Imagen de Portada

Data-Dependent LSH for the Earth Mover's Distance

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autores principales:	Jayaram, Rajesh, Waingarten, Erik, Zhang, Tian
Formato:	Preprint
Publicado:	2024
Materias:	Data Structures and Algorithms
Acceso en línea:	Acceder al recurso
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

Ejemplares similares

Approximating High-Dimensional Earth Mover's Distance as Fast as Closest Pair
por: Beretta, Lorenzo, et al.
Publicado: (2025)

Tight Pair Query Lower Bounds for Matching and Earth Mover's Distance
por: Azarmehr, Amir, et al.
Publicado: (2025)

Streaming and Massively Parallel Algorithms for Euclidean Max-Cut
por: Menand, Nicolas, et al.
Publicado: (2025)

A Quasi-Monte Carlo Data Structure for Smooth Kernel Evaluations
por: Charikar, Moses, et al.
Publicado: (2024)

Randomized Dimensionality Reduction for Euclidean Maximization and Diversity Measures
por: Gao, Jie, et al.
Publicado: (2025)

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

Average-Distortion Sketching
por: Bao, Yiqiao, et al.
Publicado: (2024)

Nearly Tight Bounds on Testing of Metric Properties
por: Bao, Yiqiao, et al.
Publicado: (2024)

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

Streaming Algorithms with Few State Changes
por: Jayaram, Rajesh, et al.
Publicado: (2024)

Instance-Optimal Uniformity Testing and Tracking
por: Blanc, Guy, et al.
Publicado: (2025)

On the LSH Distortion of Ulam and Cayley Similarities
por: Chierichetti, Flavio, et al.
Publicado: (2026)

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

Dynamic PageRank: Algorithms and Lower Bounds
por: Jayaram, Rajesh, et al.
Publicado: (2024)

Massively Parallel Minimum Spanning Tree in General Metric Spaces
por: Azarmehr, Amir, et al.
Publicado: (2024)

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

Lower Bounds for Convexity Testing
por: Chen, Xi, et al.
Publicado: (2024)

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

A Polynomial Space Lower Bound for Diameter Estimation in Dynamic Streams
por: Khanna, Sanjeev, et al.
Publicado: (2025)

Efficient Centroid-Linkage Clustering
por: Bateni, MohammadHossein, et al.
Publicado: (2024)

Metric Embeddings Beyond Bi-Lipschitz Distortion via Sherali-Adams
por: Bakshi, Ainesh, et al.
Publicado: (2023)

MUVERA: Multi-Vector Retrieval via Fixed Dimensional Encodings
por: Dhulipala, Laxman, et al.
Publicado: (2024)

The Kinetic Hourglass Data Structure for Computing the Bottleneck Distance of Dynamic Data
por: Munch, Elizabeth, et al.
Publicado: (2025)

Kd-tree Based Wasserstein Distance Approximation for High-Dimensional Data
por: Teshigawara, Kanata, et al.
Publicado: (2026)

Faster Algorithm for Bounded Tree Edit Distance in the Low-Distance Regime
por: Kociumaka, Tomasz, et al.
Publicado: (2025)

Hamming Distance Oracle
por: Boneh, Itai, et al.
Publicado: (2024)

Dynamic Dyck and Tree Edit Distance: Decompositions and Reductions to String Edit Distance
por: Das, Debarati, et al.
Publicado: (2025)

Many Flavors of Edit Distance
por: Bhattacharya, Sudatta, et al.
Publicado: (2024)

Distributed Distance Sensitivity Oracles
por: Manoharan, Vignesh, et al.
Publicado: (2024)

Lower Bounds for Approximate (& Exact) k-Disjoint-Shortest-Paths
por: Chitnis, Rajesh, et al.
Publicado: (2024)

Max-Distance Sparsification for Diversification and Clustering
por: Kumabe, Soh
Publicado: (2024)

Optimal Distance Labeling for Permutation Graphs
por: Gawrychowski, Paweł, et al.
Publicado: (2024)

Graph Spanners for Group Steiner Distances
por: Bilò, Davide, et al.
Publicado: (2024)

Max-Min Diversification with Asymmetric Distances
por: Kumpulainen, Iiro, et al.
Publicado: (2025)

On Rotation Distance of Rank Bounded Trees
por: M., Anoop S. K., et al.
Publicado: (2023)

Fully Dynamic Algorithms for Chamfer Distance
por: Goranci, Gramoz, et al.
Publicado: (2025)

Distances in Planar Graphs are Almost for Free!
por: Mozes, Shay, et al.
Publicado: (2026)

Learning Dependency Models for Subset Repair
por: Li, Haoda, et al.
Publicado: (2025)

Improved Distance (Sensitivity) Oracles with Subquadratic Space
por: Bilò, Davide, et al.
Publicado: (2024)

Almost Linear Size Edit Distance Sketch
por: Koucký, Michal, et al.
Publicado: (2024)