Probabilistic proximity search: Fighting the curse of dimensionality in metric spaces.
Proximity searches become very difficult on ``high dimensional metric spaces, that is, those whose histogram of distances has a large mean and/or a small variance. This so-called ``curse of dimensionality, well known in vector spaces, is also observed in metric spaces. The search complexity grows sharply with the dimension and with the search radius. We present a general probabilistic framework applicable to any search algorithm and whose net effect is to reduce the search radius. The higher the dimension, the more effective the technique. We illustrate empirically its practical performance on a particular class of algorithms, where large improvements in the search time are obtained at the cost of a very small error probability.
- Pivot selection techniques for proximity searching in metric spaces
- On the Least Cost for Proximity Searching in Metric Spaces
- On the geometry of similarity search: dimensionality curse and concentration of measure
- Probabilistic proximity searching algorithms based on compact partitions
- A unified approach to approximate proximity searching
- Computational geometry: a retrospective
- Fixed queries array: A fast and economical data structure for proximity searching
- scientific article; zbMATH DE number 1003290 (Why is no real title available?)
- scientific article; zbMATH DE number 2065612 (Why is no real title available?)
- Multidimensional Binary Search Trees in Database Applications
- Nearest neighbor queries in metric spaces
- Approximate similarity search: a multi-faceted problem
- Counting distance permutations
- Lower bounds on performance of metric tree indexing schemes for exact similarity search in high dimensions
- Maximum-likelihood approximate nearest neighbor method in real-time image recognition
- Feature weighting as a tool for unsupervised feature selection
- Pivot selection techniques for proximity searching in metric spaces
- scientific article; zbMATH DE number 2080487 (Why is no real title available?)
- scientific article; zbMATH DE number 1893567 (Why is no real title available?)
- Thinking ultrametrically, thinking p-adically
- On the Least Cost for Proximity Searching in Metric Spaces
- Probabilistic proximity searching algorithms based on compact partitions
- Dynamic detection for computer virus based on immune system
This page was built for publication: Probabilistic proximity search: Fighting the curse of dimensionality in metric spaces.
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1853173)
