Digital Symposium Collection 2000

On Two-Dimensional Indexability and Optimal Range Search Indexing Lars Arge, Vasilis Samoladas, and Jeffrey Scott Vitter   View Paper (PDF)   Return to Indexing Abstract In this paper we settle several longstanding open problems in theory of indexability and external orthogonal range searching. In the first part of the paper, we apply the theory of indexability to the problem of two-dimensional range searching. We show that the special case of S-sided querying can be solved with constant redundancy and access overhead. From this, we derive indexing schemes for general 4-sided range queries that exhibit an optimal tradeoff between redundancy and access overhead. In the second part of the paper, we develop dynamic external memory data structures for the two query types. Our structure for 3-sided queries occupies O(N/B) disk blocks, and it supports insertions and deletions in O(logB N) I/OS and queries in O(logB N + T/B) I/OS, where B is the disk block size, N is the number of points, and T is the query output size. These bounds are optimal. Our structure for general (4-sided) range searching occupies O ((N/B) (log( N/B))/ log log, N) disk blocks and answers queries in O(log, N + T/B) I/OS, which are optimal. It also supports updates in O((logB, N)(log(N/B))/ log logB N) I/Os. References Note: References link to DBLP on the Web. [1] Pankaj K. Agarwal , Lars Arge , Jeff Erickson , Paolo Giulio Franciosa , Jeffrey Scott Vitter : Efficient Searching with Linear Constraints. PODS 1998 : 169-178 [2] ... [3] Rudolf Bayer , Edward M. McCreight : Organization and Maintenance of Large Ordered Indices. Acta Informatica 1 : 173-189(1972) [4] ... [5] Bernard Chazelle : Filtering Search: A New Approach to Query-Answering. SIAM J. Comput. 15(3) : 703-724(1986) [6] Douglas Comer : The Ubiquitous B-Tree. Computing Surveys 11(2) : 121-137(1979) [7] Volker Gaede , Oliver Günther : Multidimensional Access Methods. Computing Surveys 30(2) : 170-231(1998) [8] ... [9] Antonin Guttman : R-Trees: A Dynamic Index Structure for Spatial Searching. SIGMOD Conference 1984 : 47-57 [10] Joseph M. Hellerstein , Elias Koutsoupias , Christos H. Papadimitriou : On the Analysis of Indexing Schemes. PODS 1997 : 249-256 [11] Scott Huddleston , Kurt Mehlhorn : A New Data Structure for Representing Sorted Lists. Acta Informatica 17 : 157-184(1982) [12] Christian Icking , Rolf Klein , Thomas Ottmann : Priority Search Trees in Secondary Memory (Extended Abstract). WG 1987 : 84-93 [13] 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) [14] Elias Koutsoupias , David Scot Taylor : Tight Bounds for 2-Dimensional Indexing Schemes. PODS 1998 : 52-58 [15] David B. Lomet , Betty Salzberg : The hB-Tree: A Multiattribute Indexing Method with Good Guaranteed Performance. TODS 15(4) : 625-658(1990) [16] Edward M. McCreight : Priority Search Trees. SIAM J. Comput. 14(2) : 257-276(1985) [17] Jürg Nievergelt , Hans Hinterberger , Kenneth C. Sevcik : The Grid File: An Adaptable, Symmetric Multikey File Structure. TODS 9(1) : 38-71(1984) [18] Jack A. Orenstein : Spatial Query Processing in an Object-Oriented Database System. SIGMOD Conference 1986 : 326-336 [19] Mark H. Overmars : The Design of Dynamic Data Structures. Lecture Notes in Computer Science Vol. 156 Springer 1983, ISBN 3-540-12330-X [20] Sridhar Ramaswamy , Sairam Subramanian : Path Caching: A Technique for Optimal External Searching. PODS 1994 : 25-35 [21] John T. Robinson : The K-D-B-Tree: A Search Structure For Large Multidimensional Dynamic Indexes. SIGMOD Conference 1981 : 10-18 [22] ... [23] Hanan Samet : The Design and Analysis of Spatial Data Structures. Addison-Wesley 1990 [24] Vasilis Samoladas , Daniel P. Miranker : A Lower Bound Theorem for Indexing Schemes and Its Application to Multidimensional Range Queries. PODS 1998 : 44-51 [25] Timos K. Sellis , Nick Roussopoulos , Christos Faloutsos : The R+-Tree: A Dynamic Index for Multi-Dimensional Objects. VLDB 1987 : 507-518 [26] Sairam Subramanian , Sridhar Ramaswamy : The P-range Tree: A New Data Structure for Range Searching in Secondary Memory. SODA 1995 : 378-387 [27] ... [28] Darren Erik Vengroff , Jeffrey Scott Vitter : Efficient 3-D Range Searching in External Memory. STOC 1996 : 192-201 [29] ... BIBTEX @inproceedings{DBLP:conf/pods/ArgeSV99,   author    = {Lars Arge and                 Vasilis Samoladas and                 Jeffrey Scott Vitter},    title     = {On Two-Dimensional Indexability and Optimal Range Search Indexing},    booktitle = {Proceedings of the Eighteenth ACM SIGACT-SIGMOD-SIGART Symposium                 on Principles of Database Systems, May 31 - June 2, 1999, Philadelphia,                 Pennsylvania},    publisher = {ACM Press},    year      = {1999},    isbn      = {1-58113-062-7},    pages     = {346-357},    crossref  = {DBLP:conf/pods/99},    bibsource = {DBLP, http://dblp.uni-trier.de} } }, Copyright(C) 2000 ACM