TY - CONF
T1 - Efficient searching with linear constraints
AU - Agarwal, Pankaj K.
AU - Arge, Lars
AU - Erickson, Jeff
AU - Franciosa, Paolo G.
AU - Vitter, Jeffrey Scott
N1 - Funding Information:
4E-mail: jeffe cs.unic.edu; http: www.uiuc.edu jeffe. Supported in part by National Science Foundation Grant DMS-9627683 and by U.S. Army Research Office MURI Grant DAAH04-96-1-0013. Part of this work was done while this author was at Duke University as a postdoctoral fellow.
Funding Information:
3E-mail: large cs.duke.edu; http: www.cs.duke.edu large. Supported in part by U.S. Army Research Office MURI Grant DAAH04-96-1-0013 and by National Science Foundation Research Grant ESS EIA-9870724.
Funding Information:
6E-mail: jsv cs.duke.edu; http www.cs.duke.edu jsv. Supported in part by U.S. Army Research Office MURI Grant DAAH04-96-1-0013 and by National Science Foundation Grants CCR-9522047 and CCR-9732787. Part of this work was done while on sabbatical at INRIA in Sophia Antipolis, France.
Funding Information:
2E-mail: panka cs.duke.edu; http www.cs.duke.edu pankaj. Supported in part by National Science Foundation Research Grants EIA-9870724 and CCR-9732787, by Army Research Office MURI Grant DAAH04-96-1-0013, by a Sloan fellowship, by a National Science Foundation NYI award, and matching funds from Xerox Corporation, and by a grant from the U.S. Israeli Binational Science Foundation.
Funding Information:
5E-mail: pgf dis.uniroma1.it; http www.dis.uniroma1.it pgf. Supported in part by EU Project 20244 (Alcom-IT). Part of this work was done while visiting Duke University under the Short Term Mobility Program of CNR.
Copyright:
Copyright 2020 Elsevier B.V., All rights reserved.
PY - 1998
Y1 - 1998
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=0031645633&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0031645633&partnerID=8YFLogxK
U2 - 10.1145/275487.275506
DO - 10.1145/275487.275506
M3 - Paper
AN - SCOPUS:0031645633
SP - 169
EP - 178
T2 - Proceedings of the 1998 17th ACM SIGART-SIGMOD-SIGART Symposium on Principles of Database Systems, PODS
Y2 - 1 June 1998 through 3 June 1998
ER -