Data-Dependent LSH for the Earth Mover’s Distance

Rajesh Jayaram, Erik Waingarten, Tian Zhang

Type: Article

Publication Date: 2024-06-10

Citations: 0

DOI: https://doi.org/10.1145/3618260.3649666

Locations

arXiv (Cornell University) - View - PDF

Similar Works

Action	Title	Year	Authors
+ PDF Chat	Data-Dependent LSH for the Earth Mover's Distance	2024	Rajesh Jayaram Erik Waingarten Tian Zhang
+	Practical and Optimal LSH for Angular Distance	2015	Alexandr Andoni Piotr Indyk Thijs Laarhoven Ilya Razenshteyn Ludwig Schmidt
+ PDF Chat	Optimal Data-Dependent Hashing for Approximate Near Neighbors	2015	Alexandr Andoni Ilya Razenshteyn
+	Optimal hashing-based time-space trade-offs for approximate near neighbors	2017	Alexandr Andoni Thijs Laarhoven Ilya Razenshteyn Erik Waingarten
+	Optimal Data-Dependent Hashing for Approximate Near Neighbors	2015	Alexandr Andoni Ilya Razenshteyn
+	Tight Lower Bounds for Data-Dependent Locality-Sensitive Hashing	2015	Alexandr Andoni Ilya Razenshteyn
+	On constant factor approximation for earth mover distance over doubling metrics	2010	Shi Li
+	Lower bounds on Locality Sensitive Hashing	2005	Rajeev Motwani Assaf Naor Rina Panigrahy‎
+ PDF Chat	Down the Rabbit Hole: Robust Proximity Search and Density Estimation in Sublinear Space	2014	Sariel Har-Peled Nirman Kumar
+	Optimal Hashing-based Time-Space Trade-offs for Approximate Near Neighbors	2017	Alexandr Andoni Thijs Laarhoven Ilya Razenshteyn Erik Waingarten
+	A Framework for Similarity Search with Space-Time Tradeoffs using Locality-Sensitive Filtering	2016	Tobias Christiani
+	Down the Rabbit Hole: Robust Proximity Search and Density Estimation in Sublinear Space	2011	Sariel Har-Peled Nirman Kumar
+	Down the Rabbit Hole: Robust Proximity Search and Density Estimation in Sublinear Space	2011	Sariel Har-Peled Nirman Kumar
+ PDF Chat	Average-Distortion Sketching	2024	Yuanyuan Bao Anubhav Baweja Nicolas Menand Erik Waingarten Nathan S. White Tian Zhang
+	Fast Locality-Sensitive Hashing Frameworks for Approximate Near Neighbor Search	2017	Tobias Christiani
+	Fast Locality-Sensitive Hashing Frameworks for Approximate Near Neighbor Search	2017	Tobias Christiani
+	Fast Locality-Sensitive Hashing for Approximate Near Neighbor Search.	2017	Tobias Christiani
+	A Refined Analysis of LSH for Well-dispersed Data Points	2017	Wenlong Mou Liwei Wang
+ PDF Chat	Lower Bounds on Locality Sensitive Hashing	2007	Rajeev Motwani Assaf Naor Rina Panigrahy‎
+	Conditional Hardness of Earth Mover Distance	2019	Dhruv Rohatgi

Works That Cite This (0)

Action	Title	Year	Authors

Works Cited by This (15)

Action	Title	Year	Authors
+ PDF Chat	Optimal Lower Bounds for Locality-Sensitive Hashing (Except When q is Tiny)	2014	Ryan O’Donnell Yi Wu Yuan Zhou
+ PDF Chat	Optimal Data-Dependent Hashing for Approximate Near Neighbors	2015	Alexandr Andoni Ilya Razenshteyn
+ PDF Chat	Parallel algorithms for geometric graph problems	2014	Alexandr Andoni Aleksandar Nikolov Krzysztof Onak Grigory Yaroslavtsev
+ PDF Chat	Embedding l ${}_{p}^{m}$ into l ${}_{1}^{n}$	1982	William B. Johnson Gideon Schechtman
+ PDF Chat	Computational Optimal Transport	2019	Gabriel Peyré Marco Cuturi
+ PDF Chat	Sketching and Embedding are Equivalent for Norms	2015	Alexandr Andoni Robert Krauthgamer Ilya Razenshteyn
+	New streaming algorithms for high dimensional EMD and MST	2022	Xi Chen Rajesh Jayaram Amit Levi Erik Waingarten
+	Generalized Preconditioning and Undirected Minimum-Cost Flow	2017	Jonah Sherman
+ PDF Chat	Maximum Flow and Minimum-Cost Flow in Almost-Linear Time	2022	Li Chen Rasmus Kyng Yang P. Liu Richard Peng Maximilian Probst Gutenberg Sushant Sachdeva
+ PDF Chat	Streaming Facility Location in High Dimension via Geometric Hashing	2022	Artur Czumaj Shaofeng H.-C. Jiang Robert Krauthgamer Pavel Veselý Mingwei Yang