2
$\begingroup$

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.

Question:

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.

$\endgroup$

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.