Coûts d'exécution env. recherche du plus proche voisin dans un quadruple saut

REMARQUE : La question a été reformulée dans mes réponses: en supposant maintenant que nous pouvons trouver les ancêtres frères les plus bas en , l'ANN peut-il vraiment être exécuté en ?O ( log n $O(1)$$O(\log n)$

Les Quadtrees sont des indices spatiaux efficaces. J'ai un casse-tête avec l'implémentation d'une recherche de voisin le plus proche dans une structure à quatre arbres compressée comme décrit dans [2]. (Sans entrer dans les détails, la recherche va de haut en bas le long de carrés dits équidistants, se terminant par le nœud de queue d'un chemin équidistant. Dans l'image jointe, il peut s'agir de n'importe lequel des nœuds du sud-est remplis de points.)

Pour que leur algorithme fonctionne, il faut maintenir pour chaque nœud - un carré avec au moins deux quadrants non vides - des pointeurs pour chaque nœud ancêtre le plus bas (le plus proche dans la hiérarchie) dans chacune des quatre directions (nord, ouest, sud , est). Ceux-ci sont indiqués par les flèches vertes pour l'ancêtre des nœuds vers l'ouest (la flèche pointe au centre du carré des ancêtres).

Le document prétend que ces pointeurs peuvent être mis à jour dans O (1) lors des insertions et suppressions de points. Cependant, quand on regarde l'insertion du point vert, il semble que je doive mettre à jour n'importe quel nombre arbitraire de pointeurs, dans ce cas six d'entre eux.

J'espère une astuce pour faire cette mise à jour du pointeur en temps constant. Peut-être existe-t-il une forme d'indirection qui peut être exploitée?

ÉDITER:

La section pertinente de l'article est 6.3, où il se lit: "si le chemin a des virages, alors en plus du ancêtres les plus bas de , nous devrions également considérer pour chacune des directions la plus basse ancêtre de qui va dans cette direction [...] Trouver ces carrés à partir de peut être fait en fois par carré si nous associons pointeurs supplémentaires à chaque carré dans pointant vers ses ancêtres les plus proches pour chaque direction . Ces pointeurs peuvent également être mis à jour en temps lors de l'insertion ou de la suppression d'un point. "q q O ( 1 ) 2 d Q 0 O ( 1 $log(c/ε)$$q$$2^d$$q$$q$$O(1)$$2^d$$Q_0$$O(1)$

[2]: Eppstein, D. et Goodrich, MT et Sun, JZ, «The Skip Quadtree: A Simple Dynamic Data Structure for Multidimensional Data», dans Actes du vingt et unième symposium annuel sur la géométrie informatique, pp. 296—305 , 2005.

Comme David, je ne sais pas pourquoi Jonathan a fait cette remarque sur les 2 ^ d pointeurs. Ils ne sont pas nécessaires. Comme David l'a mentionné ci-dessus, la propriété essentielle est que lorsque nous effectuons un emplacement de point sur une feuille v dans Q_0, il suffit de se souvenir des nœuds frères (et de leurs boîtes) dans le saut d'arbre. Lorsque nous traitons une boîte à partir de P, nous faisons un emplacement de point pour la boîte à feuilles la plus proche de notre point de requête, en insérant les boîtes frères au fur et à mesure. Il semble que ce serait plus ou moins la même chose que votre réponse. De plus, cette procédure est très similaire, par exemple, à la façon dont la localisation approximative des points est effectuée dans l'article suivant: Arya, Sunil and Mount, David M. et Netanyahu, Nathan S.et Silverman, Ruth and Wu, Angela Y., "Un algorithme optimal pour le voisin le plus proche recherchant des dimensions fixes", JACM, 1998. En effet,

On peut penser à ignorer quadtree comme une implémentation de liste de saut d'une structure de données stockant les points selon leur ordre z. C'est (sans doute) au moins conceptuellement plus simple ...

Voir le chapitre 2 ici: http://goo.gl/pLiEO .

Et oui, en supposant que vous puissiez effectuer certaines opérations de base de l'ordre z en temps constant, vous pouvez certainement faire ANN en temps logarithmique. Le chapitre susmentionné montre également qu'il n'y a aucun moyen d'éviter d'avoir des opérations bizarres si l'on veut des arbres quadratiques compressés. Notez que l'opération LCA n'est pas nécessaire ...

Je pense aussi intuitivement que l'on pourrait vivre sans ces pointeurs, et comme je dois persister tous les nœuds sur le disque dur à un moment donné, toute réduction des pointeurs est grande.

Mon idée est à peu près la suivante: à part le meilleur point candidat (feuille) , nous gardons également une trace de la pire distance à chaque tour, . Une pire distance serait le maximum des distances de tous les coins d'un nœud au point de requête , peu importe si est à l'intérieur d'un carré ou à l'extérieur. r m a x d i s t ′ ( v , q ) q v $l_{best}$$r_{max}$${dist}'(v,q)$$q$$v$$v$

Un tour est comme ceci: Si est vide, retournez le , s'il y en avait. Sinon, delete-min donne le actuel dans . Initialisez à (ou définissez-le sur si aucun meilleur candidat n'a encore été observé). Tout d'abord, testez chaque enfant non vide de dans . Si cet enfant est une feuille, mettez à jour et si nécessaire. Si est un nœud, calculez et , ce dernier étant la meilleure distance: Soit zéro, si$P$$l_{best}$$p_0$$Q_0$$r_{max}$$l_{best}$$\infty$$p_0$$Q_0$$q$$l_{best}$$r_{max}$$q$${dist}'(q,v)$${dist}(q,v)$$v$ se trouve à l'intérieur de , ou la distance la plus courte de tous les coins de à .$q$$q$$v$

Si , oubliez , sinon conservez-le. Si le nombre de nœuds est maintenu , pousser les noeuds sur . Fin de manche. q ≥ 2 ${dist}(q,v) > r_{max}$$q$$\geq 2$$P$

Sinon, procédez de manière similaire à la recherche d'origine: recherchez , le nœud correspondant à dans le le plus élevé possible , et commencez à partir de là: Encore une fois, au lieu de demander à un enfant équidistant de descendre, testez tous les enfants selon la procédure précédente , c'est-à-dire ignorer ceux dont la meilleure distance dépasse . Si après ce test un enfant est resté, descendez-y et recommencez. Si aucun enfant n'est resté, passez à et répétez. Si le test a été effectué en , la manche est terminée.p 0 Q j r m a x Q j - 1 Q $q$$p_0$$Q_j$$r_{max}$$Q_{j-1}$$Q_0$

En ce moment, je ne sais ni si cela garantit de trouver le plus proche voisin dans tous les cas possibles, ni qu'il fonctionne aussi bien que l'algorithme d'origine. Aussi si l'initialisation de est suffisante ou non. Et quelle devrait être la priorité en - toujours la meilleure distance?$r_{max}$$P$

EDIT (avril 2013)

J'ai maintenant mené plus d'expériences avec une clarification de l'algorithme ci-dessus qui utilise une définition de nœuds `` équipotents '' au lieu de nœuds d'équilibrage, en se basant sur la propriété selon laquelle la descente vers un tel nœud ne change pas la zone couverte par la forme de requête actuelle de l'étendue .$r_{max}$

Malheureusement, on peut construire des cas pathologiques (voir l'image ci-dessous; le point de requête est en bas au centre) où les performances se dégradent en tours.$O(\sqrt n)$

J'ai maintenant implémenté l'algorithme basé sur l'équistabbing, où les ancêtres frères les plus bas sont recherchés en force brute (avant d'essayer de trouver une variante O (1)), afin de vérifier le nombre maximal de tours revendiqués dans le théorème 13: .$O(\epsilon^{1−d}(\log n+\log \epsilon^{−1}))$

J'utilise l'exemple "pathologique" de ma réponse précédente. Le carré racine bidimensionnel a une longueur de côté de 512, où la coordonnée centrale est (256, 256). Les coordonnées sont données en nombres entiers, menant à un simple . Les points sont placés également espacés horizontalement à travers le carré racine, et le point de requête est à (256, 511) (notez que 512 est déjà en dehors du carré racine).$\epsilon = 1$$v$

Dans la figure ci-dessous, l'arborescence complète est affichée, et le nombre de points dans cet exemple est 16. Les contours carrés bleus indiquent les carrés intéressants qui sont poussés dans la file d'attente prioritaire, et les chiffres en leur centre indiquent le numéro rond dans qu'ils sont poussés. Les points foliaires découverts sont également étiquetés avec le numéro rond dans lequel ils sont comptabilisés. Les trois cercles bleus transparents indiquent le rayon NN connu après le 1er, le 2e et le 7e tour (le voisin le plus proche est vu pour la première fois au 7e tour). Il y a 12 tours au total (les 6 derniers carrés pop seulement de la file d'attente, mais n'ajoutez pas de nouveaux carrés).$Q_0$

J'ai exécuté cet exemple avec une série de carrés racines de plus en plus grands et un nombre de points, où l'espacement des points est resté le même (32). Cela a confirmé ce qui est déjà intuitivement visible dans l'illustration: l'algorithme a besoin de tours, tandis que le théorème 13 avec et indique que seuls tours seraient nécessaires.d=2ϵ=1O(logn$O(\sqrt n)$$d = 2$$\epsilon = 1$$O(\log n)$

Donc, à moins que je manque quelque chose de crucial, l'algorithme ne peut pas atteindre la vitesse indiquée. Des commentaires ou des idées?