DROPS

Document

DOI: 10.4230/LIPIcs.AofA.2022.8

Partial Match Queries in Quad- K-d Trees

Authors: Amalia Duch and Conrado Martínez

Published in: LIPIcs, Volume 225, 33rd International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2022)

Abstract

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.

Cite as

Amalia Duch and Conrado Martínez. Partial Match Queries in Quad- K-d Trees. In 33rd International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 225, pp. 8:1-8:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{duch_et_al:LIPIcs.AofA.2022.8,
  author =	{Duch, Amalia and Mart{\'\i}nez, Conrado},
  title =	{{Partial Match Queries in Quad- K-d Trees}},
  booktitle =	{33rd International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2022)},
  pages =	{8:1--8:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-230-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{225},
  editor =	{Ward, Mark Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2022.8},
  URN =		{urn:nbn:de:0030-drops-160949},
  doi =		{10.4230/LIPIcs.AofA.2022.8},
  annote =	{Keywords: Quadtree, Partial match queries, Associative queries, Multidimensional search, Analysis of algorithms}
}

Document

DOI: 10.4230/LIPIcs.AofA.2018.20

Fixed Partial Match Queries in Quadtrees

Authors: Amalia Duch, Gustavo Lau, and Conrado Martínez

Published in: LIPIcs, Volume 110, 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018)

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.

Cite as

Amalia Duch, Gustavo Lau, and Conrado Martínez. Fixed Partial Match Queries in Quadtrees. In 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 110, pp. 20:1-20:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{duch_et_al:LIPIcs.AofA.2018.20,
  author =	{Duch, Amalia and Lau, Gustavo and Mart{\'\i}nez, Conrado},
  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 =	{Fill, James Allen and Ward, Mark Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2018.20},
  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}
}

Search Results

Documents authored by Duch, Amalia

Partial Match Queries in Quad- K-d Trees

Abstract

Cite as

Fixed Partial Match Queries in Quadtrees

Abstract

Cite as

Thanks for your feedback!

Could not send message