Analysis of partial match queries in multidimensional search trees

Abstract

The main contribution of this thesis is to deepen and generalize previous work done in the average-case analysis of partial match queries in several types of multidimensional search trees. In particular, our focus has been the analysis of fixed PM queries. Our results about them generalize previous results which covered the case where only one coordinate is specified in the PM query- and for any dimension-or the case of 2-dimensional data structures. Using a combinatorial approach, different to the probabilistic approaches used by other researchers, we obtain asymptotic formulas for the expected cost of fixed PM queries in relaxed and standard K-d trees. We establish that, in both cases, the expected cost satisfies a common pattern in the relationship with the expected cost of random PM queries. Moreover, the same pattern appeared in the analysis, previously done by other researchers, of the expected cost of fixed partial match in 2-dimensional quad trees. Those results led us to conjecture that such formula would be pervasive to describe the expected cost of partial match queries in many different multidimensional trees, assuming some additional technical conditions about the family of multidimensional search trees under consideration. Indeed, we prove this to be the case also for K-dimensional quad trees. However, we disprove that conjecture for a new variant of K-d trees with local balancing that we define: relaxed K-dt trees. We analyze the expected cost of random PM queries and fixed PM queries in them and, while we do not find a closed-form expression for the expected cost of xed PM queries, we prove that it cannot be of the same form that we had conjectured. For random PM queries in both relaxed and standard K-dt trees, we obtain two very general results that unify several specific results that appear scattered across the literature. Finally, we also analyze random PM queries in quad-K-d trees -a generalization of both quad trees and K-d trees- and obtain a very general result that includes as particular cases previous results in relaxed K-d trees and quad trees.

La principal contribución de esta tesis es profundizar y generalizar resultados anteriores referentes al análisis en caso medio de búsquedas parciales en varios tipos de árboles multidimensionales de búsqueda. En particular nos enfocamos en el análisis de búsquedas parciales fijas. Nuestros resultados sobre ellas generalizan resultados previos que cubren el caso donde solamente una coordenada es especificada en la búsqueda parcial-y para cualquier dimensión-o el caso de estructuras de datos de dos dimensiones. Usando un enfoque combinatorio, diferente a los enfoques probabilísticos utilizados por otros investigadores, obtenemos fórmulas asintóticas para el costo esperado de búsquedas parciales fijas en árboles K-d relajados y estándares. Establecemos que, en ambos casos, el costo esperado satisface un patrón común en la relación con el costo esperado de búsquedas parciales aleatorias. Además, el mismo patrón apareció en el análisis, previamente hecho por otros investigadores, del costo esperado de búsquedas parciales fijas en quadtrees de dos dimensiones. Esos resultados nos llevaron a conjeturar que tal fómula sería generalizada para describir el costo esperado de consultas de búsqueda parcial en muchos árboles multidimensionales diferentes, asumiendo algunas condiciones técnicas adicionales sobre la familia de árboles multidimensionales de búsqueda bajo consideración. De hecho, demostramos que este también es el caso en quadtrees de K dimensiones. Sin embargo, definimos una nueva variante de árboles K-d con reorganizacion local que cumplen tales condiciones, los árboles K-dt relajados, analizamos el costo esperado de búsquedas parciales aleatorias y fijas en ellos y, aunque no encontramos una expresión cerrada para el coste esperado de las búsquedas parciales fijas, demostramos que no puede ser de la misma forma que habíamos conjeturado. También obtenemos dos resultados muy generales para busquedas parciales aleatorias en árboles K-dt relajados y estándares que unifican varios resultados específicos que aparecen dispersos en la literatura. Finalmente, analizamos búsquedas parciales aleatorias en una generalizacion de quadtrees y árboles K-d, llamada árboles quad-K-d, y obtenemos un resultado general que incluye como casos particulares resultados previos en árboles K-d relajados y quadtrees.

Són moltes les aplicacions en què es requereix administrar col·leccions de dades multidimensionals, en les quals cada objecte és identificat per un punt en un espai real o abstracte; un exemple paradigmàtics són els sistemes d’informació geogràfica. Aquestes aplicacions fan servir sovint estructures de dades multidimensionals que permetin consultes associatives -aquelles on s'especifiquen condicions per a més d'una coordenada- a més de les operacions tradicionals d’inserció, actualització, eliminació i cerca exacta. Un dels principals tipus de consultes associatives és la cerca parcial, on només s'especifiquen algunes coordenades i l'objectiu és determinar quins objectes coincideixen amb elles. Les consultes de cerca parcial són particularment importants perquè la seva anàlisi forma la base de l’anàlisi d'altres tipus de consultes associatives, com ara les cerques per rangs ortogonals (quins punts estan dins d'una àrea (hiper)rectangular donada?), les consultes per regió (per exemple, donats un punt i una distància, quins punts estan a aquesta distància o menys d'aquest punt?) o les consultes del veí més proper (on cal trobar els k punts més propers a un punt donat). En aquesta tesi analitzem en profunditat el rendiment mitjà de les cerques parcials en arbres multidimensionals de cerca representatius, els quals constitueixen una subclasse significativa de les estructures de dades multidimensionals. Els arbres multidimensionals de cerca, en particular els quadtrees i els arbres K-d, van ser definits a mitjans de la dècada dels anys 1970 com una generalització dels arbres binaris de cerca. Les consultes de cerca parcial s'hi responen realitzant un recorregut recursiu d'alguns subarbres. Durant molts anys l’anàlisi en arbres multidimensionals de cerca es va fer amb la suposició important, i sovint implícita, que en cada crida recursiva es generen a l'atzar noves coordenades de la consulta de cerca parcial. La raó d'aquesta suposició simplificadora va ser que, per als costos mitjans, aquesta anàlisi és equivalent a analitzar el rendiment de l'algorisme de cerca parcial quan l'entrada és una consulta de cerca parcial aleatòria. A principis d'aquesta dècada, alguns equips van començar a analitzar el cas mitjà de cerques parcials sense aquesta suposició: les coordenades especificades de la consulta romanen fixes durant totes les crides recursives. Aquestes consultes s'anomenen cerques parcials fixes. L'objectiu d'aquest enfocament recent és analitzar el rendiment de l'algorisme de cerca parcial, però ara les quantitats d’interès depenen de la consulta particular q donada com a entrada. L’anàlisi de cerques parcials fixes, juntament amb el de les aleatòries -que té un paper important per a l’anàlisi de les primeres- ens dóna una descripció molt detallada i precisa del rendiment de l'algorisme de cerca parcial que podria ser estesa a altres consultes associatives rellevants. La principal contribució d'aquesta tesi és aprofundir i generalitzar resultats previs referents a l’anàlisi en cas mitjà de les cerques parcials en diversos tipus d'arbres multidimensionals de cerca. En particular ens enfoquem en l’anàlisi de les cerques parcials fixes. Els nostres resultats en generalitzen resultats previs els quals cobreixen el cas on només una coordenada està especificada a la cerca parcial i per a qualsevol dimensió no el cas d'estructures de dades de dues dimensions. Usant un enfocament combinatori, diferent als enfocaments probabilístics utilitzats per altres investigadors, obtenim fórmules asimptòtiques per al cost esperat de cerques parcials fixes en arbres K-d relaxats i estàndards. Establim que, en tots dos casos, el cost esperat satisfà un patró comú en la relació amb el cost esperat de cerques parcials aleatòries. A més, el mateix patró va aparèixer en l’anàlisi, prèviament fet per altres investigadors, del cost esperat de cerques parcials fixes en quadtrees de dues dimensions. Aquests resultats ens van portar a conjecturar que tal fórmula seria general per descriure el cost esperat de consultes de cerca parcial en molts arbres multidimensionals diferents, assumint algunes condicions tècniques addicionals sobre la família d'arbres multidimensionals de cerca sota consideració. De fet, demostrem que aquest és també el cas pels quadtrees de K dimensions. Tanmateix, definim una nova variant de arbres K-d amb equilibri local que compleixen aquestes condicions, els arbres K-dt relaxats, n'analitzem el cost esperat de cerques parcials aleatòries i fixes i, tot i no trobar una expressió tancada per al cost esperat de les cerques parcials fixes, demostrem que no pot ser de la mateixa forma que havíem conjecturat. També obtenim dos resultats molt generals per a les cerques parcials aleatòries en arbres K-dt relaxats i estàndards, els quals unifiquen diversos resultats específics que apareixen dispersos a la literatura. Finalment, analitzem cerques parcials aleatòries en una generalització de quadtrees i arbres K-d, anomenada arbres quad-K-d, i obtenim un resultat general que inclou com a casos particulars resultats previs en arbres K-d relaxats i quadtrees