Lehrstuhl  |  Institut  |  Fakultät  |  LMU


Can Shared-Neighbor Distances Defeat the Curse of Dimensionality?

22nd International Conference on Scientific and Statistical Database Management (SSDBM 2010)

Michael E. Houle1, Hans-Peter Kriegel2, Peer Kröger2, Erich Schubert2, Arthur Zimek2
1 National Institute of Informatics

2-1-2 Hitotsubashi, Chiyoda-ku, Tokyo 101-8430, Japan

2Ludwig-Maximilians-Universität München
Oettingenstr. 67, 80538 München, Germany


[ EE (springerlink) | preprint (pdf) | slides (pdf) ]

Supplementary Material

  1. Experiments for the Beyer curse factor
  2. Distance histograms
  3. Centrality vs. Ranking quality
  4. Ranking quality with increasing dimensionality
  5. Ranking quality with increasing SNN size
  6. Data sets

Relationship to figures in the publication:

Figure 1 is from section 1 (Beyer curse factor).

Figures 2 and 3 are from section 5 (Ranking Candles for SNN)

Figures 4 and 5 are from section 2 (Distance histograms).

Figure 6 is from section 5 (Ranking Candles for SNN)

Follow-up Study

This study was extended to time series data and time series specific distance measures, see:

Thomas Bernecker, Michael E. Houle, Hans-Peter Kriegel, Peer Kröger, Matthias Renz, Erich Schubert, Arthur Zimek:
Quality of Similarity Rankings in Time Series
Proc. 12th International Symposium on Spatial and Temporal Databases (SSTD), Minneapolis, MN, 2011.
[EE (springerlink)]