National and Kapodistrian University of Athens
Proximity problems for high-dimensional data
Abstract
dc:descriptionFinding similar objects is a general computational task which serves as a subroutine for many major learning tasks like classification or clustering. With the recent increase of availability of complex datasets, the need for analyzing and handling high-dimensional descriptors has been increased. Likewise, there is a surge of interest into data structures for trajectory processing, motivated by the increasing availability and quality of trajectory data from mobile phones, GPS sensors, RFID technology and video analysis. In this thesis, we investigate proximity problems for highdimensional vectors and polygonal curves. The natural way to measure dissimilarity between two vectors is by evaluating a norm function for the vector difference. Popular examples of such distance functions are the Euclidean distance and the Manhattan distance. Similarly, there exist several well-studied distance functions for polygonal curves, the main example being the Fréchet distance. The core problem, for both data types, is the nearest neighbor searching problem. Given a set of objects P , we aim for a data structure which supports nearest neighbor queries; a new object q arrives and the data structure returns the most similar object in P . When the data complexity is high, aiming for an exact solution is often futile. This has led researchers to the more tractable task of designing approximate solutions. The largest part of this thesis is devoted to the approximate nearest neighbor problem and the approximate near neighbor problem: given a set of objects P and a radius parameter r, the data structure returns an object in P which is approximately within distance r (if there exists one) from some query object q. Another basic question is that of computing a subset of good representatives for a dataset. This subset often provides with sufficient information for a given computational task, and hence it possibly simplifies existing solutions. Finally, we investigate range systems for polygonal curves: we bound the Vapnik–Chervonenkis dimension for ranges defined by distance functions for curves. These bounds have direct implications in range counting problems and density estimation. The thesis is organized as follows. We introduce a new definition of “low-quality” embeddings for metric spaces. It requires that, for some query point q, there exists an approximate nearest neighbor among the pre-images of the k > 1 approximate nearest neighbors in the target space. Focusing on Euclidean spaces, we employ random projections à la Johnson Lindenstrauss in order to reduce the original problem to one in a space of dimension inversely proportional to k. This leads to simple data structures which are space-efficient and also support sublinear queries. By employing properties of certain LSH functions, we exploit a similar mapping to the Hamming space. Our primary motivation is the approximate nearest neighbor problem in l1, for pointsets with low intrinsic dimension. Doubling dimension is a well-established notion which aims to capture the intrinsic dimension of points. Nearest neighbor-preserving embeddings are known to exist for both l2 and l1 metrics, as well as for doubling subsets of l2. We propose a dimension reduction by means of a near neighbor-preserving embedding for doubling subsets of l1. Nets offers a powerful tool in computational and metric geometry, since they serve as a subset of good representatives: all points are within distance r from some net point and all net points lie at distance at least r from each other. We focus on high-dimensional spaces and present a new randomized algorithm which efficiently computes approximate r-nets with respect to Euclidean distance. Our algorithm follows a recent approach by Valiant in reducing the problem to multipoint evaluation of polynomials. We propose simple and efficient data structures, based on randomized projections, for a notion of distance between discretized curves, which generalizes both discrete Fréchet and Dynamic Time Warping distance functions. We offer the first data structures and query algorithms for the approximate nearest neighbor problem with arbitrarily good approximation factor, at the expense of increasing space usage and preprocessing time over existing methods. We propose simple and efficient data structures, based on random partitions, for the discrete Fréchet distance, in the short query regime. The data structures are especially efficient when queries are much shorter than the polygonal curves which belong to the dataset. We also study the problem for arbitrary metrics with bounded doubling dimension. The Vapnik-Chervonenkis dimension provides a notion of complexity for set or range systems. We analyze range systems where the ground set is a set of polygonal curves in the Euclidean space and the ranges are metric balls defined by curve dissimilarity measures, such as the Fréchet distance and the Hausdorff distance. Direct implications follow by applying known sampling bounds.
Degree
thesis:*- Grantor dc:publisher
- National and Kapodistrian University of Athens
- Year dc:date
- 2019
Author and committee
dc:creator, dc:contributor.*- Authors dc:creator
-
- Psarros, Ioannis
- Ψαρρός, Ιωάννης
Subjects
dc:subject × 10Rights
dc:rights- Statement dc:rights
-
- BY_NC
- Language dc:language
- eng
Identifiers
dc:identifier.*- Identifier
- 10.12681/eadd/45950