2025/03/17 by Van Der Horst, Thijs, Löffler, Maarten, Staals, Frank
paper · doi:10.20382/jocg.v16i1a3
Let P be a set of n colored points in ℝd. We develop efficient data structures that store P and can answer chromatic k-nearest neighbor (k-NN) queries. Such a query consists of a query point q and a number k, and asks for the color that appears most frequently among the k points in P closest to q. Answering such queries efficiently is the key to obtain fast k-NN classifiers. Our main aim is to obtain query times that are independent of k while using near-linear space. We show that this is possible using a combination of two data structures. The first data structure allow us to compute a region containing exactly the k-nearest neighbors of a query point q, and the second data structure can then report the most frequent color in such a region. This leads to linear-space data structures with query times of O(n1 / 2 log n) for points in ℝ1, and with query times varying between O(n2/3log2/3 n) and O(n5/6 \mathoppolylog n), depending on the distance measure used, for points in ℝ2. Since these query times are still fairly large we also consider approximations. If we are allowed to report a color that appears at least (1-ε)f^* times, where f^* is the frequency of the most frequent color, we obtain a query time of O(log n + loglog(1)/(1-ε) n) in ℝ1 and expected query times ranging between O(n1/2ε-3/2) and O(n1/2ε-5/2) in ℝ2 using near-linear space (ignoring polylogarithmic factors). All of our data structures are for the pointer-machine model.