Clustering spatial data using random walks

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Clustering spatial data using random walks

Full text

Pdf (556 KB)

Source

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

San Francisco, California

Pages: 281 - 286

Year of Publication: 2001

ISBN:1-58113-391-X

Authors

David Harel	The Weizmann Institute of Science, Rehovot, Israel
Yehuda Koren	The Weizmann Institute of Science, Rehovot, Israel

Sponsors

SIGMOD: ACM Special Interest Group on Management of Data
AAAI : American Association for Artificial Intelligence

Publisher

ACM New York, NY, USA

Bibliometrics

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

Additional Information:

abstract 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/502512.502552 What is a DOI?

ABSTRACT

Discovering significant patterns that exist implicitly in huge spatial databases is an important computational task. A common approach to this problem is to use cluster analysis. We propose a novel approach to clustering, based on the deterministic analysis of random walks on a weighted graph generated from the data. Our approach can decompose the data into arbitrarily shaped clusters of different sizes and densities, overcoming noise and outliers that may blur the natural decomposition of the data. The method requires only O(n log n) time, and one of its variants needs only constant space.

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	Matthew T. Dickerson , David Eppstein, Algorithms for proximity problems in higher dimensions, Computational Geometry: Theory and Applications, v.5 n.5, p.277-291, Jan. 1996 [doi>10.1016/0925-7721(95)00009-7]
	2	V. Estivill-Castro and I. Lee,"AUTOCLUST: Automatic Clustering via Boundary Extraction for Mining Massive Point- Data Sets", 5th International Conference on Geocomputation, GeoComputation CD-ROM: GC049, ISBN 0-9533477-2-9.
	3	Y. Gdalyahu, D. Weinshall and M. Werman, "Stochastic Image Segmentation by Typical Cuts", Proceedings IEEE Conference on Computer Vision and Pattern Recognition, 1999, pp. 588-601.
	4	Y. Koren , D. Harel, Clustering Spatial Data Using Random Walks,, Weizmann Science Press of Israel, Jerusalem, Israel, 2001
	5	Anil K. Jain , Richard C. Dubes, Algorithms for clustering data, Prentice-Hall, Inc., Upper Saddle River, NJ, 1988
	6	George Karypis , Eui-Hong (Sam) Han , Vipin Kumar, Chameleon: Hierarchical Clustering Using Dynamic Modeling, Computer, v.32 n.8, p.68-75, August 1999 [doi>10.1109/2.781637]
	7	X. Xu , M. Ester, H.P. Kriegel and J. Sander, "Clustering and Knowledge Discovery in Spatial Databases", Vistas in Astronomy, 41 (1997), 397-403.

CITED BY 12

	Diansheng Guo , Donna Peuquet , Mark Gahegan, Opening the black box: interactive hierarchical clustering for multivariate spatial patterns, Proceedings of the 10th ACM international symposium on Advances in geographic information systems, November 08-09, 2002, McLean, Virginia, USA
	Jinwook Seo , Ben Shneiderman, Interactively Exploring Hierarchical Clustering Results, Computer, v.35 n.7, p.80-86, July 2002
	Diansheng Guo , Donna J. Peuquet , Mark Gahegan, ICEAGE: Interactive Clustering and Exploration of Large and High-Dimensional Geodata, Geoinformatica, v.7 n.3, p.229-253, September 2003
	Yu Qian , Kang Zhang, A customizable hybrid approach to data clustering, Proceedings of the 2003 ACM symposium on Applied computing, March 09-12, 2003, Melbourne, Florida
	Yu Qian , Kang Zhang, The role of visualization in effective data cleaning, Proceedings of the 2005 ACM symposium on Applied computing, March 13-17, 2005, Santa Fe, New Mexico
	Yu Qian , Kang Zhang, GraphZip: a fast and automatic compression method for spatial data clustering, Proceedings of the 2004 ACM symposium on Applied computing, March 14-17, 2004, Nicosia, Cyprus
	Yu Qian , Kang Zhang, Discovering spatial patterns accurately with effective noise removal, Proceedings of the 9th ACM SIGMOD workshop on Research issues in data mining and knowledge discovery, June 13, 2004, Paris, France
	Güneş Erkan, Language model-based document clustering using random walks, Proceedings of the main conference on Human Language Technology Conference of the North American Chapter of the Association of Computational Linguistics, p.479-486, June 04-09, 2006, New York, New York
	Yu Qian , Fang Qiu , Jie Chang , Kang Zhang, Visualization-informed noise elimination and its application in processing high-spatial-resolution remote sensing imagery, Computers & Geosciences, v.34 n.1, p.35-52, January, 2008
	Huajing Li , Zaiqing Nie , Wang-Chien Lee , Lee Giles , Ji-Rong Wen, Scalable community discovery on textual data with relations, Proceeding of the 17th ACM conference on Information and knowledge management, October 26-30, 2008, Napa Valley, California, USA
	Pasi Franti , Olli Virmajoki , Ville Hautamaki, Fast Agglomerative Clustering Using a k-Nearest Neighbor Graph, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.28 n.11, p.1875-1881, November 2006
	Yunjun Gao , Baihua Zheng , Gencai Chen , Qing Li, On efficient mutual nearest neighbor query processing in spatial databases, Data & Knowledge Engineering, v.68 n.8, p.705-727, August, 2009