Fetching the paper…
Reading the bibliography…
In the Distance Oracle problem, the goal is to preprocess $n$ vectors $x_1, x_2, \cdots, x_n$ in a $d$-dimensional metric space $(\mathbb{X}^d, \| \cdot \|_l)$ into a cheap data structure, so that given a query vector $q \in \mathbb{X}^d$ and a subset $S\subseteq [n]$ of the input data points, all distances $\| q - x_i \|_l$ for $x_i\in S$ can be quickly approximated (faster than the trivial $\sim d|S|$ query time).
A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations
Herman Chernoff · 1952
Earlier work this paper cites.
Extensions of lipschitz mappings into a hilbert space
William B Johnson and Joram Lindenstrauss · 1984
Earlier work this paper cites.
Asymptotic theory of finite dimensional normed spaces, volume 1200 of lectures notes in mathematics, 1986
M Gromov, V Milman, and G Schechtman · 1986
Earlier work this paper cites.
Matrix analysis, volume 169 of
Rajendra Bhatia · 1997
Earlier work this paper cites.
The space complexity of approximating the frequency moments
Noga Alon, Yossi Matias, and Mario Szegedy · 1999
Earlier work this paper cites.
Proximity-preserving labeling schemes
David Peleg · 2000
Earlier work this paper cites.
Space lower bounds for distance approximation in the data stream model
Michael Saks and Xiaodong Sun · 2002
Earlier work this paper cites.
An information statistics approach to data stream and communication complexity
Ziv Bar-Yossef, Thathachar S Jayram, Ravi Kumar, and D Sivakumar · 2004
Earlier work this paper cites.
Finding frequent items in data streams
Moses Charikar, Kevin C. Chen, and Martin Farach-Colton · 2004
Earlier work this paper cites.
Distance labeling in graphs
Cyril Gavoille, David Peleg, Stéphane Pérennes, and Ran Raz · 2004
Earlier work this paper cites.
Optimal approximations of the frequency moments of data streams
Piotr Indyk and David Woodruff · 2005
Earlier work this paper cites.
Stable distributions, pseudorandom generators, embeddings, and data stream computation
Piotr Indyk · 2006
Earlier work this paper cites.
Information-theoretic metric learning
Jason V Davis, Brian Kulis, Prateek Jain, Suvrit Sra, and Inderjit S Dhillon · 2007
Earlier work this paper cites.
Online metric learning and fast similarity search
Prateek Jain, Brian Kulis, Inderjit S Dhillon, and Kristen Grauman · 2008
Earlier work this paper cites.
The fast johnson–lindenstrauss transform and approximate nearest neighbors
Nir Ailon and Bernard Chazelle · 2009
Earlier work this paper cites.
Kernel methods for deep learning
Youngmin Cho and Lawrence Saul · 2009
Earlier work this paper cites.
On the exact space complexity of sketching and streaming small norms
Daniel M Kane, Jelani Nelson, and David P Woodruff · 2010
Earlier work this paper cites.
Fast moment estimation in data streams in optimal space
Daniel M Kane, Jelani Nelson, Ely Porat, and David P Woodruff · 2011
Earlier work this paper cites.
Efficient sketches for the set query problem
Eric Price · 2011
Cited alongside, same era.
Pegasos: Primal estimated sub-gradient solver for svm
Shai Shalev-Shwartz, Yoram Singer, Nathan Srebro, and Andrew Cotter · 2011
Cited alongside, same era.
A note on exact distance labeling
Oren Weimann and David Peleg · 2011
Cited alongside, same era.
Sparse prediction with the k k -support norm
Andreas Argyriou, Rina Foygel, and Nathan Srebro · 2012
Cited alongside, same era.
Nearly optimal sparse fourier transform
Haitham Hassanieh, Piotr Indyk, Dina Katabi, and Eric Price · 2012
Cited alongside, same era.
Tabulation-based 5-independent hashing with applications to linear probing and second moment estimation
Mikkel Thorup and Yin Zhang · 2012
Cited alongside, same era.
Subspace embedding and linear regression with orlicz norm
Alexandr Andoni, Chengyu Lin, Ying Sheng, Peilin Zhong, and Ruiqi Zhong · 2018
Later among the works it cites.
Hölder homeomorphisms and approximate nearest neighbors
Alexandr Andoni, Assaf Naor, Aleksandar Nikolov, Ilya Razenshteyn, and Erik Waingarten · 2018
Later among the works it cites.
Cell-probe lower bounds from online communication complexity
Josh Alman, Joshua R Wang, and Huacheng Yu · 2018
Later among the works it cites.
Algorithmic theory of odes and sampling from well-conditioned logconcave densities
Yin Tat Lee, Zhao Song, and Santosh S Vempala · 2018
Later among the works it cites.
An illuminating algorithm for the light bulb problem
Josh Alman · 2019
Later among the works it cites.
On mean estimation for general norms with statistical queries
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Finding correlations in subquadratic time, with applications to learning parities and juntas
Gregory Valiant · 2012
Cited alongside, same era.
Faster ridge regression via the subsampled randomized hadamard transform
Yichao Lu, Paramveer Dhillon, Dean P Foster, and Lyle Ungar · 2013
Cited alongside, same era.
Compressed matrix multiplication
Rasmus Pagh · 2013
Cited alongside, same era.
More applications of the polynomial method to algorithm design
Amir Abboud, Ryan Williams, and Huacheng Yu · 2014
Cited alongside, same era.
Spectral k-support norm regularization
Andrew M McDonald, Massimiliano Pontil, and Dimitris Stamos · 2014
Cited alongside, same era.
Unifying and strengthening hardness for dynamic problems via the online matrix-vector multiplication conjecture
Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai, and Thatchaphol Saranurak · 2015
Cited alongside, same era.
Jerry Li, Aleksandar Nikolov, Ilya Razenshteyn, and Erik Waingarten · 2019
Later among the works it cites.
Stronger l2/l2 compressed sensing; without iterating
Vasileios Nakos and Zhao Song · 2019
Later among the works it cites.
Efficient symmetric norm regression via linear sketching
Zhao Song, Ruosong Wang, Lin Yang, Hongyang Zhang, and Peilin Zhong · 2019
Later among the works it cites.
Towards a zero-one law for column subset selection
Zhao Song, David Woodruff, and Peilin Zhong · 2019
Later among the works it cites.
Mongoose: A learnable lsh framework for efficient neural network training
Beidi Chen, Zichang Liu, Binghui Peng, Zhaozhuo Xu, Jonathan Lingjie Li, Tri Dao, Zhao Song, Anshumali Shrivastava, and Christopher Re · 2020
Later among the works it cites.
Slide: In defense of smart algorithms over hardware acceleration for large-scale deep learning systems
Beidi Chen, Tharun Medini, James Farwell, Charlie Tai, Anshumali Shrivastava, et al · 2020
Later among the works it cites.
On adaptive distance estimation
Yeshwanth Cherapanamjeri and Jelani Nelson · 2020
Later among the works it cites.
Sublinear least-squares value iteration via locality sensitive hashing
Anshumali Shrivastava, Zhao Song, and Zhaozhuo Xu · 2021
Later among the works it cites.
Zhaozhuo Xu, Zhao Song, and Anshumali Shrivastava · 2021
Later among the works it cites.
Performance of johnson–lindenstrauss transform for k-means and k-medians clustering
Konstantin Makarychev, Yury Makarychev, and Ilya Razenshteyn · 2022
Closest in time.
Sparse fourier transform over lattices: A unified approach to signal reconstruction
Zhao Song, Baocheng Sun, Omri Weinstein, and Ruizhe Zhang · 2022
Closest in time.
Speeding up sparsification with inner product search data structures
Zhao Song, Zhaozhuo Xu, and Lichen Zhang · 2022
Closest in time.