Cover Image

Graph-based Nearest Neighbors with Dynamic Updates via Random Walks

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Mishra, Nina, Naamad, Yonatan, Wagner, Tal, Zhang, Lichen
Format:	Preprint
Published:	2025
Subjects:	Data Structures and Algorithms Machine Learning
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

New Bounds for Kernel Sums via Fast Spherical Embeddings
by: Wagner, Tal
Published: (2026)

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

Efficient Banzhaf-Based Data Valuation for $k$-Nearest Neighbors Classification
by: Zhang, Guangyi, et al.
Published: (2026)

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

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

SpEx: A Spectral Approach to Explainable Clustering
by: Argov, Tal, et al.
Published: (2025)

Log-concave Sampling from a Convex Body with a Barrier: a Robust and Unified Dikin Walk
by: Gu, Yuzhou, et al.
Published: (2024)

Approximate Nearest Neighbor Search with Window Filters
by: Engels, Joshua, et al.
Published: (2024)

Positional LSH: Binary Block Matrix Approximation for Attention with Linear Biases
by: Wolfson, Daniel, et al.
Published: (2026)

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

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

Quantization for Vector Search under Streaming Updates
by: Aden-Ali, Ishaq, et al.
Published: (2025)

Distance Adaptive Beam Search for Provably Accurate Graph-Based Nearest Neighbor Search
by: Al-Jazzazi, Yousef, et al.
Published: (2025)

Learning from End User Data with Shuffled Differential Privacy over Kernel Densities
by: Wagner, Tal
Published: (2025)

Efficient Sketching and Nearest Neighbor Search Algorithms for Sparse Vector Sets
by: Bruch, Sebastian, et al.
Published: (2025)

PECANN: Parallel Efficient Clustering with Graph-Based Approximate Nearest Neighbor Search
by: Yu, Shangdi, et al.
Published: (2023)

Improved Algorithms for Kernel Matrix-Vector Multiplication Under Sparsity Assumptions
by: Indyk, Piotr, et al.
Published: (2025)

Sparse Navigable Graphs for Nearest Neighbor Search: Algorithms and Hardness
by: Khanna, Sanjeev, et al.
Published: (2025)

Fast-Convergent Proximity Graphs for Approximate Nearest Neighbor Search
by: Li, Binhong, et al.
Published: (2025)

Dynamic Correlation Clustering in Sublinear Update Time
by: Cohen-Addad, Vincent, et al.
Published: (2024)

John Ellipsoids via Lazy Updates
by: Woodruff, David P., et al.
Published: (2025)

Probabilistic Routing for Graph-Based Approximate Nearest Neighbor Search
by: Lu, Kejing, et al.
Published: (2024)

Low Rank Matrix Completion via Robust Alternating Minimization in Nearly Linear Time
by: Gu, Yuzhou, et al.
Published: (2023)

Fully Dynamic Adversarially Robust Correlation Clustering in Polylogarithmic Update Time
by: Braverman, Vladimir, et al.
Published: (2024)

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

HENN: A Hierarchical Epsilon Net Navigation Graph for Approximate Nearest Neighbor Search
by: Dehghankar, Mohsen, et al.
Published: (2025)

Correlation Clustering Algorithm for Dynamic Complete Signed Graphs: An Index-based Approach
by: Shakiba, Ali
Published: (2023)

Sparse Neighborhood Graph-Based Approximate Nearest Neighbor Search Revisited: Theoretical Analysis and Optimization
by: Ma, Xinran, et al.
Published: (2025)

Sublinear Time Quantum Sensitivity Sampling
by: Song, Zhao, et al.
Published: (2025)

Private Edge Density Estimation for Random Graphs: Optimal, Efficient and Robust
by: Chen, Hongjie, et al.
Published: (2024)

Sublinear Time Quantum Algorithm for Attention Approximation
by: Song, Zhao, et al.
Published: (2026)

Improving LSH via Tensorized Random Projection
by: Verma, Bhisham Dev, et al.
Published: (2024)

Efficient Algorithms for Adversarially Robust Approximate Nearest Neighbor Search
by: Andoni, Alexandr, et al.
Published: (2026)

Unleashing Graph Partitioning for Large-Scale Nearest Neighbor Search
by: Gottesbüren, Lars, et al.
Published: (2024)

Dynamic Similarity Graph Construction with Kernel Density Estimation
by: Laenen, Steinar, et al.
Published: (2025)

Faster Graph Embeddings via Coarsening
by: Fahrbach, Matthew, et al.
Published: (2020)

Estimating Random-Walk Probabilities in Directed Graphs
by: Bertram, Christian, et al.
Published: (2025)

Bypassing the Noisy Parity Barrier: Learning Higher-Order Markov Random Fields from Dynamics
by: Gaitonde, Jason, et al.
Published: (2024)

The Marked Edge Walk: A Novel MCMC Algorithm for Sampling of Graph Partitions
by: McWhorter, Atticus, et al.
Published: (2025)

Prune, Don't Rebuild: Efficiently Tuning $α$-Reachable Graphs for Nearest Neighbor Search
by: Zhang, Tian, et al.
Published: (2026)