Math @ Duke

Publications [#235407] of Pankaj K. Agarwal
Papers Published
 Agarwal, PK; Arge, L; Erickson, J; Franciosa, PG; Vitter, JS, Efficient searching with linear constraints,
in Seventeenth Annual Symposium on Principles of Database Systems,
Proceedings of the ACM SIGACTSIGMODSIGART Symposium on Principles of Database Systems
(1998),
pp. 169178
(last updated on 2018/03/18)
Abstract: We show how to preprocess a set S of points in Rd into an external memory data structure that efficiently supports linearconstraint queries. Each query is in the form of a linear constraint a·x≤b; the data structure must report all the points of S that satisfy the constraint. 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 nearlinear size data structure that can answer linearconstraint queries using an optimal number of I/Os. We also present a linearsize data structure that can answer queries efficiently in the worst case. We combine these two approaches to obtain tradeoffs between space and query time. Finally, we show that some of our techniques extend to higher dimensions.


dept@math.duke.edu
ph: 919.660.2800
fax: 919.660.2821
 
Mathematics Department
Duke University, Box 90320
Durham, NC 277080320

