| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 430577 | Journal of Discrete Algorithms | 2012 | 17 Pages |
Abstract
Degrading performance of indexing schemes for exact similarity search in high dimensions has long since been linked to histograms of distributions of distances and other 1-Lipschitz functions getting concentrated. We discuss this observation in the framework of the phenomenon of concentration of measure on the structures of high dimension and the Vapnik–Chervonenkis theory of statistical learning.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Vladimir Pestov,