Random Multivariate Search Trees
Abstract
Trees are commonly used to store data so that they can be efficiently retrieved and used in applications. For multidimensional data, one could consider kd-trees, quadtrees, BSP trees, simplex trees, grid trees, epsilon nets, and many other structures. The height of these trees is logarithmic in the data size for random input. Some search operations such as range search and nearest neighbor search have surprising complexities. So, we will give a brief survey of the known results on random multivariate trees and point out the challenges ahead of us.
Cite
Text
Devroye. "Random Multivariate Search Trees." Annual Conference on Computational Learning Theory, 2006. doi:10.1007/11776420_1Markdown
[Devroye. "Random Multivariate Search Trees." Annual Conference on Computational Learning Theory, 2006.](https://mlanthology.org/colt/2006/devroye2006colt-random/) doi:10.1007/11776420_1BibTeX
@inproceedings{devroye2006colt-random,
title = {{Random Multivariate Search Trees}},
author = {Devroye, Luc},
booktitle = {Annual Conference on Computational Learning Theory},
year = {2006},
pages = {1},
doi = {10.1007/11776420_1},
url = {https://mlanthology.org/colt/2006/devroye2006colt-random/}
}