Timezone: »

Random Projection Trees Revisited
Aman Dhesi · Purushottam Kar

Wed Dec 08 12:00 AM -- 12:00 AM (PST) @

The Random Projection Tree (RPTree) structures proposed in [Dasgupta-Freund-STOC-08] are space partitioning data structures that automatically adapt to various notions of intrinsic dimensionality of data. We prove new results for both the RPTree-Max and the RPTree-Mean data structures. Our result for RPTree-Max gives a near-optimal bound on the number of levels required by this data structure to reduce the size of its cells by a factor s >= 2. We also prove a packing lemma for this data structure. Our final result shows that low-dimensional manifolds possess bounded Local Covariance Dimension. As a consequence we show that RPTree-Mean adapts to manifold dimension as well.

Author Information

Aman Dhesi (Princeton University)
Purushottam Kar (Indian Institute of Technology Kanpur)

More from the Same Authors