文章基本信息

标题：Randomly-oriented k-d Trees Adapt to Intrinsic Dimension
本地全文：下载
作者：Santosh S. Vempala
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2012
卷号：18
页码：48-57
DOI：10.4230/LIPIcs.FSTTCS.2012.48
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：The classic k-d tree data structure continues to be widely used in spite of its vulnerability to the so-called curse of dimensionality. Here we provide a rigorous explanation: for randomly rotated data, a k-d tree adapts to the intrinsic dimension of the data and is not affected by the ambient dimension, thus keeping the data structure efficient for objects such as low-dimensional manifolds and sparse data. The main insight of the analysis can be used as an algorithmic pre-processing step to realize the same benefit: rotate the data randomly; then build a k-d tree. Our work can be seen as a refinement of Random Projection trees [Dasgupta 2008], which also adapt to intrinsic dimension but incur higher traversal costs as the resulting cells are polyhedra and not cuboids. Using k-d trees after a random rotation results in cells that are cuboids, thus preserving the traversal efficiency of standard k-d trees.
关键词：Data structures; Nearest Neighbors; Intrinsic Dimension; k-d Tree