A new near-linear time algorithm for k-nearest neighbor search using a compressed cover tree

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Elkin, Yury, Kurlin, Vitaliy
Format:	Preprint
Published:	2021
Subjects:	Computational Geometry Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Performance bounds for nearest neighbor search with k-d trees
by: Bazzani, Marco, et al.
Published: (2026)

Parameterized and approximation algorithms for coverings points with segments in the plane
by: Kowalska, Katarzyna, et al.
Published: (2024)

Hybrid k-Clustering: Blending k-Median and k-Center
by: Fomin, Fedor V., et al.
Published: (2024)

Finding the root in random nearest neighbor trees
by: Brandenberger, Anna, et al.
Published: (2024)

Euclidean distance compression via deep random features
by: Leroux, Brett, et al.
Published: (2024)

A face cover perspective to $\ell_1$ embeddings of planar graphs
by: Filtser, Arnold
Published: (2019)

Top-k Stabbing Interval Queries
by: Akram, Waseem, et al.
Published: (2024)

A Subquadratic Time Approximation Algorithm for Individually Fair k-Center
by: Ebbens, Matthijs, et al.
Published: (2024)

Efficient Enumeration of At Most $k$-Out Polygons
by: Akram, Waseem, et al.
Published: (2025)

Faster Approximation Scheme for Euclidean $k$-TSP
by: van Wijland, Ernest, et al.
Published: (2023)

On Optimal Coreset Construction for Euclidean $(k,z)$-Clustering
by: Huang, Lingxiao, et al.
Published: (2022)

Experimental comparison of graph-based approximate nearest neighbor search algorithms on edge devices
by: Ganbarov, Ali, et al.
Published: (2024)

Faster exponential algorithms for cut problems via geometric data structures
by: Kozma, László, et al.
Published: (2025)

Subexponential algorithms in geometric graphs via the subquadratic grid minor property: the role of local radius
by: Berthe, Gaétan, et al.
Published: (2023)

On connections between k-coloring and Euclidean k-means
by: Aman, Enver, et al.
Published: (2024)

Approximation algorithms for satisfiable and nearly satisfiable ordering CSPs
by: Makarychev, Yury
Published: (2026)

Worst-Case and Smoothed Analysis of the Hartigan-Wong Method for k-Means Clustering
by: Manthey, Bodo, et al.
Published: (2023)

The Complexity of Geodesic Spanners using Steiner Points
by: de Berg, Sarita, et al.
Published: (2024)

Fine-Grained Complexity of Continuous Euclidean k-Center
by: Blank, Lotte, et al.
Published: (2026)

Recognizing 2-Layer and Outer $k$-Planar Graphs
by: Kobayashi, Yasuaki, et al.
Published: (2024)

Near-Optimal Bounds for Parameterized Euclidean k-means
by: Cohen-Addad, Vincent, et al.
Published: (2026)

Binary weights spanning trees and the $k$-red spanning tree problem in linear time
by: Hochbaum, Dorit S.
Published: (2024)

Hashing geographical point data using the space-filling H-curve
by: Netay, Igor V.
Published: (2024)

Time complexity of the Analyst's Traveling Salesman algorithm
by: Ramirez, Anthony, et al.
Published: (2022)

On Tight Robust Coresets for $k$-Medians Clustering
by: Huang, Lingxiao, et al.
Published: (2025)

Improved Learning via k-DTW: A Novel Dissimilarity Measure for Curves
by: Krivošija, Amer, et al.
Published: (2025)

An algorithm for accurate and simple-looking metaphorical maps
by: Katsanou, Eleni, et al.
Published: (2025)

Finding a Largest-Area Triangle in a Terrain in Near-Linear Time
by: Cabello, Sergio, et al.
Published: (2021)

$k$-PCA for (non-squared) Euclidean Distances: Polynomial Time Approximation
by: Greenhut, Daniel, et al.
Published: (2025)

Touring a Sequence of Orthogonal Polygons
by: Casel, Katrin, et al.
Published: (2026)

Bifurcation: How to Explore a Tree
by: Har-Peled, Sariel
Published: (2025)

A Deterministic Partition Tree and Applications
by: Wang, Haitao
Published: (2025)

On computing the (exact) Fréchet distance with a frog
by: Conradi, Jacobus, et al.
Published: (2025)

Ranking and Unranking of the Planar Embeddings of a Planar Graph
by: Di Battista, Giuseppe, et al.
Published: (2024)

NP-hardness and a PTAS for the Euclidean Steiner Line Problem
by: Bartlmae, Simon, et al.
Published: (2024)

Sampling from convex sets with a cold start using multiscale decompositions
by: Narayanan, Hariharan, et al.
Published: (2022)

A dynamic $(1+\varepsilon)$-spanner for disk intersection graphs
by: de Berg, Sarita, et al.
Published: (2026)

A Quasi-Polynomial Time Algorithm for 3-Coloring Circle Graphs
by: S, Ajaykrishnan E, et al.
Published: (2025)

Bipartizing (Pseudo-)Disk Graphs: Approximation with a Ratio Better than 3
by: Lokshtanov, Daniel, et al.
Published: (2024)

A Bouquet of Results on Maximum Range Sum: General Techniques and Hardness Reductions
by: Gusain, Rachana, et al.
Published: (2025)