License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.AofA.2018.20
URN: urn:nbn:de:0030-drops-89136
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/8913/
Go to the corresponding LIPIcs Volume Portal

Duch, Amalia ; Lau, Gustavo ; Martínez, Conrado

Fixed Partial Match Queries in Quadtrees

pdf-format:
LIPIcs-AofA-2018-20.pdf (0.6 MB)

Abstract

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.

BibTeX - Entry

@InProceedings{duch_et_al:LIPIcs:2018:8913,
  author =	{Amalia Duch and Gustavo Lau and Conrado Mart{\'i}nez},
  title =	{{Fixed Partial Match Queries in Quadtrees}},
  booktitle =	{29th International Conference on Probabilistic,  Combinatorial and Asymptotic Methods for the Analysis of Algorithms  (AofA 2018)},
  pages =	{20:1--20:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-078-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{110},
  editor =	{James Allen Fill and Mark Daniel Ward},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/8913},
  URN =		{urn:nbn:de:0030-drops-89136},
  doi =		{10.4230/LIPIcs.AofA.2018.20},
  annote =	{Keywords: Quadtree, Partial match queries, Associative queries, Multidimensional search, Analysis of algorithms}
}

Keywords: Quadtree, Partial match queries, Associative queries, Multidimensional search, Analysis of algorithms
Collection: 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018)
Issue Date: 2018
Date of publication: 18.06.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI