Partial match retrieval of multidimensional data
Philippe Flajolet, Claude P. Puech · Journal of the ACM · 1986
A precise analysis of partial match retrieval of multidimensional data is presented. The structures considered here are multidimensional search trees ( k -d-trees) and digital tries ( k -d-tries), as well as structures designed for efficient retrieval of information stored on external devices. The methods used include a detailed study of a differential system around a regular singular point in conjunction with suitable contour integration techniques for the analysis of k -d-trees, and properties of the Mellin integral transform for k -d-tries and extendible cell algorithms.