Partial match queries in relaxed multidimensional search trees

Partial match queries arise frequently in the context of large databases, where each record contains a distinct multidimensional key, that is, the key of each record is a K-tuple of values. The components of a key are called the coordinates or attributes of the key. In a partial match query we specify the value of s attributes, 0 < s < K, and leave the remaining K - s attributes unspecified. The goal is to retrieve all the records in the database that match the specified attributes. In this paper we present several results about the average performance and variance of partial matches in relaxed K-dimensional trees (search trees and digital tries). These data structures are variants of the well known K d-trees and K d-tries. In relaxed trees the sequence of attributes used to guide a query is explicitly stored at the nodes of the tree and randomly generated and, in general, will be different for different search paths. In the standard variants, the sequence of attributes that guides a query examines the attributes in a cyclic fashion, fixed and identical for all search paths. We show that the probabilistic analysis of the relaxed multidimensional trees is very similar to that of standard K d-trees and K d-tries, and also to the analysis of quadtrees. In fact, besides the average cost and variance of partial match in relaxed K d-trees and K d-tries, we also obtain the variance of partial matches in two-dimensional quadtrees. We also compute the average cost of partial matches in other relaxed multidimensional digital tries, namely, relaxed K d-Patricia and relaxed K d-digital search tree