Efficient searching with linear constraints

Abstract

We show how to preprocess a set S of points in R d into an external memory data structure that efficiently supports linear-constraint queries. Each query is in the form of a linear constraint x d a 0 + P d 1 i=1 a i x i ; 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 and d = 3, we present the first near-linear size data structures that can answer linear-constraint queries using an optimal number of I/Os. We also present a linear-size data structures that can answer queries efficiently in the worst case. For the d = 2 case, we also show how to combine these two approaches to obtain tradeoffs between space and query time. Finally, we show that some of our techniques extend to higher dimensions.