Efficient Searching with Linear Constraints
Pankaj K. Agarwal, Lars Arge, Jeff Erickson, Paolo Giulio Franciosa, Jeffrey Scott Vitter
Full Paper (PDF)

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.

References

References, where available, link to the DBLP on the World Wide Web.

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

@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-966-3},
pages = {169-178},
crossref = {DBLP:conf/pods/98},
bibsource = {DBLP, http://dblp.uni-trier.de}
}


DBLP: Copyright ©1999 by Michael Ley (ley@uni-trier.de).