The IGrid index

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

The IGrid index: reversing the dimensionality curse for similarity indexing in high dimensional space

Full text

Pdf (248 KB)

Source

International Conference on Knowledge Discovery and Data Mining archive
Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining table of contents

Boston, Massachusetts, United States

Pages: 119 - 129

Year of Publication: 2000

ISBN:1-58113-233-6

Authors

Charu C. Aggarwal	IBM T. J. Watson Research Center, Yorktown Heights, NY
Philip S. Yu	IBM T. J. Watson Research Center, Yorktown Heights, NY

Sponsors

SIGKDD: ACM Special Interest Group on Knowledge Discovery in Data
AAAI : Am Assoc for Artifical Intelligence
SIGART: ACM Special Interest Group on Artificial Intelligence
SIGMOD: ACM Special Interest Group on Management of Data

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 10, Downloads (12 Months): 59, Citation Count: 8

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/347090.347116 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	C. C. Aggarwal, A. Hinneburg, D. A. Keim. On The Surprising Behavior of Distance Metrics in High Dimensional Space. IBM Research Report, RC 21739, 2000.
	2	Charu C. Aggarwal , Joel L. Wolf , Philip S. Yu , Cecilia Procopiuc , Jong Soo Park, Fast algorithms for projected clustering, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.61-72, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
	3	Charu C. Aggarwal , Philip S. Yu, Finding generalized projected clusters in high dimensional spaces, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.70-81, May 15-18, 2000, Dallas, Texas, United States
	4	Charu C. Aggarwal , Joel L. Wolf , Philip S. Yu, A new method for similarity indexing of market basket data, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.407-418, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
	5	Sunil Arya, Nearest neighbor searching and applications, University of Maryland at College Park, College Park, MD, 1996
	6	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
	7	Norbert Beckmann , Hans-Peter Kriegel , Ralf Schneider , Bernhard Seeger, The R*-tree: an efficient and robust access method for points and rectangles, Proceedings of the 1990 ACM SIGMOD international conference on Management of data, p.322-331, May 23-26, 1990, Atlantic City, New Jersey, United States
	8	Kristin P. Bennett , Usama Fayyad , Dan Geiger, Density-based indexing for approximate nearest-neighbor queries, Proceedings of the fifth ACM SIGKDD international conference on Knowledge discovery and data mining, p.233-243, August 15-18, 1999, San Diego, California, United States [doi>10.1145/312129.312236]
	9	Stefan Berchtold , Christian Böhm , Hans-Peter Kriegal, The pyramid-technique: towards breaking the curse of dimensionality, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.142-153, June 01-04, 1998, Seattle, Washington, United States
	10	Deflating the Dimensionality Curse Using Multiple Fractal Dimensions, Proceedings of the 16th International Conference on Data Engineering, p.589, February 28-March 03, 2000
	11	Stefan Berchtold , Daniel A. Keim , Hans-Peter Kriegel, The X-tree: An Index Structure for High-Dimensional Data, Proceedings of the 22th International Conference on Very Large Data Bases, p.28-39, September 03-06, 1996
	12	Kevin S. Beyer , Jonathan Goldstein , Raghu Ramakrishnan , Uri Shaft, When Is ''Nearest Neighbor'' Meaningful?, Proceeding of the 7th International Conference on Database Theory, p.217-235, January 10-12, 1999
	13	G. Das, H. Mannila, P. Ronkainen. Similarity of Attributes by External Probes. KDD Conference Proceedings, pages 16-22, 1998.
	14	S. Deerwester et al. Indexing by Latent Semantic Analysis. Journal of the American Society for Information Science, 41(6): pages 391-407, 1990.
	15	U. Shaft, J. Goldstein, K. Beyer. Nearest Neighbor Query Performance for Unstable Distributions. Technical Report TR 1388, University of Wisconsin at Madison, 1998.
	16	Venkatesh Ganti , Johannes Gehrke , Raghu Ramakrishnan, CACTUS—clustering categorical data using summaries, Proceedings of the fifth ACM SIGKDD international conference on Knowledge discovery and data mining, p.73-83, August 15-18, 1999, San Diego, California, United States [doi>10.1145/312129.312201]
	17	Aristides Gionis , Piotr Indyk , Rajeev Motwani, Similarity Search in High Dimensions via Hashing, Proceedings of the 25th International Conference on Very Large Data Bases, p.518-529, September 07-10, 1999
	18	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
	19	Alexander Hinneburg , Charu C. Aggarwal , Daniel A. Keim, What Is the Nearest Neighbor in High Dimensional Spaces?, Proceedings of the 26th International Conference on Very Large Data Bases, p.506-515, September 10-14, 2000
	20	R. Jain, D. A. White. Similarity Indexing: Algorithms and Performance. SPIE Storage and Retrieval for Image and Video Databases IV, 2670: pages 62-75, 1996.
	21	Ibrahim Kamel , Christos Faloutsos, Hilbert R-tree: An Improved R-tree using Fractals, Proceedings of the 20th International Conference on Very Large Data Bases, p.500-509, September 12-15, 1994
	22	Norio Katayama , Shin'ichi Satoh, The SR-tree: an index structure for high-dimensional nearest neighbor queries, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.369-380, May 11-15, 1997, Tucson, Arizona, United States
	23	King Ip Lin , H. V. Jagadish , Christos Faloutsos, The TV-tree: an index structure for high-dimensional data, The VLDB Journal — The International Journal on Very Large Data Bases, v.3 n.4, October 1994
	24	Nick Roussopoulos , Stephen Kelley , Frédéric Vincent, Nearest neighbor queries, Proceedings of the 1995 ACM SIGMOD international conference on Management of data, p.71-79, May 22-25, 1995, San Jose, California, United States
	25	Gerard Salton , Michael J. McGill, Introduction to Modern Information Retrieval, McGraw-Hill, Inc., New York, NY, 1986
	26	Hanan Samet, The design and analysis of spatial data structures, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
	27	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
	28	David A. White , Ramesh Jain, Similarity Indexing with the SS-tree, Proceedings of the Twelfth International Conference on Data Engineering, p.516-523, February 26-March 01, 1996

CITED BY 9

	Charu C. Aggarwal, Towards effective and interpretable data mining by visual interaction, ACM SIGKDD Explorations Newsletter, v.3 n.2, January 2002
	Charu C. Aggarwal, On the effects of dimensionality reduction on high dimensional similarity search, Proceedings of the twentieth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.256-266, May 2001, Santa Barbara, California, United States
	Guang-Ho Cha, Bitmap indexing method for complex similarity queries with relevance feedback, Proceedings of the 1st ACM international workshop on Multimedia databases, November 07-07, 2003, New Orleans, LA, USA
	Anthony K. H. Tung , Rui Zhang , Nick Koudas , Beng Chin Ooi, Similarity search: a matching based approach, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
	Charu C. Aggarwal, On the use of Human-Computer Interaction for Projected Nearest Neighbor Search, Data Mining and Knowledge Discovery, v.13 n.1, p.89-117, July 2006
	Tomáš Skopal, Unified framework for fast exact and approximate search in dissimilarity spaces, ACM Transactions on Database Systems (TODS), v.32 n.4, p.29-es, November 2007
	Wolfgang Müller , P. Oscar Boykin , Vwani P. Roychowdhury , Nima Sarshar, Comparison of image similarity queries in P2P systems, Computer Communications, v.31 n.2, p.375-386, February, 2008
	Shenghuo Zhu , Tao Li , Zhiyuan Chen , Dingding Wang , Yihong Gong, Dynamic active probing of helpdesk databases, Proceedings of the VLDB Endowment, v.1 n.1, August 2008
	Mykola Galushka , David Patterson, Intelligent index selection for case-based reasoning, Knowledge-Based Systems, v.19 n.8, p.625-638, December, 2006