Combinatorial techniques for database searching

In this thesis we give complexity lower bounds on a variety of searching problems, establish some lower bounds on discrepancy of point-set systems and provide a general tool—the trace method—for giving lower bounds on discrepancy and off-line range searching complexity of point-set systems.; Let A be the incidence matrix of a set system with m sets and n points, m ≤ n, and let t = tr M, where M = ATA. Finally, let σ = tr M2 be the sum of squares of the elements of M. We prove that the hereditary discrepancy of the set system is at least $cns/t2t/n$, with c = 6−4. This general trace bound allows us to resolve discrepancy-type questions for which spectral methods had previously failed. Also, by using this result in conjunction with the “spectral lemma” for linear circuits, we derive a complexity bound of , (for any $3$ > 0), for off-line range searching. We give explicit hard (and high-discrepancy) instances of set-systems of points and lines, points and halfplanes and points and axis-parallel boxes.; Independently of the previous problem we consider the nearest-neighbor searching over the d-cube. Given a collection of points in {lcub}0, 1{rcub}d, find the one nearest to a query point (in the L1 sense). We establish a lower bound of $W$(log log d/log log log d) on the worst-case query time. This result holds in the cell probe model with (any amount of) polynomial storage and word-size $dO1$. The same lower bound holds for the approximate version of the problem, where the answer may be any point further than the nearest neighbor by a factor as large as , for any fixed $3$ > 0.