ACM SIGMOD Anthology ACM SIGMOD dblp.uni-trier.de

Efficient Searching with Linear Constraints.

Pankaj K. Agarwal, Lars Arge, Jeff Erickson, Paolo Giulio Franciosa, Jeffrey Scott Vitter: Efficient Searching with Linear Constraints. PODS 1998: 169-178
@inproceedings{DBLP:conf/pods/AgarwalAEFV98,
  author    = {Pankaj K. Agarwal and
               Lars Arge and
               Jeff Erickson and
               Paolo Giulio Franciosa and
               Jeffrey Scott Vitter},
  title     = {Efficient Searching with Linear Constraints},
  booktitle = {Proceedings of the Seventeenth ACM SIGACT-SIGMOD-SIGART Symposium
               on Principles of Database Systems, June 1-3, 1998, Seattle, Washington},
  publisher = {ACM Press},
  year      = {1998},
  isbn      = {0-89791-996-3},
  pages     = {169-178},
  ee        = {http://doi.acm.org/10.1145/275487.275506, db/conf/pods/AgarwalAEFV98.html},
  crossref  = {DBLP:conf/pods/98},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

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.

Copyright © 1998 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.


Load The ACM SIGMOD Anthology, CDROM Edition, Volume 1-3, PODS '82-'98. and ... Load The ACM SIGMOD Anthology, Silver Edition, DVD 1, Proceedings. and ... BibTeX

Printed Edition

Proceedings of the Seventeenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, June 1-3, 1998, Seattle, Washington. ACM Press 1998, ISBN 0-89791-996-3
Contents BibTeX

Online Edition: ACM Digital Library

[Index Terms]
[Full Text in PDF Format, 1239 KB]

References

[1]
...
[2]
...
[3]
...
[4]
Pankaj K. Agarwal, Marc J. van Kreveld, Mark H. Overmars: Intersection Queries in Curved Objects. J. Algorithms 15(2): 229-266(1993) BibTeX
[5]
...
[6]
Rudolf Bayer, Edward M. McCreight: Organization and Maintenance of Large Ordered Indices. Acta Inf. 1: 173-189(1972) BibTeX
[7]
Norbert Beckmann, Hans-Peter Kriegel, Ralf Schneider, Bernhard Seeger: The R*-Tree: An Efficient and Robust Access Method for Points and Rectangles. SIGMOD Conference 1990: 322-331 BibTeX
[8]
Stefan Berchtold, Christian Böhm, Daniel A. Keim, Hans-Peter Kriegel: A Cost Model For Nearest Neighbor Search in High-Dimensional Data Space. PODS 1997: 78-86 BibTeX
[9]
Stefan Berchtold, Daniel A. Keim, Hans-Peter Kriegel: The X-tree : An Index Structure for High-Dimensional Data. VLDB 1996: 28-39 BibTeX
[10]
Bernard Chazelle: Filtering Search: A New Approach to Query-Answering. SIAM J. Comput. 15(3): 703-724(1986) BibTeX
[11]
Bernard Chazelle, R. Cole, Franco P. Preparata, Chee-Keng Yap: New Upper Bounds for Neighbor Searching. Information and Control 68(1-3): 105-124(1986) BibTeX
[12]
Bernard Chazelle, Leonidas J. Guibas, D. T. Lee: The Power of Geometric Duality. BIT 25(1): 76-90(1985) BibTeX
[13]
...
[14]
...
[15]
Douglas Comer: The Ubiquitous B-Tree. ACM Comput. Surv. 11(2): 121-137(1979) BibTeX
[16]
...
[17]
Freddy Dumortier, Marc Gyssens, Luc Vandeurzen, Dirk Van Gucht: On the Decidability of Semi-Linearity of Semi-Algebraic Sets and Its Implications for Spatial Databases. PODS 1997: 68-77 BibTeX
[18]
Herbert Edelsbrunner, Emo Welzl: Constructing Belts in Two-Dimensional Arrangements with Applications. SIAM J. Comput. 15(1): 271-284(1986) BibTeX
[19]
Georgios Evangelidis, David B. Lomet, Betty Salzberg: The hB-Pi-Tree: A Multi-Attribute Index Supporting Concurrency, Recovery and Node Consolidation. VLDB J. 6(1): 1-25(1997) BibTeX
[20]
...
[21]
...
[22]
Jonathan Goldstein, Raghu Ramakrishnan, Uri Shaft, Jie-Bing Yu: Processing Queries By Linear Constraints. PODS 1997: 257-267 BibTeX
[23]
Michael T. Goodrich, Jyh-Jong Tsay, Darren Erik Vengroff, Jeffrey Scott Vitter: External-Memory Computational Geometry (Preliminary Version). FOCS 1993: 714-723 BibTeX
[24]
Ralf Hartmut Güting: An Introduction to Spatial Database Systems. VLDB J. 3(4): 357-399(1994) BibTeX
[25]
Antonin Guttman: R-Trees: A Dynamic Index Structure for Spatial Searching. SIGMOD Conference 1984: 47-57 BibTeX
[26]
...
[27]
Andreas Henrich: Improving the Performance of Multi-Dimensional Access Structures Based on k-d-Trees. ICDE 1996: 68-75 BibTeX
[28]
Erik G. Hoel, Hanan Samet: A Qualitative Comparison Study of Data Structures for Large Line Segment Databases. SIGMOD Conference 1992: 205-214 BibTeX
[29]
Ibrahim Kamel, Christos Faloutsos: Hilbert R-tree: An Improved R-tree using Fractals. VLDB 1994: 500-509 BibTeX
[30]
Paris C. Kanellakis, Sridhar Ramaswamy, Darren Erik Vengroff, Jeffrey Scott Vitter: Indexing for Data Models with Constraints and Classes. J. Comput. Syst. Sci. 52(3): 589-612(1996) BibTeX
[31]
David B. Lomet, Betty Salzberg: The hB-Tree: A Multiattribute Indexing Method with Good Guaranteed Performance. ACM Trans. Database Syst. 15(4): 625-658(1990) BibTeX
[32]
...
[33]
...
[34]
Jirí Matousek: Geometric Range Searching. ACM Comput. Surv. 26(4): 421-461(1994) BibTeX
[35]
Rajeev Motwani, Prabhakar Raghavan: Randomized Algorithms. Cambridge University Press 1995, ISBN 0-521-47465-5
BibTeX
[36]
Jürg Nievergelt, Hans Hinterberger, Kenneth C. Sevcik: The Grid File: An Adaptable, Symmetric Multikey File Structure. ACM Trans. Database Syst. 9(1): 38-71(1984) BibTeX
[37]
...
[38]
Mark H. Overmars, Jan van Leeuwen: Maintenance of Configurations in the Plane. J. Comput. Syst. Sci. 23(2): 166-204(1981) BibTeX
[39]
...
[40]
Sridhar Ramaswamy, Sairam Subramanian: Path Caching: A Technique for Optimal External Searching. PODS 1994: 25-35 BibTeX
[41]
John T. Robinson: The K-D-B-Tree: A Search Structure For Large Multidimensional Dynamic Indexes. SIGMOD Conference 1981: 10-18 BibTeX
[42]
...
[43]
Hanan Samet: The Design and Analysis of Spatial Data Structures. Addison-Wesley 1990
BibTeX
[44]
Timos K. Sellis, Nick Roussopoulos, Christos Faloutsos: The R+-Tree: A Dynamic Index for Multi-Dimensional Objects. VLDB 1987: 507-518 BibTeX
[45]
...
[46]
...
[47]
Dan E. Willard: Polygon Retrieval. SIAM J. Comput. 11(1): 149-165(1982) BibTeX

Referenced by

  1. Haifeng Yu, Amin Vahdat: Efficient Numerical Error Bounding for Replicated Network Services. VLDB 2000: 123-133
  2. Simonas Saltenis, Christian S. Jensen, Scott T. Leutenegger, Mario A. Lopez: Indexing the Positions of Continuously Moving Objects. SIGMOD Conference 2000: 331-342
  3. Yuan-Chi Chang, Lawrence D. Bergman, Vittorio Castelli, Chung-Sheng Li, Ming-Ling Lo, John R. Smith: The Onion Technique: Indexing for Linear Optimization Queries. SIGMOD Conference 2000: 391-402
  4. Pankaj K. Agarwal, Lars Arge, Jeff Erickson: Indexing Moving Points. PODS 2000: 175-186
  5. George Kollios, Dimitrios Gunopulos, Vassilis J. Tsotras: On Indexing Mobile Objects. PODS 1999: 261-272
  6. Lars Arge, Vasilis Samoladas, Jeffrey Scott Vitter: On Two-Dimensional Indexability and Optimal Range Search Indexing. PODS 1999: 346-357
  7. Elisa Bertino, Barbara Catania, Boris Chidlovskii: Indexing Constraint Databases by Using a Dual Representation. ICDE 1999: 618-627
  8. Jeffrey Scott Vitter: External Memory Algorithms. PODS 1998: 119-128
BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Sat May 16 23:34:20 2009