The DOI matches its Crossref record; 48 of the 48 references it cites were found in a registry or an index.
The Concentration of Fractional Distances
Abstract
Nearest neighbor search and many other numerical data analysis tools most often rely on the use of the euclidean distance. When data are high dimensional, however, the euclidean distances seem to concentrate; all distances between pairs of data elements seem to be very similar. Therefore, the relevance of the euclidean distance has been questioned in the past, and fractional norms (Minkowski-like norms with an exponent less than one) were introduced to fight the concentration phenomenon. This paper justifies the use of alternative distances to fight concentration by showing that the concentration is indeed an intrinsic property of the distances and not an artifact from a finite sample. Furthermore, an estimation of the concentration as a function of the exponent of the distance and of the distribution of the data is given. It leads to the conclusion that, contrary to what is generally admitted, fractional norms are not always less concentrated than the euclidean norm; a counterexample is given to prove this claim. Theoretical arguments are presented, which show that the concentration phenomenon can appear for real data that do not match the hypotheses of the theorems, in particular, the assumption of independent and identically distributed variables. Finally, some insights about how to choose an optimal metric are given.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
A Global Geometric Framework for Nonlinear Dimensionality Reduction
Tenenbaum, J. B., Silva, V. D., & Langford, J. C. (2000) · Science · doi:10.1126/science.290.5500.2319 · Cited by 13,585
Jain, A. K., Murty, M. N., & Flynn, P. J. (1999) · ACM Computing Surveys · doi:10.1145/331499.331504 · Cited by 13,199
Introduction to Statistical Pattern Recognition
(1990) · Elsevier eBooks · doi:10.1016/c2009-0-27872-x · Cited by 11,031
UCI Repository of machine learning databases
Blake, C. L. (1998) · Medical Entomology and Zoology · Cited by 10,582
Approximate nearest neighbors: towards removing the curse of dimensionality
Indyk, P., & Motwani, R. (1998) · Proceedings of the thirtieth annual ACM symposium on Theory of computing - STOC '98 · doi:10.1145/276698.276876 · Cited by 4,188
Introduction to statistical pattern recognition (2nd ed.)
Fukunaga, K. (1990) · Academic Press Professional, Inc. eBooks · Cited by 3,797
Adaptive Control Processes: A Guided Tour
Bellman, R. E. (1961) · doi:10.1515/9781400874668 · Cited by 2,802
When Is ''Nearest Neighbor'' Meaningful?
Beyer, K., Goldstein, J., Ramakrishnan, R., & Shaft, U. (1999) · Lecture Notes in Computer Science · doi:10.1007/3-540-49257-7_15 · Cited by 2,403
Adaptive Control Processes: A Guided Tour.
Page, E. S., & Bellman, R. (1962) · Journal of the Royal Statistical Society. Series A (General) · doi:10.2307/2343225 · Cited by 2,185
On the Surprising Behavior of Distance Metrics in High Dimensional Space
Aggarwal, C. C., Hinneburg, A., & Keim, D. A. (2001) · Lecture Notes in Computer Science · doi:10.1007/3-540-44503-x_27 · Cited by 2,083
Relevance feedback: a power tool for interactive content-based image retrieval
Rui, Y., Huang, T. S., Ortega, M., & Mehrotra, S. (1998) · IEEE Transactions on Circuits and Systems for Video Technology · doi:10.1109/76.718510 · Cited by 1,764
Improving retrieval performance by relevance feedback
Salton, G., & Buckley, C. (1990) · Journal of the American Society for Information Science · doi:10.1002/(sici)1097-4571(199006)41:4<288::aid-asi8>3.0.co;2-h · Cited by 1,495
Chávez, E., Navarro, G., Baeza-Yates, R., & Marroquín, J. L. (2001) · ACM Computing Surveys · doi:10.1145/502807.502808 · Cited by 1,246
Radial basis functions for multivariable interpolation: a review
Powell, M. J. D. (1987) · Clarendon Press eBooks · Cited by 1,197
Berchtold, S., Keim, D. A., & Kriegel, H.-P. (2002) · Readings in Multimedia Computing and Networking · doi:10.1016/b978-155860651-7/50124-8 · Cited by 1,118
Böhm, C., Berchtold, S., & Keim, D. A. (2001) · ACM Computing Surveys · doi:10.1145/502807.502809 · Cited by 827
The SR-tree: an index structure for high-dimensional nearest neighbor queries
Katayama, N., & Satoh, S. (1997) · Proceedings of the 1997 ACM SIGMOD international conference on Management of data - SIGMOD '97 · doi:10.1145/253260.253347 · Cited by 817
Using the triangle inequality to accelerate k-means
Elkan, C. (2003) · Cited by 705
Near Neighbor Search in Large Metric Spaces
Brin, S. (1995) · Cited by 556
What Is the Nearest Neighbor in High Dimensional Spaces
Hinneburg, A., Aggarwal, C. C., & Keim, D. A. (2000) · KOPS (University of Konstanz) · Cited by 505
The TV-tree: An index structure for high-dimensional data
Lin, K.-I., Jagadish, H. V., & Faloutsos, C. (1994) · The VLDB Journal · doi:10.1007/bf01231606 · Cited by 494
The X Tree: An Index Structure for High Dimensional Data
Berchtold, S., Keim, D. A., & Kriegel, H.-P. (1996) · KOPS (University of Konstanz) · Cited by 414
An Investigation of Practical Approximate Nearest Neighbor Algorithms
Liu, T., Moore, A., Yang, K., & Gray, A. (2004) · Cited by 375
A cost model for nearest neighbor search in high-dimensional data space
Berchtold, S., Böhm, C., Keim, D. A., & Kriegel, H.-P. (1997) · Proceedings of the sixteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems · doi:10.1145/263661.263671 · Cited by 373
Independent quantization: an index compression technique for high-dimensional data spaces
Berchtold, S., Bohm, C., Jagadish, H. V., Kriegel, H.-P., & Sander, J. (2002) · Proceedings of 16th International Conference on Data Engineering (Cat. No.00CB37073) · doi:10.1109/icde.2000.839456 · Cited by 291
Stefánsson, A., Končar, N., & Jones, A. J. (1997) · Neural Computing & Applications · doi:10.1007/bf01413858 · Cited by 254
Local Dimensionality Reduction: A New Approach to Indexing High Dimensional Spaces
Chakrabarti, K., & Mehrotra, S. (2000) · Cited by 230
On the "dimensionality curse" and the "self-similarity blessing"
Korn, F., Pagel, B.-U., & Faloutsos, C. (2001) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/69.908983 · Cited by 220
Cheney, E. W. (1986) · Proceedings of Symposia in Applied Mathematics · doi:10.1090/psapm/036/864366 · Cited by 209
The hybrid tree: an index structure for high dimensional feature spaces
Chakrabarti, K., & Mehrotra, S. (1999) · IEEE International Conference on Data Engineering (ICDE) · doi:10.1109/icde.1999.754960 · Cited by 207
Nonlinear projection with curvilinear distances: Isomap versus curvilinear distance analysis
Lee, J. A., Lendasse, A., & Verleysen, M. (2004) · Neurocomputing · doi:10.1016/j.neucom.2004.01.007 · Cited by 173
Self-citationFast parallel similarity search in multimedia databases
Berchtold, S., Böhm, C., Braunmüller, B., Keim, D. A., & Kriegel, H.-P. (1997) · Proceedings of the 1997 ACM SIGMOD international conference on Management of data - SIGMOD '97 · doi:10.1145/253260.253263 · Cited by 168
Functional Classification in Hilbert Spaces
Gérard Biau, A., Bunea, F., & Wegkamp, M. H. (2005) · IEEE Transactions on Information Theory · doi:10.1109/tit.2005.847705 · Cited by 141
Peer-to-peer spatial queries in sensor networks
Demirbaş, M., & Ferhatosmanoğlu, H. (2004) · International Conference on Peer-to-Peer Computing · doi:10.1109/ptp.2003.1231501 · Cited by 139
Ciaccia, P., & Patella, M. (2002) · IEEE International Conference on Data Engineering (ICDE) · doi:10.1109/icde.2000.839417 · Cited by 138
Re-designing distance functions and distance-based applications for high dimensional data
Aggarwal, C. C. (2001) · ACM SIGMOD Record · doi:10.1145/373626.373638 · Cited by 115
Density-based indexing for approximate nearest-neighbor queries
Bennett, K. P., Fayyad, U. M., & Geiger, D. (1999) · ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD) · doi:10.1145/312129.312236 · Cited by 97
Compressing Large Boolean Matrices Using Reordering Techniques
Johnson, D. S., Krishnan, S. M., Chhugani, J., Kumar, S., & Venkatasubramanian, S. (2004) · Elsevier eBooks · doi:10.1016/b978-012088469-8.50005-x · Cited by 79
Analysis of predictive spatio-temporal queries
Tao, Y., Sun, J., & Dimitris Papadias, C. (2003) · ACM Transactions on Database Systems · doi:10.1145/958942.958943 · Cited by 68
Tuncel, E., Ferhatosmanoğlu, H., & Rose, K. H. (2002) · ACM International Conference on Multimedia (ACM MM) · doi:10.1145/641007.641117 · Cited by 66
Fractional Distance Measures for Content-Based Image Retrieval
Howarth, P. H., & Rüger, S. (2005) · Lecture notes in computer science · doi:10.1007/978-3-540-31865-1_32 · Cited by 48
An adaptive and efficient dimensionality reduction algorithm for high-dimensional indexing
Jin, H., Ooi, B. C., Shen, H. T., Yu, C., & Zhou, A. Y. (2004) · IEEE International Conference on Data Engineering (ICDE) · doi:10.1109/icde.2003.1260784 · Cited by 47
Value and Relation Display for Interactive Exploration of High Dimensional Datasets
Yang, J., Patro, A., Huang, S., Mehta, N., Ward, M. O., & Rundensteiner, E. A. (2004) · doi:10.1109/infovis.2004.71 · Cited by 47
Katayama, N., & Satoh, S. (2002) · IEEE International Conference on Data Engineering (ICDE) · doi:10.1109/icde.2001.914863 · Cited by 38
Value and Relation Display for Interactive Exploration of High Dimensional Datasets
Yang, J., Patro, A., Huang, S., Mehta, N., Ward, M. O., & Rundensteiner, E. A. (2005) · IEEE Symposium on Information Visualization · doi:10.1109/infvis.2004.71 · Cited by 30
Similarity search in sets and categorical data using the signature tree
Mamoulis, N., Cheung, D. W.-L., & Lian, W. (2004) · IEEE International Conference on Data Engineering (ICDE) · doi:10.1109/icde.2003.1260783 · Cited by 29
Unsupervised learning with normalised data and non-Euclidean norms
Doherty, K. A. J., Adams, R. G., & Davey, N. (2005) · Applied Soft Computing · doi:10.1016/j.asoc.2005.05.005 · Cited by 28
Non-Euclidean Norms and Data Normalisation
Doherty, K. A. J., Adams, R., & Davey, N. (2004) · University of Hertfordshire Research Archive (University of Hertfordshire) · Cited by 23
Cited by
A survey on unsupervised outlier detection in high‐dimensional numerical data
Zimek, A., Schubert, E., & Kriegel, H. (2012) · Statistical Analysis and Data Mining The ASA Data Science Journal · doi:10.1002/sam.11161 · Cited by 864
A comprehensive survey of anomaly detection techniques for high dimensional big data
Thudumu, S., Branch, P., Jin, J., & Singh, J. (2020) · Journal of Big Data · doi:10.1186/s40537-020-00320-x · Cited by 425
Minkowski metric, feature weighting and anomalous cluster initializing in K-Means clustering
Cordeiro de Amorim, R., & Mirkin, B. (2012) · Pattern Recognition · doi:10.1016/j.patcog.2011.08.012 · Cited by 328
Can Shared-Neighbor Distances Defeat the Curse of Dimensionality?
Houle, M. E., Kriegel, H.-P., Kröger, P., Schubert, E., & Zimek, A. (2010) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-13818-8_34 · Cited by 268
The Role of Hubness in Clustering High-Dimensional Data
Tomasev, N., Radovanovic, M., Mladenic, D., & Ivanovic, M. (2014) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2013.25 · Cited by 142
Metadata
- Authors
- Francois, D., Wertz, V., & Verleysen, M.
- Venue
- IEEE Transactions on Knowledge and Data Engineering
- Published
- 2007-07
- Volume
- 19
- Issue
- 7
- Pages
- 873-886
- ISSN
- 1041-4347 (ISSN-L)
- OpenAlex
- W2168532736
- Cited by
- 308
- References
- 48
- FWCI
- 15.76
- Type
- journal article
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.