Advertisement
Published in:
2006 | OriginalPaper | Chapter
Random Multivariate Search Trees
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
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.