The analysis of partial match queries in random multidimensional trees: A selected survey

Computer Science Review 2026 Open access

Read full text
Authors: Amalia Duch, Hsien‐Kuei Hwang, Conrado Martı́nez, Ralph Neininger
DOI: 10.1016/j.cosrev.2026.100904
Cited by: 1
References: 49

Abstract

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.

Fields of Study & Subjects

Data Management and Algorithms Complex Network Analysis Techniques Complexity and Algorithms in Graphs

Publication details

Journal / source
Computer Science Review
Publisher
Elsevier BV
Volume
61
Pages
100904–100904
Publication date
20 February 2026
Language
EN