Performance bounds for nearest neighbor search with k-d trees

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Bazzani, Marco, Dasgupta, Sanjoy
Format:	Preprint
Published:	2026
Subjects:	Data Structures and Algorithms Computational Geometry
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

A new near-linear time algorithm for k-nearest neighbor search using a compressed cover tree
by: Elkin, Yury, et al.
Published: (2021)

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)

New bounds on the cohesion of complete-link and other linkage methods for agglomeration clustering
by: Dasgupta, Sanjoy, et al.
Published: (2024)

Top-k Stabbing Interval Queries
by: Akram, Waseem, 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)

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

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

Near-tight Bounds for Computing the Fréchet Distance in d-Dimensional Grid Graphs and the Implications for λ-low Dense Curves
by: Conradi, Jacobus, et al.
Published: (2026)

An Algorithmic Solution for Computing Circle Intersection Areas and its Applications to Wireless Communications
by: Librino, Federico, et al.
Published: (2012)

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

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

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

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

Fast and simple multiplication of bounded twin-width matrices
by: Kozma, László, et al.
Published: (2026)

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

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

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

Lower bounds for the universal TSP on the plane
by: Kravaris, Cosmas
Published: (2024)

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

Dynamic and Streaming Algorithms for Union Volume Estimation
by: Bhore, Sujoy, et al.
Published: (2026)

Counting Unit Circular Arc Intersections
by: Wang, Haitao
Published: (2026)

Optimal-Cost Construction of Shallow Cuttings for 3-D Dominance Ranges in the I/O-Model
by: Nekrich, Yakov, et al.
Published: (2026)

Upward-Planar Drawings with Bounded Span
by: Angelini, Patrizio, et al.
Published: (2026)

Exact Subquadratic Algorithm for Many-to-Many Matching on Planar Point Sets with Integer Coordinates
by: Park, Seongbin, et al.
Published: (2026)

Scalable Exact Hierarchical Agglomerative Clustering via Sparse Geographic Distance Graphs
by: Maus, Victor, et al.
Published: (2026)

Online Algorithms for Geometric Independent Set
by: De, Minati, et al.
Published: (2026)

FPT Approximation Schemes for Min-Sum Radii and Min-Sum Diameters Clustering
by: Grandoni, Fabrizio, et al.
Published: (2026)

Hitting Axis-Parallel Segments with Weighted Points
by: Raman, Rajiv, et al.
Published: (2026)

Deterministic Volume Estimation of Truncated Hypercubes
by: Gunluk, Kyra
Published: (2026)

Approximation Schemes for Subset TSP and Steiner Tree on Geometric Intersection Graphs
by: Kisfaludi-Bak, Sándor, et al.
Published: (2026)

Charting the Diameter Computation Landscape of Geometric Intersection Graphs in Three Dimensions and Higher
by: Chan, Timothy M., et al.
Published: (2026)

Instance and Universally Optimal Bounds for Imprecise Pareto Fronts
by: de Berg, Sarita, et al.
Published: (2026)

Delaunay Triangulations with Predictions
by: Cabello, Sergio, et al.
Published: (2026)

Lower Bounds for Dominating Set in Ball Graphs and for Weighted Dominating Set in Unit-Ball Graphs
by: de Berg, Mark, et al.
Published: (2026)

Parameterized Approximation of Rectangle Stabbing
by: Chu, Huairui, et al.
Published: (2026)

Maximum Independent Sets in Disk Graphs with Disks in Convex Position
by: Tkachenko, Anastasiia, et al.
Published: (2026)

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