Cover Image

Sublinear Data Structures for Nearest Neighbor in Ultra High Dimensions

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Herold, Martin G., Nanongkai, Danupon, Spoerhase, Joachim, Varma, Nithin, Wu, Zihang
Format:	Preprint
Published:	2025
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

Fully Dynamic Exact Edge Connectivity in Sublinear Time
by: Goranci, Gramoz, et al.
Published: (2023)

Minimum $s$--$t$ Cuts with Fewer Cut Queries
by: Jiang, Yonggang, et al.
Published: (2025)

Negative-Weight Single-Source Shortest Paths in Near-linear Time
by: Bernstein, Aaron, et al.
Published: (2022)

Incremental Planar Nearest Neighbor Queries with Optimal Query Time
by: Iacono, John, et al.
Published: (2025)

Fast Nearest Neighbor Search for $\ell_p$ Metrics
by: Krauthgamer, Robert, et al.
Published: (2026)

On Practical Nearest Sub-Trajectory Queries under the Fréchet Distance
by: Gudmundsson, Joachim, et al.
Published: (2022)

Shortcuts and Transitive-Closure Spanners Approximation
by: Chalermsook, Parinya, et al.
Published: (2025)

Graph-Based Nearest-Neighbor Search without the Spread
by: Giliberti, Jeff, et al.
Published: (2026)

A Broader View on Clustering under Cluster-Aware Norm Objectives
by: Herold, Martin G., et al.
Published: (2025)

Clustering to Minimize Cluster-Aware Norm Objectives
by: Herold, Martin G., et al.
Published: (2024)

Navigable Graphs for High-Dimensional Nearest Neighbor Search: Constructions and Limits
by: Diwan, Haya, et al.
Published: (2024)

Using Ray-shooting Queries for Sublinear Algorithms for Dominating Sets in RDV Graphs
by: Biedl, Therese, et al.
Published: (2026)

Sublinear Sketches for Approximate Nearest Neighbor and Kernel Density Estimation
by: Danait, Ved, et al.
Published: (2025)

Adversarially Robust Approximate Furthest Neighbor
by: Banihashem, Kiarash, et al.
Published: (2026)

Sublinear-Time Reconfiguration of Programmable Matter with Joint Movements
by: Kumar, Manish, et al.
Published: (2026)

Terminal Embeddings in Sublinear Time
by: Cherapanamjeri, Yeshwanth, et al.
Published: (2021)

Parameterized Approximation for Robust Clustering in Discrete Geometric Spaces
by: Abbasi, Fateme, et al.
Published: (2023)

SVD Provably Denoises Nearest Neighbor Data
by: Kannan, Ravindran, et al.
Published: (2026)

Pseudodeterministic Algorithms for Minimum Cut Problems
by: Agarwala, Aryan, et al.
Published: (2025)

Approximating Traveling Salesman Problems Using a Bridge Lemma
by: Böhm, Martin, et al.
Published: (2024)

Data Structures for Approximate Discrete Fréchet Distance
by: van der Hoog, Ivor, et al.
Published: (2022)

Dimension-Free Parameterized Approximation Schemes for Hybrid Clustering
by: Gadekar, Ameet, et al.
Published: (2025)

Data Structures for Range Sorted Consecutive Occurrence Queries
by: Akram, Waseem, et al.
Published: (2024)

Strongly Sublinear Algorithms for Testing Pattern Freeness
by: Newman, Ilan, et al.
Published: (2021)

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

Dimension-Accuracy Tradeoffs in Contrastive Embeddings for Triplets, Terminals & Top-k Nearest Neighbors
by: Chatziafratis, Vaggos, et al.
Published: (2023)

A Tail Estimate with Exponential Decay for the Randomized Incremental Construction of Search Structures
by: Gudmundsson, Joachim, et al.
Published: (2021)

A Polynomial Coreset for Furthest Neighbor in Planar Metrics
by: Kluk, Kacper, et al.
Published: (2026)

Spanner for the $0/1/\infty$ weighted region problem
by: Gudmundsson, Joachim, et al.
Published: (2024)

Sublinear-Time Computation in the Presence of Online Erasures
by: Kalemaj, Iden, et al.
Published: (2021)

Learning with Structure: Computing Consistent Subsets on Structurally-Regular Graphs
by: Banik, Aritra, et al.
Published: (2025)

Parallel, Distributed, and Quantum Exact Single-Source Shortest Paths with Negative Edge Weights
by: Ashvinkumar, Vikrant, et al.
Published: (2023)

A Task-Parallel Approach for Localized Topological Data Structures
by: Liu, Guoxi, et al.
Published: (2023)

Approximation Schemes and Structural Barriers for the Two-Dimensional Knapsack Problem with Rotations
by: Kar, Debajyoti, et al.
Published: (2026)

Improved Online Hitting Set Algorithms for Structured and Geometric Set Systems
by: Bhore, Sujoy, et al.
Published: (2026)

Discovering Data Structures: Nearest Neighbor Search and Beyond
by: Salemohamed, Omar, et al.
Published: (2024)

Simple Grid Polygon Online Exploration Revisited
by: Brock, Maximilian, et al.
Published: (2024)

Feature-aware manifold meshing and remeshing of point clouds and polyhedral surfaces with guaranteed smallest edge length
by: Lipschütz, Henriette, et al.
Published: (2023)

Efficient Data Shapley for Weighted Nearest Neighbor Algorithms
by: Wang, Jiachen T., et al.
Published: (2024)

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