Random projection trees and low dimensional manifolds

By Sanjoy Dasgupta, Yoav Freund. 2008

471 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Representation & Self-Supervised Learning, Signal Processing

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

In Representation & Self-Supervised Learning

In Signal Processing

Citations in the corpus

Maximum inner-product search using cone trees (2012, background): “For exact nearest-neighbor searches, trees can yield great accelerations in anywhere from low- to high-dimensional data, as long as there is low intrinsic dimensionality [4, 10].”
Parseval Networks: Improving Robustness to Adversarial Examples (2017, background): “(Dasgupta & Freund, 2008) which can be measured from the covariance matrix of the data.”
Visualizing Large-scale and High-dimensional Data (2016, methodology): “…2 d ) (with N being the number of data points and d being the number of dimensions) which is too costly, existing approaches use roughly three categories of techniques: space-partitioning trees [3, 10, 21, 7], locality sensitive hashing techniques [8, 6, 12], and neighbor exploring techniques [9].”
Fast approximate spectral clustering (2009, methodology): “RP trees are an alternative to k-means in which a distortionreducing transformation is obtained via random projection s [8].”
Neural Decision Trees (2017, background): “Early stopping can be detrimental by stopping the exploration, known as the horizon effect Duda et al. (2012), a DT can instead be fully developed and then postpruned using some heuristics which is a way to regularize the splits.”
Q-learning with Nearest Neighbors (2018, methodology): “The computation can be potentially sped up by using more efficient data structures and algorithms for finding (approximate) nearest neighbors, such as k-d trees [5], random projection trees [13], Locality Sensitive Hashing [21] and boundary trees [26].”
Multiscale Quantization for Fast Similarity Search (2017, methodology): “Tree based methods [7, 29, 9], graph based methods [16] and locality sensitive hashing style algorithms [19, 1, 32] focus on non-exhaustive search by partitioning the search space.”
Testing the Manifold Hypothesis (2013, background): “We refer the interested reader to a limited set of papers associated with this field; see [3, 8, 9, 11, 16, 20, 26, 31, 32, 41, 43, 47, 50, 52, 55] and the references therein.”
Fast Exact Max-Kernel Search (2012, methodology): “Trees offer good hierarchical indexing schemes in low to medium dimensions; for high-dimensional data, trees which exploit some lowdimensional structure have been developed [17, 16].”
Finding and Leveraging Structure in Learning Problems (2012, result): “Similar manifold adaptivity results have been shown in classification [54] and in non-parametric regression [30, 116].”
Scalable Nearest Neighbor Algorithms for High Dimensional Data (2014, methodology): “Variations of the k-d tree using non-axis-aligned partitioning hyperplanes have been proposed: the PCA-tree [15], the RP-tree [16], and the trinary projection tree [17].”
Milvus: A Purpose-Built Vector Data Management System (2021, background): “Prior works on approximate search can be roughly classified in four categories: LSH-based [23, 23, 24, 32, 40, 44, 45, 48, 73], tree-based [17, 46, 54, 57], graph-based [20, 43, 49, 61, 72], and quantization-based [3, 6, 22, 27, 33, 35].”
Randomized Partition Trees for Nearest Neighbor Search (2015, background): “The resulting structure (Figure 2) is almost exactly the random projection tree (or RP tree) of [10].”
Approximate Nearest Neighbor Search on High Dimensional Data - Experiments, Analyses, and Improvement (v1.0) (2016, background): “In earlier versions, Annoy constructs multiple random projection trees [13].”
Multiresolution Tree Networks for 3D Point Cloud Processing (2018, methodology): “If we choose axes from a random set of directions, it builds an RP-tree [10].”
3D Point Cloud Generative Adversarial Network Based on Tree Structured Graph Convolutions (2019, methodology): “However, this method needed the assumption that inputs are the 1D-ordered lists of points obtained by space-partitioning algorithms such as Kdimensional tree and random projection tree [7].”
Algorithms for Reinforcement Learning (2010, methodology): “Possibilities include using strip-like tilings combined with hash functions, interpolators that use low-discrepancy grids (Lemieux, 2009, Chapter 5 and 6), or random projections (Dasgupta and Freund, 2008).”