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

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.

• It's been a while, so I don't remember precisely, but on rereading the paper this morning (both the arxiv and journal versions) I couldn't find where it says we keep the pointers you say we need. I thought we were only keeping parent-child pointers and cross-sample pointers. So maybe you could point more precisely to the text in the paper that says what you say it does. – David Eppstein Jun 14 '11 at 5:53
• Hi David, thanks for taking a look. The ANN search is the last section (6). The problem is indicated in fig. 7 (b) which roughly is what I have graphed in the above illustration, if q is somewhere in bottom left. I have edited the question to include the particular part of the text from section 6.3. I have some ideas about how I could be relaxed with the definition of equistabbing maybe, but I'm not sure I can prove that any alternative counting doesn't violate the targeted performance... – 0__ Jun 14 '11 at 11:49
• Ok, that does look like an issue. I'm discussing it with Goodrich (we've lost touch with Sun, who did most of the details here). Our current feeling is that we shouldn't actually need these extra pointers (we don't need them for approx ranges, why should approx neighbors be any different, and it should be possible for the query algorithm to remember the ancestors it saw on the way down rather than using pointers to look them up) but we'll get back to you when we're a little more sure of the details here. – David Eppstein Jun 14 '11 at 16:34
• Great, thank you very much. For reasons of character count and layout, I will add an answer which sketches out my 'intuitive idea', maybe it's a starting point. – 0__ Jun 14 '11 at 16:43

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.

• That's good news! I was just not sure if adding the siblings during the go-down-step would change the bound of the overall worst case cost or not, but I suppose no. I had looked into the paper by Arya et al., but I found it much less accessible than your Quadtree paper :) – 0__ Jun 15 '11 at 19:18
• Wow! Welcome to cstheory.SE! – Hsien-Chih Chang 張顯之 Jun 16 '11 at 1:31

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...

• Yes, and the deterministic variants are a lot like 2-3 trees for the same z-order. – David Eppstein Apr 22 '13 at 3:27
• Thanks for the link, I have seen your paper before, indeed. In any case, I could not empirically verify the bound with the given algorithm. I have a feeling that the reference to Lemma 7, which is used to bound the number of rounds in theorem 13, might be invalid, because it assumes a constant radius $r$, whereas the search radius in the ANN incrementally changes, and so does the set of critical squares. ? – 0__ Apr 22 '13 at 20:35
• The radius definite shrinks during the search process. I am reasonably optimistic the argument is correct. – Sariel Har-Peled Apr 23 '13 at 4:35

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.

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?