DOLPHIN: An efficient algorithm for mining distance-based outliers in very large datasets

ABSTRACT

In this work a novel distance-based outlier detection algorithm, named DOLPHIN, working on disk-resident datasets and whose I/O cost corresponds to the cost of sequentially reading the input dataset file twice, is presented.

It is both theoretically and empirically shown that the main memory usage of DOLPHIN amounts to a small fraction of the dataset and that DOLPHIN has linear time performance with respect to the dataset size. DOLPHIN gains efficiency by naturally merging together in a unified schema three strategies, namely the selection policy of objects to be maintained in main memory, usage of pruning rules, and similarity search techniques. Importantly, similarity search is accomplished by the algorithm without the need of preliminarily indexing the whole dataset, as other methods do.

The algorithm is simple to implement and it can be used with any type of data, belonging to either metric or nonmetric spaces. Moreover, a modification to the basic method allows DOLPHIN to deal with the scenario in which the available buffer of main memory is smaller than its standard requirements. DOLPHIN has been compared with state-of-the-art distance-based outlier detection algorithms, showing that it is much more efficient.

REFERENCES

• 1: Charu C. Aggarwal , Philip S. Yu, Outlier detection for high dimensional data, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.37-46, May 21-24, 2001, Santa Barbara, California, United States
• 2: Fabrizio Angiulli , Fabio Fassetti, Very efficient mining of distance-based outliers, Proceedings of the sixteenth ACM conference on Conference on information and knowledge management, November 06-10, 2007, Lisbon, Portugal [doi>10.1145/1321440.1321550]
• 3: Fabrizio Angiulli , Clara Pizzuti, Fast Outlier Detection in High Dimensional Spaces, Proceedings of the 6th European Conference on Principles of Data Mining and Knowledge Discovery, p.15-26, August 19-23, 2002
• 4: Fabrizio Angiulli , Clara Pizzuti, Outlier Mining in Large High-Dimensional Data Sets, IEEE Transactions on Knowledge and Data Engineering, v.17 n.2, p.203-215, February 2005 [doi>10.1109/TKDE.2005.31]
• 5: Arning, A., Aggarwal, C., and Raghavan, P. 1996. A linear method for deviation detection in large databases. In Proceedings of the International Conference on Knowledge Discovery and Data Mining (KDD'96), 164--169.
• 6: Barnett, V. and Lewis, T. 1994. Outliers in Statistical Data. John Wiley & Sons.
• 7: Stephen D. Bay , Mark Schwabacher, Mining distance-based outliers in near linear time with randomization and a simple pruning rule, Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2003, Washington, D.C. [doi>10.1145/956750.956758]
• 8: 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
• 9: Jon Louis Bentley, Multidimensional binary search trees used for associative searching, Communications of the ACM, v.18 n.9, p.509-517, Sept. 1975 [doi>10.1145/361002.361007]
• 10: 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
• 11: 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 [doi>10.1145/502807.502809]
• 12: 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
• 13: Edgar Chávez , Gonzalo Navarro , Ricardo Baeza-Yates , José Luis Marroquín, Searching in metric spaces, ACM Computing Surveys (CSUR), v.33 n.3, p.273-321, September 2001 [doi>10.1145/502807.502808]
• 14: Paolo Ciaccia , Marco Patella , Pavel Zezula, M-tree: An Efficient Access Method for Similarity Search in Metric Spaces, Proceedings of the 23rd International Conference on Very Large Data Bases, p.426-435, August 25-29, 1997
• 15: Davies, L. and Gather, U. 1989. The identification of multiple outliers. Tech. rep. 89/1, Department of Statistics, University of Dortmund.
• 16: Davies, L. and Gather, U. 1993. The identification of multiple outliers. J. Amer. Statist. Assoc. 88, 782--792.
• 17: Eskin, E., Arnold, A., Prerau, M., Portnoy, L., and Stolfo, S. 2002. A geometric framework for unsupervised anomaly detection: Detecting intrusions in unlabeled data. In Applications of Data Mining in Computer Security. Kluwer.
• 18: Ghoting, A., Parthasarathy, S., and Otey, M. 2006. Fast mining of distance-based outliers in high-dimensional datasets. In Proceedings of the SIAM International Conference on Data Mining (SDM'06).
• 19: Hawkins, D. 1980. Identification of Outliers. Monographs on Applied Probability and Statistics. Chapman & Hall.
• 20: Wen Jin , Anthony K. H. Tung , Jiawei Han, Mining top-n local outliers in large databases, Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining, p.293-298, August 26-29, 2001, San Francisco, California [doi>10.1145/502512.502554]
• 21: Edwin M. Knorr , Raymond T. Ng, A unified approach for mining outliers, Proceedings of the 1997 conference of the Centre for Advanced Studies on Collaborative research, p.11, November 10-13, 1997, Toronto, Ontario, Canada
• 22: 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
• 23: Edwin M. Knorr , Raymond T. Ng, Finding Intensional Knowledge of Distance-Based Outliers, Proceedings of the 25th International Conference on Very Large Data Bases, p.211-222, September 07-10, 1999
• 24: 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 [doi>10.1007/s007780050006]
• 25: Lazarevic, A., Ertöz, L., Kumar, V., Ozgur, A., and Srivastava, J. 2003. A comparative study of anomaly detection schemes in network intrusion detection. In Proceedings of the SIAM International Conference on Data Mining.
• 26: Papadimitriou, S., Kitagawa, H., Gibbons, P., and Faloutsos, C. 2003. Loci: Fast outlier detection using the local correlation integral. In Proceedings of the International Conference on Data Enginnering (ICDE), 315--326.
• 27: 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
• 28: Rider, P. 1962. The negative binomial distribution and the incomplete beta function. The Amer. Math. Monthly 69, 4, 302--304.
• 29: E V Ruiz, An algorithm for finding nearest neighbours in (approximately) constant average time, Pattern Recognition Letters, v.4 n.3, p.145-157, July 1986 [doi>10.1016/0167-8655(86)90013-9]
• 30: Hanan Samet, Foundations of Multidimensional and Metric Data Structures (The Morgan Kaufmann Series in Computer Graphics and Geometric Modeling), Morgan Kaufmann Publishers Inc., San Francisco, CA, 2005
• 31: Schultze, V. and Pawlitschko, J. 2002. The identification of outliers in exponential samples. Statistica Neerlandica 56, 1, 41--57.
• 32: Yufei Tao , Xiaokui Xiao , Shuigeng Zhou, Mining distance-based outliers from large databases in any metric space, Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, August 20-23, 2006, Philadelphia, PA, USA [doi>10.1145/1150402.1150447]
• 33: Uhlmann, J. K. 1991. Satisfying general proximity/similarity queries with metric trees. Inf. Process. Lett. 40, 4, 175--179.
• 34: Watanabe, O. 2000. Simple sampling techniques for discovery science. TIEICE: IEICE Trans. Commun./Electron./Inf. Syst.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval

General Terms:
Algorithms, Performance

Keywords:
Data mining, distance-based outliers, outlier detection