Costs of performing approx. nearest neighbor search in a skip quadtree

Question

NOTE: The question has been restated in my answers: Assuming now that we can find the lowest sibling ancestors in $O(1)$ time, can the ANN be really performed in $O(\log n)$?

---

Quadtrees are efficient spatial indices. I have a puzzle with the implementation of a nearest neighbour search in a compressed quadtree structure as described in [2]. (Without going into details, the search is going top-down along so-called equidistant squares, ending in the tail node of an equidistant path. In the attached image this might be any of the nodes in the southeast filled with points.)

For their algorithm to work, one must maintain for each node -- a square with at least two non-empty quadrants -- pointers for each lowest (closest in the hierarchy) ancestor node in each of the four directions (north, west, south, east). These are indicated by the green arrows for the nodes' westward ancestor (the arrow points at the ancestor square's centre).

The paper claims these pointers can be updated in O(1) during point insertions and deletions. However when looking at the insertion of the green point, it seems I need to update any arbitrary number of pointers, in this case six of them.

I am hoping for a trick to do this pointer update in constant time. Maybe there is a form of indirection that can be exploited?

EDIT:

The relevant section from the paper is 6.3, where it reads: "if the path has bends, then in addition to the $log(c/ε)$ lowest ancestors of $q$, we should also consider for each of the $2^d$ directions the lowest ancestor of $q$ that goes towards that direction [...] Finding these squares from $q$ can be done in $O(1)$ time per square if we associate additional $2^d$ pointers to each square in $Q_0$ pointing to its closest ancestors for each direction. These pointers can also be updated in $O(1)$ time during an insertion or deletion of a point."

[2]: Eppstein, D. and Goodrich, M.T. and Sun, J.Z., “The Skip Quadtree: A Simple Dynamic Data Structure for Multidimensional Data,” in Proceedings of the twenty-first annual symposium on Computational geometry, pp. 296—305, 2005.

Answer 1

Like David, I don't know why Jonathan put in that remark about the 2^d pointers. They are not needed. As David mentioned above, the essential property is that when we are doing a point location to a leaf v in Q_0, it is sufficient to remember the sibling nodes (and their boxes) in the skip quadtree. When we process a box from P, we do a point location for the leaf box closest to our query point, inserting the sibling boxes as we go down. It sounds like this would be more or less the same as your answer. In addition, this procedure is very similar, for instance, to how approximate point location is done in the following paper: Arya, Sunil and Mount, David M. and Netanyahu, Nathan S. and Silverman, Ruth and Wu, Angela Y., "An optimal algorithm for approximate nearest neighbor searching fixed dimensions", JACM, 1998. Indeed, the skip quadtree (without those extra pointers) satisfies their conditions (a)-(e) that allow for fast approximate nearest-neighbor searching.

Answer 2

One can think about skip quadtree as a skip-list implementation of a data-structure storing the points according to their z-order. It is (arguably) at least conceptually simpler...

See chapter 2 here: http://goo.gl/pLiEO .

And yes, assuming you can perform some basic z-order operations in constant time, you can definitely do ANN in logarithmic time. The aforementioned chapter also shows that there is no way to avoid having bizarre operations if one wants compressed quadtrees. Note, that LCA operation is not necessary...

Answer 3

I also intuitively feel that one could live without those pointers, and as I need to persist all the nodes to harddisk at some point, any reductions in pointers is great.

My idea is roughly as follows: Apart from the best candidate point (leaf) $l_{best}$, we also keep track of the worst distance in each round, $r_{max}$. A worst distance ${dist}'(v,q)$ would be the maximum of the distances of all corners of a node $q$ to the query point $v$, no matter if $v$ is inside a square or outside.

A round is like this: If $P$ is empty, return the $l_{best}$, if there was any. Otherwise delete-min gives the current $p_0$ in $Q_0$. Initialize $r_{max}$ to $l_{best}$ (or set it to $\infty$ if no best candidate had been observed yet). First, test each non-empty child of $p_0$ in $Q_0$. If this child $q$ is a leaf, update the $l_{best}$ and $r_{max}$ if necessary. If $q$ is a node, calculate ${dist}'(q,v)$ and ${dist}(q,v)$, the latter being the best distance: Either zero, if $v$ lies inside $q$, or the shortest distance of all corners of $q$ to $v$.

If ${dist}(q,v) > r_{max}$, forget $q$, otherwise keep it. If the number of nodes kept is $\geq 2$, push those nodes onto $P$. End of round.

Otherwise, proceed similar to the original search: Find $q$, the corresponding node to $p_0$ in the highest possible $Q_j$, and begin from there: Again, instead of asking for an equidistant child to descend to, test all the children according to the previous procedure, that is, skip those whose best distance exceeds $r_{max}$. If after this test a child remained, descend to it and repeat. If no child remained, go to $Q_{j-1}$ and repeat. If the test was performed in $Q_0$, the round is finished.

At this moment, I know neither if this guarantees to find the nearest neighbour in every possible case, nor that it performs as good as the original algorithm. Also if the initialization of $r_{max}$ is sufficient or not. And what should be the priority in $P$ -- still the best distance?

---

EDIT (April 2013)

I have now conducted more experiments with a clarification of the above algorithm which uses a definition of 'equipotent' nodes instead of equistabbing nodes, based on the property that descending to such a node does not change the area covered by the current query shape of extent $r_{max}$.

Unfortunately, one can construct pathological cases (see image below; query point is bottom centre) where performance degrades to $O(\sqrt n)$ rounds.

Answer 4

I have now implemented the equistabbing based algorithm, where the lowest sibling ancestors are searched brute-force (before trying to find a O(1) variant), in order to verify the maximum number of rounds claimed in theorem 13: $O(\epsilon^{1−d}(\log n+\log \epsilon^{−1}))$.

I am using the "pathological" example from my previous answer. The 2-dimensional root square has a side length of 512, where the centre coordinate is (256, 256). Coordinates are given in integers, leading to a straight forward $\epsilon = 1$. The points are placed equally spaced horizontally across the root square, and the query point $v$ is at (256, 511) (note that 512 is already outside the root square).

In the figure below, the full tree $Q_0$ is shown, and the number of points in this example is 16. The blue square outlines indicate the interesting squares which are pushed onto the priority queue, and the digits in their centre indicate the round number in which they are pushed. Leaf points discovered are also labelled with the round number in which they are accounted for. The three transparent blue circles indicate the known NN radius after the 1st, the 2nd, and the 7th round (the nearest neighbour is first seen in the 7th round). There are 12 rounds in total (the last 6 only pop squares from the queue, but do not add any new squares).

I have run this example with a series of increasingly large root squares and number of points, where the spacing of the points remained the same (32). This confirmed what is already intuitively visible from the illustration: The algorithm needs $O(\sqrt n)$ rounds, whereas theorem 13 with $d = 2$ and $\epsilon = 1$ states that only $O(\log n)$ rounds would be needed.

So unless I am missing something crucial, the algorithm cannot achieve the stated speed. Any comments or ideas?