Proximity problems for high-dimensional data
Ioannis Psarros · HAL (Le Centre pour la Communication Scientifique Directe) · 2019
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.