Efficient searching with linear constraints

Written with Pankaj K. Agarwal, Lars Arge, Paolo G. Franciosa, and Jeffrey Scott Vitter.
Journal of Computer and System Sciences 61(2):192-216, 2000.
(Special issue of invited papers from the 17th ACM Symposium on Principles of Database Systems)

Proceedings of the 17th ACM Symposium on Principles of Database Systems, 169-178, 1998.

We show how to preprocess a set S of points in Rd to get an external memory data structure that efficiently supports linear­constraint queries. Each query is in the form of a linear constraint x_d \le a_0 + \sum_{i=1}^d-1 a_ix_i; the data structure must report all the points of S that satisfy the constraint. (This problem is called halfspace range searching in the computational geometry literature.) Our goal is to minimize the number of disk blocks required to store the data structure and the number of disk accesses (I/Os) required to answer a query. For d=2, we present the first data structures that uses linear space and answers linear­constraint queries using an optimal number of I/Os in the worst case. For d=3. we present a near-linear size data structure that answers queries using an optimal number of I/Os on the average. We also present linear­size data structures that answer d-dimensional linear-constraint queries (and even more general d-dimensional simplex queries) efficiently in the worst case. For the case d=3, we also show how to obtain tradeoffs between space and query time.

Publications - Jeff Erickson (jeffe@cs.uiuc.edu) 30 Jul 2002