Efficient searching with linear constraints

Pankaj K. Agarwal, Lars Arge, Jeff Erickson, Paolo G. Franciosa, Jeffrey Scott Vitter

Research output: Contribution to conferencePaper

Abstract

We show how to preprocess a set S of points in Rd into an external memory data structure that efficiently supports linear-constraint 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 near-linear size data structure that can answer linear-constraint queries using an optimal number of I/Os. We also present a linear-size 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.

Original languageEnglish (US)
Pages169-178
Number of pages10
StatePublished - Jan 1 1998
Externally publishedYes
EventProceedings of the 1998 17th ACM SIGART-SIGMOD-SIGART Symposium on Principles of Database Systems, PODS - Seattle, WA, USA
Duration: Jun 1 1998Jun 3 1998

Other

OtherProceedings of the 1998 17th ACM SIGART-SIGMOD-SIGART Symposium on Principles of Database Systems, PODS
CitySeattle, WA, USA
Period6/1/986/3/98

ASJC Scopus subject areas

  • Software
  • Information Systems
  • Hardware and Architecture

Fingerprint Dive into the research topics of 'Efficient searching with linear constraints'. Together they form a unique fingerprint.

  • Cite this

    Agarwal, P. K., Arge, L., Erickson, J., Franciosa, P. G., & Vitter, J. S. (1998). Efficient searching with linear constraints. 169-178. Paper presented at Proceedings of the 1998 17th ACM SIGART-SIGMOD-SIGART Symposium on Principles of Database Systems, PODS, Seattle, WA, USA, .