High performance clustering based on the similarity join

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

High performance clustering based on the similarity join

Full text

Pdf (135 KB)

Source

Conference on Information and Knowledge Management archive
Proceedings of the ninth international conference on Information and knowledge management table of contents

McLean, Virginia, United States

Pages: 298 - 305

Year of Publication: 2000

ISBN:1-58113-320-0

Authors

Christian Böhm	Institute for Computer Science, University of Munich, Oettingenstr. 67, 80538 München, Germany
Bernhard Braunmüller	Institute for Computer Science, University of Munich, Oettingenstr. 67, 80538 München, Germany
Markus Breunig	Institute for Computer Science, University of Munich, Oettingenstr. 67, 80538 München, Germany
Hans-Peter Kriegel	Institute for Computer Science, University of Munich, Oettingenstr. 67, 80538 München, Germany

Sponsors

SIGMIS: ACM Special Interest Group on Management Information Systems
SIGIR: ACM Special Interest Group on Information Retrieval

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 7, Downloads (12 Months): 58, Citation Count: 9

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/354756.354832 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	Mihael Ankerst , Markus M. Breunig , Hans-Peter Kriegel , Jörg Sander, OPTICS: ordering points to identify the clustering structure, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.49-60, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
	2	Rakesh Agrawal , Johannes Gehrke , Dimitrios Gunopulos , Prabhakar Raghavan, Automatic subspace clustering of high dimensional data for data mining applications, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.94-105, June 01-04, 1998, Seattle, Washington, United States
	3	Rakesh Agrawal , Tomasz Imieliński , Arun Swami, Mining association rules between sets of items in large databases, Proceedings of the 1993 ACM SIGMOD international conference on Management of data, p.207-216, May 25-28, 1993, Washington, D.C., United States
	4	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
	5	Jochen Van den Bercken , Bernhard Seeger , Peter Widmayer, A Generic Approach to Bulk Loading Multidimensional Index Structures, Proceedings of the 23rd International Conference on Very Large Data Bases, p.406-415, August 25-29, 1997
	6	Stefan Berchtold , Christian Böhm , Hans-Peter Kriegel, Improving the Query Performance of High-Dimensional Index Structures by Bulk-Load Operations, Proceedings of the 6th International Conference on Extending Database Technology: Advances in Database Technology, p.216-230, March 23-27, 1998
	7	Markus M. Breunig , Hans-Peter Kriegel , Raymond T. Ng , Jörg Sander, LOF: identifying density-based local outliers, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.93-104, May 15-18, 2000, Dallas, Texas, United States
	8	Thomas Brinkhoff , Hans-Peter Kriegel , Bernhard Seeger, Efficient processing of spatial joins using R-trees, Proceedings of the 1993 ACM SIGMOD international conference on Management of data, p.237-246, May 25-28, 1993, Washington, D.C., United States
	9	Thomas Brinkhoff , Hans-Peter Kriegel , Bernhard Seeger, Parallel Processing of Spatial Joins Using R-trees, Proceedings of the Twelfth International Conference on Data Engineering, p.258-265, February 26-March 01, 1996
	10	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
	11	Ester M., Frommelt A., Kriegel H.-P., Sander J.: 'Algorithms for Characterization and Trend Detection in Spatial Data-bases', Proc. 4th Int. Conf. on Knowledge Discovery and Data Mining, New York, NY, 1998, pp. 44-50.
	12	Martin Ester , Hans-Peter Kriegel , Jörg Sander , Michael Wimmer , Xiaowei Xu, Incremental Clustering for Mining in a Data Warehousing Environment, Proceedings of the 24rd International Conference on Very Large Data Bases, p.323-333, August 24-27, 1998
	13	Ester M., Kriegel H.-P., Sander J., Xu X.: 'A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise', Proc. 2nd Int. Conf. on Knowledge Discovery and Data Mining, Portland, OR, AAAI Press, 1996, pp. 226-231.
	14	Christos Faloutsos , King-Ip Lin, FastMap: a fast algorithm for indexing, data-mining and visualization of traditional and multimedia datasets, Proceedings of the 1995 ACM SIGMOD international conference on Management of data, p.163-174, May 22-25, 1995, San Jose, California, United States
	15	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]
	16	Sudipto Guha , Rajeev Rastogi , Kyuseok Shim, CURE: an efficient clustering algorithm for large databases, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.73-84, June 01-04, 1998, Seattle, Washington, United States
	17	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
	18	Yun-Wu Huang , Ning Jing , Elke A. Rundensteiner, Spatial Joins Using R-trees: Breadth-First Traversal with Global Optimizations, Proceedings of the 23rd International Conference on Very Large Data Bases, p.396-405, August 25-29, 1997
	19	Hinneburg A., Keim D.A.: 'An Efficient Approach to Clustering in Large Multimedia Databases with Noise', Proc. 4th Int. Conf. on Knowledge Discovery & Data Mining, New York City, NY, 1998, pp. 58-65.
	20	Hattori K., Torii Y.: 'Effective algorithms for the nearest neighbor method in the clustering problem'. Pattern Recognition, 1993, Vol. 26, No. 5, pp. 741-746.
	21	Huang, Z.: 'A Fast Clustering Algorithm to Cluster Very Large Categorical Data Sets in Data Mining'. In Proc. SIGMOD Workshop on Research Issues on Data Mining and Knowledge Discovery, Tech. Report 97-07, UBC, Dept. of CS, 1997.
	22	H. V. Jagadish, A retrieval technique for similar shapes, Proceedings of the 1991 ACM SIGMOD international conference on Management of data, p.208-217, May 29-31, 1991, Denver, Colorado, United States
	23	Anil K. Jain , Richard C. Dubes, Algorithms for clustering data, Prentice-Hall, Inc., Upper Saddle River, NJ, 1988
	24	Keim D. A.: 'Visual Database Exploration Techniques', Proc. Tutorial Int. Conf. on Knowledge Discovery and Data Mining, Newport Beach, CA, 1997 (http://www.informatik.unihalle.de/~keim/PS/KDD97.pdf).
	25	Krzysztof Koperski , Jiawei Han, Discovery of Spatial Association Rules in Geographic Information Databases, Proceedings of the 4th International Symposium on Advances in Spatial Databases, p.47-66, August 06-09, 1995
	26	Edwin M. Knorr , Raymond T. Ng, Finding Aggregate Proximity Relationships and Commonalities in Spatial Data Mining, IEEE Transactions on Knowledge and Data Engineering, v.8 n.6, p.884-897, December 1996 [doi>10.1109/69.553156]
	27	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
	28	Kaufman L., Rousseeuw P. J.: 'Finding Groups in Data: An Introduction to Cluster Analysis', John Wiley & Sons, 1990.
	29	Nick Koudas , Kenneth C. Sevcik, Size separation spatial join, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.324-335, May 11-15, 1997, Tucson, Arizona, United States
	30	Nick Koudas , Kenneth C. Sevcik, High Dimensional Similarity Joins: Algorithms and Performance Evaluation, Proceedings of the Fourteenth International Conference on Data Engineering, p.466-475, February 23-27, 1998
	31	Hans-Peter Kriegel , Thomas Seidl, Approximation-Based Similarity Search for 3-D Surface Segments, Geoinformatica, v.2 n.2, p.113-147, June 1998 [doi>10.1023/A:1009760031965]
	32	Flip Korn , Nikolaos Sidiropoulos , Christos Faloutsos , Eliot Siegel , Zenon Protopapas, Fast Nearest Neighbor Search in Medical Image Databases, Proceedings of the 22th International Conference on Very Large Data Bases, p.215-226, September 03-06, 1996
	33	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
	34	Ming-Ling Lo , Chinya V. Ravishankar, Spatial joins using seeded trees, Proceedings of the 1994 ACM SIGMOD international conference on Management of data, p.209-220, May 24-27, 1994, Minneapolis, Minnesota, United States
	35	Ming-Ling Lo , Chinya V. Ravishankar, Spatial hash-joins, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.247-258, June 04-06, 1996, Montreal, Quebec, Canada
	36	MacQueen, J.: 'Some Methods for Classification and Analysis of Multivariate Observations', 5th Berkeley Symp. Math. Statist. Prob., Vol. 1, pp. 281-297.
	37	Thomas M. Mitchell, Machine Learning, McGraw-Hill Higher Education, 1997
	38	Murtagh F.: 'A Survey of Recent Advances in Hierarchical Clustering Algorithms', The Computer Journal Vol. 26, No. 4, 1983, pp.354-359.
	39	Raymond T. Ng , Jiawei Han, Efficient and Effective Clustering Methods for Spatial Data Mining, Proceedings of the 20th International Conference on Very Large Data Bases, p.144-155, September 12-15, 1994
	40	Jignesh M. Patel , David J. DeWitt, Partition based spatial-merge join, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.259-270, June 04-06, 1996, Montreal, Quebec, Canada
	41	Gregory Piateski , William Frawley, Knowledge Discovery in Databases, MIT Press, Cambridge, MA, 1991
	42	John A. Richards, Remote Sensing Digital Image Analysis: An Introduction, Springer-Verlag New York, Inc., Secaucus, NJ, 1994
	43	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]
	44	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
	45	Gholamhosein Sheikholeslami , Surojit Chatterjee , Aidong Zhang, WaveCluster: A Multi-Resolution Clustering Approach for Very Large Spatial Databases, Proceedings of the 24rd International Conference on Very Large Data Bases, p.428-439, August 24-27, 1998
	46	Sibson R.: 'SLINK: an optimally efficient algorithm for the single-link cluster method', The Computer Journal Vol. 16, No. 1, 1973, pp.30-34.
	47	Kyuseok Shim , Ramakrishnan Srikant , Rakesh Agrawal, High-Dimensional Similarity Joins, Proceedings of the Thirteenth International Conference on Data Engineering, p.301-311, April 07-11, 1997
	48	Ullman J.D.: 'Database and Knowledge-Base System', Vol. II,Compute Science Press, Rockville, MD, 1989.

CITED BY 9

	Jens-Peter Dittrich , Bernhard Seeger, GESS: a scalable similarity-join algorithm for mining large data sets in high dimensional spaces, Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining, p.47-56, August 26-29, 2001, San Francisco, California
	Fabrizio Angiulli , Clara Pizzuti, An approximate algorithm for top-k closest pairs join query in large high dimensional data, Data & Knowledge Engineering, v.53 n.3, p.263-281, June 2005
	Zhengwu Yang , Guoqiang Yang, A near-optimal similarity join algorithm and performance evaluation, Information Sciences—Informatics and Computer Science: An International Journal, v.167 n.1-4, p.87-108, 2 December 2004
	Stefan Brecheisen , Hans-Peter Kriegel , Martin Pfeifle, Multi-step density-based clustering, Knowledge and Information Systems, v.9 n.3, p.284-308, March 2006
	Roberto J. Bayardo , Yiming Ma , Ramakrishnan Srikant, Scaling up all pairs similarity search, Proceedings of the 16th international conference on World Wide Web, May 08-12, 2007, Banff, Alberta, Canada
	Jens-Peter Dittrich , Bernhard Seeger , David Scot Taylor , Peter Widmayer, Progressive merge join: a generic and non-blocking sort-based join algorithm, Proceedings of the 28th international conference on Very Large Data Bases, p.299-310, August 20-23, 2002, Hong Kong, China
	Alexandros Nanopoulos , Yannis Theodoridis , Yannis Manolopoulos, C2P: Clustering based on Closest Pairs, Proceedings of the 27th International Conference on Very Large Data Bases, p.331-340, September 11-14, 2001
	Edwin H. Jacox , Hanan Samet, Metric space similarity joins, ACM Transactions on Database Systems (TODS), v.33 n.2, p.1-38, June 2008
	Claudio Gennaro, A content-addressable network for similarity join in metric spaces, Proceedings of the 3rd international conference on Scalable information systems, June 04-06, 2008, Vico Equense, Italy