Combinatorial techniques for database searching
Bernard Chazelle, Alexey Lvov · Medical Entomology and Zoology · 2001
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 Wnlogpt/n-3 s/np , (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 {0, 1}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 2flogd 1-3f , for any fixed 3 > 0.