Partial match queries in random quadtrees

Nicolas Broutin, Ralph Neininger, Henning Sulzbach

We consider the problem of recovering items matching a partially specified pattern in multidimensional trees (quad trees and k-d trees). We assume the traditional model where the d…