On the analysis of indexing schemes

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

On the analysis of indexing schemes

Full text

Pdf (1.28 MB)

Source

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

Tucson, Arizona, United States

Pages: 249 - 256

Year of Publication: 1997

ISBN:0-89791-910-6

Authors

Joseph M. Hellerstein	Division of Computer Science, UC Berkeley, Berkeley, CA
Elias Koutsoupias	Department of Computer Science, UCLA, Los Angeles, CA
Christos H. Papadimitriou	Division of Computer Science, UC Berkeley, Berkeley, CA

Sponsor

SIGMOD: ACM Special Interest Group on Management of Data

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 13, Downloads (12 Months): 46, Citation Count: 42

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/263661.263688 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	Alfred V. Aho , John E. Hopcroft , Jeffrey Ullman , J. D. Ullman , J. E. Hopcroft, Data Structures and Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1983
	2	R. Bayer and C. McCreight. Organization and Maintenance of Large Ordered Indexes. Acta Informatica 1(3):173-189, 1972.
	3	Alberto Belussi , Christos Faloutsos, Estimating the Selectivity of Spatial Queries Using the `Correlation' Fractal Dimension, Proceedings of the 21th International Conference on Very Large Data Bases, p.299-310, September 11-15, 1995
	4	Douglas Comer, Ubiquitous B-Tree, ACM Computing Surveys (CSUR), v.11 n.2, p.121-137, June 1979 [doi>10.1145/356770.356776]
	5	R. A. Finkel and J. L. Bentley. Quad-Trees: A Data Structure For Retrieval On Composite Keys. Acta Informatica, 4(1):1--9, 1974.
	6	Christos Faloutsos, Searching Multimedia Databases by Content, Kluwer Academic Publishers, Norwell, MA, 1996
	7	Christos Faloutsos , Ibrahim Kamel, Beyond uniformity and independence: analysis of R-trees using the concept of fractal dimension, Proceedings of the thirteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.4-13, May 24-27, 1994, Minneapolis, Minnesota, United States [doi>10.1145/182591.182593]
	8	Christos Faloutsos , Volker Gaede, Analysis of n-Dimensional Quadtrees using the Hausdorff Fractal Dimension, Proceedings of the 22th International Conference on Very Large Data Bases, p.40-50, September 03-06, 1996
	9	Christos Faloutsos , Yossi Matias , Abraham Silberschatz, Modeling Skewed Distribution Using Multifractals and the `80-20' Law, Proceedings of the 22th International Conference on Very Large Data Bases, p.307-317, September 03-06, 1996
	10	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
	11	Joseph M. Hellerstein , Jeffrey F. Naughton , Avi Pfeffer, Generalized Search Trees for Database Systems, Proceedings of the 21th International Conference on Very Large Data Bases, p.562-573, September 11-15, 1995
	12	L. Hellerstein , P. Klein , R. Wilber, On the time-space complexity of reachability queries for preprocessed graphs, Information Processing Letters, v.35 n.5, p.261-267, Aug. 1990 [doi>10.1016/0020-0190(90)90055-3]
	13	Sandy Irani , Anna R. Karlin, Online computation, Approximation algorithms for NP-hard problems, PWS Publishing Co., Boston, MA, 1996
	14	H. V. Jagadish, Linear clustering of objects with multiple attributes, Proceedings of the 1990 ACM SIGMOD international conference on Management of data, p.332-342, May 23-26, 1990, Atlantic City, New Jersey, United States
	15	Paris C. Kanellakis , Sridhar Ramaswamy , Darren E. Vengroff , Jeffrey S. Vitter, Indexing for data models with constraints and classes (extended abstract), Proceedings of the twelfth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.233-243, May 25-28, 1993, Washington, D.C., United States [doi>10.1145/153850.153884]
	16	Donald E. Knuth, The art of computer programming, volume 3: (2nd ed.) sorting and searching, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1998
	17	L. Lovhsz. Combinatorial Problems and Exercises. North-Holland, Amsterdam, 1979.
	18	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]
	19	Kurt Mehlhorn, Data structures and algorithms 3: multi-dimensional searching and computational geometry, Springer-Verlag New York, Inc., New York, NY, 1984
	20	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]
	21	M. H. Nodine, M. T. Goodrich, and J. S. Vitter. Blocking for External Graph Searching. Algorithmica, 16 (2):181-214, August.1996.
	22	Bernd-Uwe Pagel , Hans-Werner Six , Heinrich Toben , Peter Widmayer, Towards an analysis of range query performance in spatial data structures, Proceedings of the twelfth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.214-221, May 25-28, 1993, Washington, D.C., United States [doi>10.1145/153850.153878]
	23	Paris C. Kanellakis , Sridhar Ramaswamy , Darren E. Vengroff , Jeffrey S. Vitter, Indexing for data models with constraints and classes (extended abstract), Proceedings of the twelfth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.233-243, May 25-28, 1993, Washington, D.C., United States [doi>10.1145/153850.153884]
	24	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]
	25	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]
	26	Michiel H. M. Smid , Mark H. Overmars, Maintaining range trees in secondary memory. Part II: lower bounds, Acta Informatica, v.27 n.5, p.453-480, 1990 [doi>10.1007/BF00289019]
	27	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
	28	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
	29	Robert Endre Tarjan, Data structures and network algorithms, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1983
	30	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]
	31	Andrew Chi-Chih Yao, Should Tables Be Sorted?, Journal of the ACM (JACM), v.28 n.3, p.615-628, July 1981 [doi>10.1145/322261.322274]

CITED BY 42

	Susanne E. Hambrusch , Chuan-Ming Liu, Data replication for external searching in static tree structures, Proceedings of the ninth international conference on Information and knowledge management, p.360-367, November 06-11, 2000, McLean, Virginia, United States
	Betty Salzberg , Vassilis J. Tsotras, Comparison of access methods for time-evolving data, ACM Computing Surveys (CSUR), v.31 n.2, p.158-221, June 1999
	Marcel Kornacker , Mehul Shah , Joseph M. Hellerstein, AMDB: an access method debugging tool, ACM SIGMOD Record, v.27 n.2, p.570-571, June 1998
	Eamonn Keogh , Kaushik Chakrabarti , Michael Pazzani , Sharad Mehrotra, Locally adaptive dimensionality reduction for indexing large time series databases, ACM SIGMOD Record, v.30 n.2, p.151-162, June 2001
	Jeffrey Scott Vitter, External memory algorithms, Proceedings of the seventeenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.119-128, June 01-04, 1998, Seattle, Washington, United States
	Elias Koutsoupias , David Taylor, Indexing schemes for random points, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.596-602, January 17-19, 1999, Baltimore, Maryland, 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
	Eamonn Keogh , Selina Chu , Michael Pazzani, Ensemble-index: a new approach to indexing large databases, Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining, p.117-125, August 26-29, 2001, San Francisco, California
	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
	Christian Böhm , Stefan Berchtold , Daniel A. Keim, Searching in high-dimensional spaces: Index structures for improving the performance of multimedia databases, ACM Computing Surveys (CSUR), v.33 n.3, p.322-373, September 2001
	Kaushik Chakrabarti , Eamonn Keogh , Sharad Mehrotra , Michael Pazzani, Locally adaptive dimensionality reduction for indexing large time series databases, ACM Transactions on Database Systems (TODS), v.27 n.2, p.188-228, June 2002
	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
	H. V. Jagadish , Laks V. S. Lakshmanan , Divesh Srivastava, Snakes and sandwiches: optimal clustering strategies for a data warehouse, ACM SIGMOD Record, v.28 n.2, p.37-48, June 1999
	Susanne E. Hambrusch , Chuan-Ming Liu, Data replication in static tree structures, Information Processing Letters, v.86 n.4, p.197-202, 31 May 2003
	Lars Arge, External memory data structures, Handbook of massive data sets, Kluwer Academic Publishers, Norwell, MA, 2002
	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
	Jessica Lin , Eamonn Keogh , Stefano Lonardi , Bill Chiu, A symbolic representation of time series, with implications for streaming algorithms, Proceedings of the 8th ACM SIGMOD workshop on Research issues in data mining and knowledge discovery, June 13-13, 2003, San Diego, California
	Lars Arge , Vasilis Samoladas , Jeffrey Scott Vitter, On two-dimensional indexability and optimal range search indexing, Proceedings of the eighteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.346-357, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
	Sergey Melnik , Hector Garcia-Molina, Adaptive algorithms for set containment joins, ACM Transactions on Database Systems (TODS), v.28 n.1, p.56-99, March 2003
	George Kollios , Vassilis J. Tsotras , Dimitrios Gunopulos , Alex Delis , Marios Hadjieleftheriou, Indexing Animated Objects Using Spatiotemporal Access Methods, IEEE Transactions on Knowledge and Data Engineering, v.13 n.5, p.758-777, September 2001
	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
	Bela Stantic , Sankalp Khanna , John Thornton, An efficient method for indexing now-relative bitemporal data, Proceedings of the fifteenth Australasian database conference, p.113-122, January 01, 2004, Dunedin, New Zealand
	Rui Zhang , Panos Kalnis , Beng Chin Ooi , Kian-Lee Tan, Generalized multidimensional data mapping and query processing, ACM Transactions on Database Systems (TODS), v.30 n.3, p.661-697, September 2005
	Raymond T. Ng , Dominic Tam, Multilevel Filtering for High-Dimensional Image Data: Why and How, IEEE Transactions on Knowledge and Data Engineering, v.11 n.6, p.916-928, November 1999
	Hakan Ferhatosmanoǧlu , Divyakant Agrawal , Ömer Eǧecioǧlu , Amr El Abbadi, Optimal data-space partitioning of spatial data for parallel I/O, Distributed and Parallel Databases, v.17 n.1, p.75-101, January 2005
	Michail Vlachos , Christopher Meek , Zografoula Vagena , Dimitrios Gunopulos, Identifying similarities, periodicities and bursts for online search queries, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France
	Jessica Lin , Eamonn Keogh , Li Wei , Stefano Lonardi, Experiencing SAX: a novel symbolic representation of time series, Data Mining and Knowledge Discovery, v.15 n.2, p.107-144, October 2007
	Allan Borodin , Rafail Ostrovsky , Yuval Rabani, Lower bounds for high dimensional nearest neighbor search and related problems, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.312-321, May 01-04, 1999, Atlanta, Georgia, United States
	Uri Shaft , Raghu Ramakrishnan, Theory of nearest neighbors indexability, ACM Transactions on Database Systems (TODS), v.31 n.3, p.814-838, September 2006
	Eamonn Keogh , Chotirat Ann Ratanamahatana, Exact indexing of dynamic time warping, Knowledge and Information Systems, v.7 n.3, p.358-386, March 2005
	Vladimir Pestov , Aleksandar Stojmirović, Indexing schemes for similarity search: an illustrated paradigm, Fundamenta Informaticae, v.70 n.4, p.367-385, April 2006
	Vassilis G. Kaburlasos , Ioannis N. Athanasiadis , Pericles A. Mitkas, Fuzzy lattice reasoning (FLR) classifier and its application for ambient ozone estimation, International Journal of Approximate Reasoning, v.45 n.1, p.152-188, May, 2007
	Eamonn Keogh, Exact indexing of dynamic time warping, Proceedings of the 28th international conference on Very Large Data Bases, p.406-417, August 20-23, 2002, Hong Kong, China
	Edwin M. Knorr , Raymond T. Ng , Vladimir Tucakov, Distance-based outliers: algorithms and applications, The VLDB Journal — The International Journal on Very Large Data Bases, v.8 n.3-4, p.237-253, February 2000
	Edwin M. Knorr , Raymond T. Ng, Algorithms for Mining Distance-Based Outliers in Large Datasets, Proceedings of the 24rd International Conference on Very Large Data Bases, p.392-403, August 24-27, 1998
	Roger Weber , Hans-Jörg Schek , Stephen Blott, A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces, Proceedings of the 24rd International Conference on Very Large Data Bases, p.194-205, August 24-27, 1998
	Jonathan Goldstein , Raghu Ramakrishnan, Contrast Plots and P-Sphere Trees: Space vs. Time in Nearest Neighbour Searches, Proceedings of the 26th International Conference on Very Large Data Bases, p.429-440, September 10-14, 2000
	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
	Yufei Tao , Xiaokui Xiao, Primal or dual: which promises faster spatiotemporal search?, The VLDB Journal — The International Journal on Very Large Data Bases, v.17 n.5, p.1253-1270, August 2008
	Bela Stantic , Abdul Sattar , Paolo Terenziani, The POINT approach to represent now in bitemporal databases, Journal of Intelligent Information Systems, v.32 n.3, p.297-323, June 2009
	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
	Jorg Hoffmann , Jana Koehler, A new method to index and query sets, Proceedings of the 16th international joint conference on Artifical intelligence, p.462-467, July 31-August 06, 1999, Stockholm, Sweden