2026-07-23T20:44:44Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8913 2024-03-06T10:43:44Z ddc:004 open_access

Fixed Partial Match Queries in Quadtrees Duch, Amalia Lau, Gustavo Martínez, Conrado Quadtree Partial match queries Associative queries Multidimensional search Analysis of algorithms Several recent papers in the literature have addressed the analysis of the cost P_{n,q} of partial match search for a given fixed query q - that has s out of K specified coordinates - in different multidimensional data structures. Indeed, detailed asymptotic estimates for the main term in the expected cost P_{n,q} = E {P_{n,q}} in standard and relaxed K-d trees are known (for any dimension K and any number s of specified coordinates), as well as stronger distributional results on P_{n,q} for standard 2-d trees and 2-dimensional quadtrees. In this work we derive a precise asymptotic estimate for the main order term of P_{n,q} in quadtrees, for any values of K and s, 0 < s < K, under the assumption that the limit of P_{n,q}/n^alpha when n -> infty exists, where alpha is the exponent of n in the expected cost of a random partial match query with s specified coordinates in a random K-dimensional quadtree. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Amalia Duch and Gustavo Lau and Conrado Martínez 2018 Is Part Of LIPIcs, Volume 110, 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.AofA.2018.20 urn:nbn:de:0030-drops-89136 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2018.20 eng https://creativecommons.org/licenses/by/3.0/legalcode