2026-07-22T13:05:58Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:16094 2024-03-06T10:56:56Z ddc:004 open_access

Partial Match Queries in Quad- K-d Trees Duch, Amalia Martínez, Conrado Quadtree Partial match queries Associative queries Multidimensional search Analysis of algorithms Quad-K-d trees [Bereckzy et al., 2014] are a generalization of several well-known hierarchical K-dimensional data structures. They were introduced to provide a unified framework for the analysis of associative queries and to investigate the trade-offs between the cost of different operations and the memory needs (each node of a quad-K-d tree has arity 2^m for some m, 1 ≤ m ≤ K). Indeed, we consider here partial match - one of the fundamental associative queries - for several families of quad-K-d trees including, among others, relaxed K-d trees and quadtrees. In particular, we prove that the expected cost of a random partial match P̂_n that has s out of K specified coordinates in a random quad-K-d tree of size n is P̂_n ∼ β⋅ n^α where α and β are constants given in terms of K and s as well as additional parameters that characterize the specific family of quad-K-d trees under consideration. Additionally, we derive a precise asymptotic estimate for the main order term of P_{n,𝐪} - the expected cost of a fixed partial match in a random quad-K-d tree of size n. The techniques and procedures used to derive the mentioned costs extend those already successfully applied to derive analogous results in quadtrees and relaxed K-d trees; our results show that the previous results are just particular cases, and states the validity of the conjecture made in [Duch et al., 2016] to a wider variety of multidimensional data structures. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Amalia Duch and Conrado Martínez 2022 Is Part Of LIPIcs, Volume 225, 33rd International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.AofA.2022.8 urn:nbn:de:0030-drops-160949 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2022.8 eng https://creativecommons.org/licenses/by/4.0/legalcode