Universitat Politècnica de Catalunya
Universitat Politècnica de Catalunya. Departament de Ciències de la Computació
Universitat Politècnica de Catalunya. ALBCOM - Algorísmia, Bioinformàtica, Complexitat i Mètodes Formals
2026-08
We analyze the probabilistic performance of partial match queries in random multidimensional search trees, using k-d trees (and their variants) and quadtrees, as primary examples. A partial match query aims to retrieve all points from a tree that match a given query point on a predetermined subset of coordinates. As one of the most basic associative searches, its analysis is foundational for evaluating more complex queries. This selection of data structures allows us to demonstrate common analytical techniques and offer a historical perspective on the field.
The work of Amalia Duch and Conrado Martínez has been supported by funds from the MOTION Project (Project PID2020-112581GB-C21) of the Spanish Ministry of Science and Innovation MCIN/AEI/10.13039/501100011033.
Peer Reviewed
Postprint (published version)
Article
English
Àrees temàtiques de la UPC::Informàtica::Informàtica teòrica; Multidimensional data structures; k-dimensional trees; Quadtrees; Partial match queries; Associative queries
Elsevier
https://www.sciencedirect.com/science/article/pii/S1574013726000134
info:eu-repo/grantAgreement/AEI/Plan Estatal de Investigación Científica y Técnica y de Innovación 2017-2020/PID2020-112581GB-C21/ES/MODELOS Y TECNICAS PARA EL PROCESAMIENTO DE INFORMACION A GRAN ESCALA -- BARCELONA/
http://creativecommons.org/licenses/by-nc-nd/4.0/
Open Access
Attribution-NonCommercial-NoDerivatives 4.0 International
E-prints [72399]
