Chromatic k-Nearest Neighbors Queries using (Near-)Linear Space
Summary
In this thesis, we study the chromatic k-nearest neighbors problem in one and two dimension(s), under the L_1, L_2 and L_∞ metrics. In this problem, we wish to preprocess a set of n colored points, such that given a query point q and integer k, the most frequently occurring color among the k nearest neighbors of q can be found efficiently. We give the first data structures that answer queries without computing the k-nearest neighbors of a query point explicitly, resulting in query time complexities that are truly sublinear. Aside from the standard chromatic k-nearest neighbors problem, we also study the semi-online variant of the problem, in which we allow points to be added and deleted, as long as the time at which a point is deleted is known once it is inserted. Finally, we also consider an approximate version of the problem, in which a color needs to be reported that occurs often enough among the k-nearest neighbors of q. For all but the two-dimensional approximate problem under the L_1 and L_∞ metrics, we give data structures that use linear space. For this last problem, we show the existence of a linear-space data structure, whose query time is lower than what we achieve.