822 citations
- New York UniversityUS5 papers
- University of California, BerkeleyUS5 papers
- Princeton UniversityUS4 papers
- California Institute of TechnologyUS3 papers
- Columbia UniversityUS3 papers
- Courant Institute of Mathematical SciencesUS3 papers
- Max Planck Institute for AstronomyDE3 papers
- University of Maryland, College ParkUS3 papers
- University of WashingtonUS3 papers
- AlbaNovaSE2 papers
- Fermi National Accelerator LaboratoryUS2 papers
- Goddard Space Flight CenterUS2 papers
Showing cs.DSShow all
2 papers · 1 filter
cs.DS2015★ 33 cited
Optimal Data-Dependent Hashing for Approximate Near Neighbors
Alexandr Andoni, Ilya Razenshteyn
We show an optimal data-dependent hashing scheme for the approximate near neighbor problem. For an -point data set in a -dimensional space our data structure achieves query t…
cs.DS2014★ 2 cited
Time lower bounds for nonadaptive turnstile streaming algorithms
Kasper Green Larsen, Jelani Nelson, Huy L. Nguyen
We say a turnstile streaming algorithm is "non-adaptive" if, during updates, the memory cells written and read depend only on the index being updated and random coins tossed at the…