Abstract
An important problem in database and data mining systems is the detection of outlying points. It is often the case that data observations exhibiting atypical properties are of more interest than those fitting common patterns. While anomaly and outlier detection have received considerable attention from the statistics community, these approaches are primarily focused on analysis of data sets containing relatively few and univariate observations. Recently, valuable approaches have been proposed to facilitate multidimensional analysis for larger data sets. Unfortunately, these approaches are often expensive and require numerous comparisons between each point and the remainder of the data.
We propose an approach using histograms for outlier detection. Sparse regions of the data are recognised and used for identifying points that are likely to be outliers. An extensive experimental evaluation demonstrates the efficiency of our approach under a number of circumstances with varying parameters on real world and synthetic data sets.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Acharya, S., Poosala, V., Ramaswamy, S.: Selectivity estimation in spatial databases. In: SIGMOD, pp. 13–24. ACM Press, New York (1999)
Barnett, V., Lewis, T.: Outliers in statistical data. John Wiley, Chichester (1994)
Bay, S.D., Kibler, D., Pazzani, M.J., Smyth, P.: The UCI KDD archive of large data sets for data mining research and experimentation. Information Processing Society of Japan Magazine 42(5), 462–466 (2001)
Bay, S.D., Schwabacher, M.: Mining distance-based outliers in near linear time with randomization and a simple pruning rule. In: Getoor, L., Senator, T.E., Domingos, P., Faloutsos, C. (eds.) KDD, pp. 29–38. ACM Press, New York (2003)
Breunig, M.M., Kriegel, H.-P., Ng, R.T., Sander, J.: OPTICS-OF: Identifying Local Outliers. In: Żytkow, J.M., Rauch, J. (eds.) PKDD 1999. LNCS (LNAI), vol. 1704, pp. 262–270. Springer, Heidelberg (1999)
Breunig, M.M., Kriegel, H.-P., Ng, R.T., Sander, J.: Lof: Identifying density-based local outliers. In: SIGMOD, pp. 93–104. ACM Press, New York (2000)
Deshpande, A., Garofalakis, M., Rastogi, R.: Independence is good: dependency-based histogram synopses for high-dimensional data. In: SIGMOD, Santa Barbara, California, United States, pp. 199–210. ACM Press, New York (2001), doi:10.1145/375663.375685
Gunopulos, D., Kollios, G., Tsotras, V.J., Domeniconi, C.: Approximating multi-dimensional aggregate range queries over real attributes. In: SIGMOD, Dallas, Texas, United States, pp. 463–474. ACM Press, New York (2000), doi:10.1145/342009.335448
Hawkins, D.: Identification of outliers. Chapman and Hall, Boca Raton (1980)
Knorr, E.M., Ng, R.T.: A unified approach for mining outliers. In: CASCON, p. 11. IBM (1997)
Knorr, E.M., Ng, R.T.: Algorithms for mining distance-based outliers in large datasets. In: VLDB, pp. 392–403. Morgan Kaufmann, San Francisco (1998)
Knorr, E.M., Ng, R.T.: Finding intensional knowledge of distance-based outliers. In: VLDB, pp. 211–222. Morgan Kaufmann, San Francisco (1999)
Knorr, E.M., Ng, R.T., Tucakov, V.: Distance-based outliers: Algorithms and applications. VLDB J. 8(3-4), 237–253 (2000)
Kollios, G., Gunopulos, D., Koudas, N., Berchtold, S.: Efficient biased sampling for approximate clustering and outlier detection in large datasets (2003)
Papadimitriou, S., Kitagawa, H., Gibbons, P.B., Faloutsos, C.: Loci: Fast outlier detection using the local correlation integral. In: ICDE, pp. 315–326 (2003)
Ramaswamy, S., Rastogi, R., Shim, K.: Efficient algorithms for mining outliers from large data sets. In: SIGMOD, Dallas, Texas, United States, pp. 427–438. ACM Press, New York (2000), doi:10.1145/342009.335437
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2007 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Gebski, M., Wong, R.K. (2007). An Efficient Histogram Method for Outlier Detection. In: Kotagiri, R., Krishna, P.R., Mohania, M., Nantajeewarawat, E. (eds) Advances in Databases: Concepts, Systems and Applications. DASFAA 2007. Lecture Notes in Computer Science, vol 4443. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-71703-4_17
Download citation
DOI: https://doi.org/10.1007/978-3-540-71703-4_17
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-71702-7
Online ISBN: 978-3-540-71703-4
eBook Packages: Computer ScienceComputer Science (R0)