Suppose we are given a family $F$ of $n$ sets of total cardinality $N$ with elements of the sets drawn from a universe $U$ of size $|U| = d$. Alternately, suppose we have $n$ points in $R^d$, or $n$ $d$-dimensional vectors.


We want to preprocess the sets/points such that we can efficiently report the approximate (Hamming/Minkowski) distance between any two sets/points within a factor of $1 + \epsilon$
What is the best known query time / preprocessing time for this problem?
(Note that we do not make any assumption on the relationship between $d$ and $n$. In particular $d$ is not necessarily sub-linear in $n$)

One approach would be to use a dimension reduction technique in the preprocessing phase, to speed up the query time. For example, we could use some algorithm based on the Johnson–Lindenstrauss lemma to project the points into a $k$ dimensional space first, and later when answering a query, we only spend $k$ time instead of $d$ time to compute the distance between any pair of points.

I think that Alon showed that $k = \Omega(\frac{\log n}{\epsilon^2 \log (1/\epsilon)})$ for the Johnson-Lindenstrauss lemma.

In their STOC'06 paper, Ailon and Chazelle give an algorithm which achieves a nearly matching upper bound of $k = O(\epsilon^{-2} \log n)$ using FJLT with a preprocessing time of $O(n\cdot(d \log d + \epsilon^{-3} \log^2 n))$ for the dimension reduction of all $n$ points under $\ell_1$ distance. Are there any similar approaches which achieve a better preprocessing time?

Are there any alternate approaches that beat the lower bound on $k$? In A sparse Johnson-Lindenstrauss transform, under "Main Results", Dasgupta et al. appear to achieve $k = O(\epsilon^{-2}\log(\frac{1}{ \delta}))$, but I fear I may be misunderstanding that section of the paper.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.