2026-07-20T05:10:56Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:17005 2024-03-06T10:58:57Z ddc:004 open_access

Chromatic k-Nearest Neighbor Queries van der Horst, Thijs Löffler, Maarten Staals, Frank data structure nearest neighbor classification Let P be a set of n colored points. 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(n^{1/2} log n) for points in ℝ¹, and with query times varying between O(n^{2/3}log^{2/3} n) and O(n^{5/6} polylog n), depending on the distance measure used, for points in ℝ². These results can be extended to work in higher dimensions as well. Since the 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 + log log_{1/(1-ε)} n) in ℝ¹ and expected query times ranging between Õ(n^{1/2}ε^{-3/2}) and Õ(n^{1/2}ε^{-5/2}) in ℝ² using near-linear space (ignoring polylogarithmic factors). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Thijs van der Horst and Maarten Löffler and Frank Staals 2022 Is Part Of LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2022.67 urn:nbn:de:0030-drops-170055 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2022.67 eng https://creativecommons.org/licenses/by/4.0/legalcode