Proximity problems for high-dimensional data
Preprint
Abstract
With the increase of availability of complex datasets, there is a need for algorithmic solutions which scale well as the complexity of the data increases. We focus on proximity problems for high-dimensional vectors and polygonal curves and we present new solutions for the problem of computing approximate nearest neighbors. In Euclidean spaces, we propose and analyse random projections to a very low dimension, aiming for a high-dimensional solution which is also space efficient. For polygonal curves, we design a data structure with arbitrarily small approximation error. In addition, we present a new solution for computing good representatives, when the dataset consists of high-dimensional vectors. Finally, we study range spaces defined by metrics for polygonal curves and we present new bounds on their VC dimension.Keywords
All Related Versions
This publication has 3 references indexed in Scilit:
- Randomized Embeddings with Slack and High-Dimensional Approximate Nearest NeighborACM Transactions on Algorithms, 2018
- Database-friendly random projections: Johnson-Lindenstrauss with binary coinsJournal of Computer and System Sciences, 2003
- Extensions of Lipschitz mappings into a Hilbert space1984