Resumen de Analysis of partial match queries in multidimensional search trees
Gustavo Salvador Lau Laynes Lozada
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.
