Detecting graph-based spatial outliers

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Detecting graph-based spatial outliers: algorithms and applications (a summary of results)

Full text

Pdf (590 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: 371 - 376

Year of Publication: 2001

ISBN:1-58113-391-X

Authors

Shashi Shekhar	University of Minnesota, Minneapolis, MN
Chang-Tien Lu	University of Minnesota, Minneapolis, MN
Pusheng Zhang	University of Minnesota, Minneapolis, MN

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): 14, Downloads (12 Months): 75, Citation Count: 16

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.502567 What is a DOI?

ABSTRACT

Identification of outliers can lead to the discovery of unexpected, interesting, and useful knowledge. Existing methods are designed for detecting spatial outliers in multidimensional geometric data sets, where a distance metric is available. In this paper, we focus on detecting spatial outliers in graph structured data sets. We define statistical tests, analyze the statistical foundation underlying our approach, design several fast algorithms to detect spatial outliers, and provide a cost model for outlier detection procedures. In addition, we provide experimental results from the application of our algorithms on a Minneapolis-St.Paul(Twin Cities) traffic dataset to show their effectiveness and usefulness.

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	V. Barnett and T. Lewis. Outliers in Statistical Data. John Wiley, New York, 3rd edition, 1994.
	3	Markus M. Breunig , Hans-Peter Kriegel , Raymond T. Ng , Jörg Sander, OPTICS-OF: Identifying Local Outliers, Proceedings of the Third European Conference on Principles of Data Mining and Knowledge Discovery, p.262-270, September 15-18, 1999
	4	Oliver Günther, The Design of the Cell Tree: An Object-Oriented Index Structure for Geometric Databases, Proceedings of the Fifth International Conference on Data Engineering, p.598-605, February 06-10, 1989
	5	D. Hawkins. Identification of Outliers. Chapman and Hail, 1980.
	6	R. A. Johnson , D. W. Wichern, Applied multivariate statistical analysis, Prentice-Hall, Inc., Upper Saddle River, NJ, 1988
	7	E. Knorr and R. Ng. A unified notion of outliers: Properties and computation. In Proc. of the International Conference on Knowledge Discovery and Data Mining, pages 219-222, 1997.
	8	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
	9	J. A. Orenstein , T. H. Merrett, A class of data structures for associative searching, Proceedings of the 3rd ACM SIGACT-SIGMOD symposium on Principles of database systems, April 02-04, 1984, Waterloo, Ontario, Canada [doi>10.1145/588011.588037]
	10	Franco P. Preparata , Michael I. Shamos, Computational geometry: an introduction, Springer-Verlag New York, Inc., New York, NY, 1985
	11	Sridhar Ramaswamy , Rajeev Rastogi , Kyuseok Shim, Efficient algorithms for mining outliers from large data sets, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.427-438, May 15-18, 2000, Dallas, Texas, United States
	12	Ida Ruts , Peter J. Rousseeuw, Computing depth contours of bivariate point clouds, Computational Statistics & Data Analysis, v.23 n.1, p.153-168, Nov. 15, 1996 [doi>10.1016/S0167-9473(96)00027-8]
	13	Shashi Shekhar , Duen-Ren Liu, CCAM: A Connectivity-Clustered Access Method for Networks and Network Computations, IEEE Transactions on Knowledge and Data Engineering, v.9 n.1, p.102-119, January 1997 [doi>10.1109/69.567054]
	14	D. Yu, G. Sheikholeslami, and A. Zhang. Findout: Finding outliers in very large datasets. In Department of Computer Science and Engineering State University of New York at Buffalo Buffalo, Technical report 99-03, http://www.cse.buffalo.edu/tech-reports/, 1999.

CITED BY 16

	Shashi Shekhar , Yan Huang , Judy Djugash , Changqing Zhou, Vector map compression: a clustering approach, Proceedings of the 10th ACM international symposium on Advances in geographic information systems, November 08-09, 2002, McLean, Virginia, USA
	Yan Huang , Hui Xiong , Shashi Shekhar , Jian Pei, Mining confident co-location rules without a support threshold, Proceedings of the 2003 ACM symposium on Applied computing, March 09-12, 2003, Melbourne, Florida
	Ian Davidson , Goutam Paul, Locating secret messages in images, Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, August 22-25, 2004, Seattle, WA, USA
	Victoria Hodge , Jim Austin, A Survey of Outlier Detection Methodologies, Artificial Intelligence Review, v.22 n.2, p.85-126, October 2004
	Vandana Pursnani Janeja , Vijayalakshmi Atluri, LS³: a <u>L</u>inear <u>S</u>emantic <u>S</u>can <u>S</u>tatistic technique for detecting anomalous windows, Proceedings of the 2005 ACM symposium on Applied computing, March 13-17, 2005, Santa Fe, New Mexico
	Tianming Hu , Sam Yuan Sung, A trimmed mean approach to finding spatial outliers, Intelligent Data Analysis, v.8 n.1, p.79-95, January 2004
	Aaron Ceglar , John F. Roddick , David M. W. Powers, CURIO: a fast outlier and outlier cluster detection algorithm for large datasets, Proceedings of the 2nd international workshop on Integrating artificial intelligence and data mining, p.39-47, December 01-01, 2007, Gold Coast, Australia
	Chang-Tien Lu , Yufeng Kou , Jiang Zhao , Li Chen, Detecting and tracking regional outliers in meteorological data, Information Sciences: an International Journal, v.177 n.7, p.1609-1632, April, 2007
	Jeffrey Xu Yu , Weining Qian , Hongjun Lu , Aoying Zhou, Finding centric local outliers in categorical/numerical spaces, Knowledge and Information Systems, v.9 n.3, p.309-338, March 2006
	Sanjay Chawla , Pei Sun, SLOM: a new measure for local spatial outliers, Knowledge and Information Systems, v.9 n.4, p.412-429, April 2006
	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
	Sajib Barua , Reda Alhajj, A parallel multi-scale region outlier mining algorithm for meteorological data, Proceedings of the 15th annual ACM international symposium on Advances in geographic information systems, November 07-09, 2007, Seattle, Washington
	Betsy George , James M. Kang , Shashi Shekhar, Spatio-Temporal Sensor Graphs (STSG): A data model for the discovery of spatio-temporal patterns, Intelligent Data Analysis, v.13 n.3, p.457-475, August 2009
	Vandana P. Janeja , Vijayalakshmi Atluri, Spatial outlier detection in heterogeneous neighborhoods, Intelligent Data Analysis, v.13 n.1, p.85-107, January 2009
	Varun Chandola , Arindam Banerjee , Vipin Kumar, Anomaly detection: A survey, ACM Computing Surveys (CSUR), v.41 n.3, p.1-58, July 2009
	Malik Agyemang , Ken Barker , Rada Alhajj, A comprehensive survey of numeric and symbolic outlier mining techniques, Intelligent Data Analysis, v.10 n.6, p.521-538, December 2006