On the Surprising Behavior of Distance Metrics in High Dimensional Spaces

By Charu C. Aggarwal, Alexander Hinneburg, Daniel A. Keim. 2001

2,357 citations recorded by the source corpus.

In recent years, the effect of the curse of high dimensionality has been studied in great detail on several problems such as clustering, nearest neighbor search, and indexing. In high dimensional space the data becomes sparse, and traditional indexing and algorithmic techniques fail from a efficiency and/or effectiveness perspective. Recent research results show that in high dimensional space, the concept of proximity, distance or nearest neighbor may not even be qualitatively meaningful. In this paper, we view the dimensionality curse from the point of view of the distance metrics which are used to measure the similarity between objects. We specifically examine the behavior of the commonly used L k norm and show that the problem of meaningfulness in high dimensionality is sensitive to the value of k. For example, this means that the Manhattan distance metric (L 1 norm) is consistently more preferable than the Euclidean distance metric (L 2 norm) for high dimensional data mining applications. Using the intuition derived from our analysis, we introduce and examine a natural extension of the L k norm to fractional distance metrics. We show that the fractional distance metric provides more meaningful results both from the theoretical and empirical perspective. The results show that fractional distance metrics can significantly improve the effectiveness of standard clustering algorithms such as the k-means algorithm.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition, Statistical Learning Theory, Algorithms & Complexity, Signal Processing

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

  1. Percy Liang
  2. Ruslan Salakhutdinov
  3. Charu C. Aggarwal
  4. Eric P. Xing
  5. Yoshua Bengio
  6. Mohit Bansal
  7. Noah A. Smith
  8. Jianfeng Gao

In Computer Vision and Pattern Recognition

  1. Luc Van Gool
  2. Yi Yang
  3. Dacheng Tao
  4. Cordelia Schmid
  5. Trevor Darrell
  6. Xiaogang Wang
  7. Andrew Zisserman
  8. Jitendra Malik

In Statistical Learning Theory

  1. Andrew Gordon Wilson
  2. Ruslan Salakhutdinov
  3. Eric P. Xing
  4. Zhiting Hu
  5. Christian Beecks
  6. Han Lin Shang
  7. Anil Jayanti Aswani
  8. T. Chari

In Algorithms & Complexity

  1. Christian Beecks
  2. Han Lin Shang
  3. Anil Jayanti Aswani
  4. T. Chari
  5. Lior S. Pachter
  6. Matt Olfat
  7. Michel Verleysen
  8. Damien François

In Signal Processing

  1. Charu C. Aggarwal
  2. Renato Cordeiro de Amorim
  3. Arthur Zimek
  4. Pavel Berkhin
  5. Boris G. Mirkin
  6. Hans-Peter Kriegel
  7. Lalit P. Jain
  8. Elena A. Allen

Citations in the corpus