On two-dimensional indexability and optimal range search indexing

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

On two-dimensional indexability and optimal range search indexing

Full text

Pdf (1.60 MB)

Source

Symposium on Principles of Database Systems archive
Proceedings of the eighteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems table of contents

Philadelphia, Pennsylvania, United States

Pages: 346 - 357

Year of Publication: 1999

ISBN:1-58113-062-7

Authors

Lars Arge	Center for Geometric Computing, Department of Computer Science, Duke University, Box 90129, Durham, NC
Vasilis Samoladas	Department of Computer Sciences, University of Texas at Austin, Austin, TX
Jeffrey Scott Vitter	Center for Geometric Computing, Department of Computer Science, Duke University, Box 90129, Durham, NC

Sponsors

SIGART: ACM Special Interest Group on Artificial Intelligence
SIGMOD: ACM Special Interest Group on Management of Data
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 6, Downloads (12 Months): 54, Citation Count: 32

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/303976.304010 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Pankaj K. Agarwal , Lars Arge , Jeff Erickson , Paolo G. Franciosa , Jeffry Scott Vitter, Efficient searching with linear constraints, Proceedings of the seventeenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.169-178, June 01-04, 1998, Seattle, Washington, United States [doi>10.1145/275487.275506]
	2	L. Arge , J. S. Vitter, Optimal dynamic interval management in external memory, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.560, October 14-16, 1996
	3	R. Bayer and E. McCreight. Organization and maintenance of large ordered indexes. Acta Informatica, 1:173- 189, 1972.
	4	G. Blankenagel and R. H. Giiting. XP-trees--External priority search trees. Technical report, FernUniversit/it Hagen, Informatik-Bericht Nr. 92, 1990.
	5	Bernard Chazelle, Filtering search: a new approach to query answering, SIAM Journal on Computing, v.15 n.3, p.703-724, August 1986 [doi>10.1137/0215051]
	6	Douglas Comer, Ubiquitous B-Tree, ACM Computing Surveys (CSUR), v.11 n.2, p.121-137, June 1979 [doi>10.1145/356770.356776]
	7	Volker Gaede , Oliver Günther, Multidimensional access methods, ACM Computing Surveys (CSUR), v.30 n.2, p.170-231, June 1998 [doi>10.1145/280277.280279]
	8	Roberto Grossi , Giuseppe F. Italiano, Efficient cross-trees for external memory, External memory algorithms, American Mathematical Society, Boston, MA, 1999
	9	Antonin Guttman, R-trees: a dynamic index structure for spatial searching, Proceedings of the 1984 ACM SIGMOD international conference on Management of data, June 18-21, 1984, Boston, Massachusetts
	10	Joseph M. Hellerstein , Elias Koutsoupias , Christos H. Papadimitriou, On the analysis of indexing schemes, Proceedings of the sixteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.249-256, May 11-15, 1997, Tucson, Arizona, United States [doi>10.1145/263661.263688]
	11	S. Huddleston and K. Mehlhorn. A new data structure for representing sorted lists. Acta Informatica, 17:157- 184, 1982.
	12	Ch. Icking , R. Klein , Th. Ottmann, Priority search trees in secondary memory (extended abstract), Proceedings of the International Workshop WG '87 on Graph-theoretic concepts in computer science, p.84-93, July 1988, Kloster Banz/Staffelstein, Germany
	13	Paris Kanellakis , Sridhar Ramaswamy , Darren E. Vengroff , Jeffrey Scott Vitter, Indexing for data models with constraints and classes, Journal of Computer and System Sciences, v.52 n.3, p.589-612, June 1996 [doi>10.1006/jcss.1996.0043]
	14	Elias Koutsoupias , D. S. Taylor, Tight bounds for 2-dimensional indexing schemes, Proceedings of the seventeenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.52-58, June 01-04, 1998, Seattle, Washington, United States [doi>10.1145/275487.275494]
	15	David B. Lomet , Betty Salzberg, The hB-tree: a multiattribute indexing method with good guaranteed performance, ACM Transactions on Database Systems (TODS), v.15 n.4, p.625-658, Dec. 1990 [doi>10.1145/99935.99949]
	16	E. McCreight. Priority search trees. SIAM Journal of Computing, 14(2):257-276, 1985.
	17	J. Nievergelt , Hans Hinterberger , Kenneth C. Sevcik, The Grid File: An Adaptable, Symmetric Multikey File Structure, ACM Transactions on Database Systems (TODS), v.9 n.1, p.38-71, March 1984 [doi>10.1145/348.318586]
	18	Jack A. Orenstein, Spatial query processing in an object-oriented database system, Proceedings of the 1986 ACM SIGMOD international conference on Management of data, p.326-336, May 28-30, 1986, Washington, D.C., United States
	19	Mark H. Overmars, Design of Dynamic Data Structures, Springer-Verlag New York, Inc., Secaucus, NJ, 1987
	20	Sridhar Ramaswamy , Sairam Subramanian, Path caching (extended abstract): a technique for optimal external searching, Proceedings of the thirteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.25-35, May 24-27, 1994, Minneapolis, Minnesota, United States [doi>10.1145/182591.182595]
	21	John T. Robinson, The K-D-B-tree: a search structure for large multidimensional dynamic indexes, Proceedings of the 1981 ACM SIGMOD international conference on Management of data, April 29-May 01, 1981, Ann Arbor, Michigan [doi>10.1145/582318.582321]
	22	Hanan Samet, Applications of spatial data structures: Computer graphics, image processing, and GIS, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
	23	Hanan Samet, The design and analysis of spatial data structures, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
	24	Vasilis Samoladas , Daniel P. Miranker, A lower bound theorem for indexing schemes and its application to multidimensional range queries, Proceedings of the seventeenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.44-51, June 01-04, 1998, Seattle, Washington, United States [doi>10.1145/275487.275493]
	25	Timos K. Sellis , Nick Roussopoulos , Christos Faloutsos, The R+-Tree: A Dynamic Index for Multi-Dimensional Objects, Proceedings of the 13th International Conference on Very Large Data Bases, p.507-518, September 01-04, 1987
	26	Sairam Subramanian , Sridhar Ramaswamy, The P-range tree: a new data structure for range searching in secondary memory, Proceedings of the sixth annual ACM-SIAM symposium on Discrete algorithms, p.378-387, January 22-24, 1995, San Francisco, California, United States
	27	D. E. Vengroff. TPIE User Manual and Reference. Duke University, 1997.- Available at http://www, on. duke. edu/TPIE/.
	28	Darren Erik Vengroff , Jeffrey Scott Vitter, Efficient 3-D range searching in external memory, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.192-201, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.237864]
	29	Jeffrey Scott Vitter, External memory algorithms and data structures, External memory algorithms, American Mathematical Society, Boston, MA, 1999

CITED BY 32

	Joseph M. Hellerstein , Elias Koutsoupias , Daniel P. Miranker , Christos H. Papadimitriou , Vasilis Samoladas, On a model of indexability and its bounds for range queries, Journal of the ACM (JACM), v.49 n.1, p.35-55, January 2002
	Simonas Šaltenis , Christian S. Jensen , Scott T. Leutenegger , Mario A. Lopez, Indexing the positions of continuously moving objects, ACM SIGMOD Record, v.29 n.2, p.331-342, June 2000
	Pankaj K. Agarwal , Lars Arge , Jeff Erickson, Indexing moving points (extended abstract), Proceedings of the nineteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.175-186, May 15-18, 2000, Dallas, Texas, United States
	Jeffrey Scott Vitter, External memory algorithms and data structures: dealing with massive data, ACM Computing Surveys (CSUR), v.33 n.2, p.209-271, June 2001
	Lars Arge, External memory data structures, Handbook of massive data sets, Kluwer Academic Publishers, Norwell, MA, 2002
	Gerth Stolting Brodal , Rolf Fagerberg, Lower bounds for external memory dictionaries, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
	Paolo Ferragina , Nick Koudas , S. Muthukrishnan , Divesh Srivastava, Two-dimensional substring indexing, Journal of Computer and System Sciences, v.66 n.4, p.763-774, 1 June 2003
	Flip Korn , Bernd-Uwe Pagel , Christos Faloutsos, On the 'Dimensionality Curse' and the 'Self-Similarity Blessing', IEEE Transactions on Knowledge and Data Engineering, v.13 n.1, p.96-111, January 2001
	Pankaj K. Agarwal , Lars Arge , Andrew Danner , Bryan Holland-Minkley, Cache-oblivious data structures for orthogonal range searching, Proceedings of the nineteenth annual symposium on Computational geometry, June 08-10, 2003, San Diego, California, USA
	Pankaj K. Agarwal , Lars Arge , Jeff Erickson, Indexing moving points, Journal of Computer and System Sciences, v.66 n.1, p.207-243, 01 February 2003
	Xian Liu , Wilsun Xu, A Stochastic Programming Approach for Range Query Retrieval Problems, IEEE Transactions on Knowledge and Data Engineering, v.14 n.4, p.867-880, July 2002
	Pankaj K. Agarwal , Lars Arge , Ke Yi, An optimal dynamic interval stabbing-max data structure?, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
	Lars Arge , Gerth Stølting Brodal , Rolf Fagerberg , Morten Laustsen, Cache-oblivious planar orthogonal range searching and counting, Proceedings of the twenty-first annual symposium on Computational geometry, June 06-08, 2005, Pisa, Italy
	Noga Alon , Nick Duffield , Carsten Lund , Mikkel Thorup, Estimating arbitrary subset sums with few probes, Proceedings of the twenty-fourth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 13-15, 2005, Baltimore, Maryland
	Holger Bast , Ingmar Weber, Type less, find more: fast autocompletion search with a succinct index, Proceedings of the 29th annual international ACM SIGIR conference on Research and development in information retrieval, August 06-11, 2006, Seattle, Washington, USA
	S. Sioutas , L. Drossos , D. Tsolis , T. S. Papatheodorou, Embedding advanced geometric techniques into SQL for efficient indexing of mobile objects, Proceedings of the 5th WSEAS International Conference on Applied Informatics and Communications, p.348-356, September 15-17, 2005, Malta
	Delis Vasilis , Makris Christos , Sioutas Spiros, A provably efficient computational model for approximate spatiotemporal retrieval, Proceedings of the 7th ACM international symposium on Advances in geographic information systems, p.40-46, November 02-06, 1999, Kansas City, Missouri, United States
	Paolo Ferragina , Nick Koudas , Divesh Srivastava , S. Muthukrishnan, Two-dimensional substring indexing, Proceedings of the twentieth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.282-288, May 2001, Santa Barbara, California, United States
	Thomas H. Meyer, Fast algorithms using minimal data structures for common topological relationships in large, irregularly spaced topographic data sets, Computers & Geosciences, v.33 n.3, p.325-334, March, 2007
	Lars Arge , Norbert Zeh, Simple and semi-dynamic structures for cache-oblivious planar orthogonal range searching, Proceedings of the twenty-second annual symposium on Computational geometry, June 05-07, 2006, Sedona, Arizona, USA
	Reynold Cheng , Yuni Xia , Sunil Prabhakar , Rahul Shah , Jeffrey Scott Vitter, Efficient indexing methods for probabilistic threshold queries over uncertain data, Proceedings of the Thirtieth international conference on Very large data bases, p.876-887, August 31-September 03, 2004, Toronto, Canada
	George Kollios , Dimitris Papadopoulos , Dimitrios Gunopulos , J. Tsotras, Indexing mobile objects using dual transformations, The VLDB Journal — The International Journal on Very Large Data Bases, v.14 n.2, p.238-256, April 2005
	Mohamed Y. Eltabakh , Wing-Kai Hon , Rahul Shah , Walid G. Aref , Jeffrey S. Vitter, The SBC-tree: an index for run-length compressed sequences, Proceedings of the 11th international conference on Extending database technology: Advances in database technology, March 25-29, 2008, Nantes, France
	Jeffrey Scott Vitter, Algorithms and data structures for external memory, Foundations and Trends® in Theoretical Computer Science, v.2 n.4, p.305-474, January 2008
	Holger Bast , Christian W. Mortensen , Ingmar Weber, Output-sensitive autocompletion search, Information Retrieval, v.11 n.4, p.269-286, August 2008
	S. Sioutas , K. Tsakalidis , K. Tsichlas , C. Makris , Y. Manolopoulos, A new approach on indexing mobile objects on the plane, Data & Knowledge Engineering, v.67 n.3, p.362-380, December, 2008
	Michail Argyriou , Vasilis Samoladas , Spyros Blanas, GRaSP: generalized range search in peer-to-peer networks, Proceedings of the 3rd international conference on Scalable information systems, June 04-06, 2008, Vico Equense, Italy
	Peyman Afshani , Timothy M. Chan, Optimal halfspace range reporting in three dimensions, Proceedings of the Nineteenth Annual ACM -SIAM Symposium on Discrete Algorithms, p.180-186, January 04-06, 2009, New York, New York
	Peyman Afshani , Chris Hamilton , Norbert Zeh, A general approach for cache-oblivious range reporting and approximate range counting, Proceedings of the 25th annual symposium on Computational geometry, June 08-10, 2009, Aarhus, Denmark
	Ke Yi, Dynamic indexability and lower bounds for dynamic one-dimensional range query indexes, Proceedings of the twenty-eighth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 29-July 01, 2009, Providence, Rhode Island, USA
	Lars Arge, Worst-case efficient range search indexing: invited tutorial, Proceedings of the twenty-eighth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 29-July 01, 2009, Providence, Rhode Island, USA
	Peyman Afshani , Chris Hamilton , Norbert Zeh, Cache-oblivious range reporting with optimal queries requires superlinear space, Proceedings of the 25th annual symposium on Computational geometry, June 08-10, 2009, Aarhus, Denmark