The analysis of partial match queries in random multidimensional trees: A selected survey
Amalia Duch, Hsien‐Kuei Hwang, Conrado Martı́nez, Ralph Neininger · Computer Science Review · 2026
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.