WRITTEN IN SEP 2010: Dave Mount gave a brilliant talk at today's internal UMCP theory day on a joint paper he wrote with Sunil Arya and Guilherme da Fonseca. I actually understood it! It is a perfect example of something that is so simple, clever, obvious-after-you-see-it, and useful that it might not get into STOC. Dave thought it would not get in for this reason. I am less sure. However, Dave Mount and I agree that when the decision is made I will blog about it. If the paper gets in it will be an anecdote that counters the only-complicated-papers-get-into-STOC notion. If the paper does not get in then it will be an anecdote that supports this notion. Either way I get a post out of it and Dave, Sunil, and Guilherme get publicity for their results (either in anger or in joy).
Here is the problem of interest and their variant on it.
- Given a set S of n points in d-dim space create a data structure so that the question: given point q, find the point p in S that is closest to q. We want low space and quick time. This seems hard to achieve.
- Given a set S of n points in d-dim space, and a parameter ε, create a data structure so that the question: given point q, find the point p in S that is at worst (1+ε)OPT away from q. This is called Approx Nearest Neighbor. We call it ANN.
Here is what was known: In Space-Time Tradeoffs for approximate nearest neighbor searching, by Arya, Malamatos, Mount, they showed a very complicated algorithm that did the following. View d as being constant. S is a set of n points in d-dim space. ε is also an input.
Let γ be a tradeoff parameter with 2 ≤ γ ≤ 1/ε.
There is a data structure for ANN with
- space O(n γd-1log(1/ε)), and
- query time O(log(nγ) + 1/(ε γ)(d-1)/2).
- If γ=2 then space O(nlog(1/ε)) and query time O(log n + 1/ε(d-1)/2).
The new result was an improvement and was easy to code and use. I won't state it since it is not easy to typeset (AH HA- maybe being hard to typeset will give them an edge) but here is the paper: Approximate Polytope Membership Queries, (CONFESSION: that very last link was revised in July 2011, but the rest was written in SEPT 2010.)
WRITTEN IN FEB 2011: CONGRATS to Dave, Sunil, and Guil. Their paper got in. That's one anecdote against the notion that STOC does not nice simple ideas. If YOU (the reader) have some other ones, please leave them as comments.
WRITTEN IN JUNE 2011: The STOC talk was EXCELLENT. Here are the slides.