Linear-time Algorithms for Pairwise Statistical Problems

By Parikshit Ram, William B. March, Alexander G. Gray. 2009

73 citations recorded by the source corpus.

How researchers see this paper

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

In Optimization & Training

Citations in the corpus

Maximum inner-product search using cone trees (2012, methodology): “The dualtree algorithms have been applied to different tree-based algorithms like nearest-neighbor search [15] and kernel density estimation [16] with theoretical runtime guarantees [31].”
On Estimating L 22 Divergence (2014, methodology): “can be used to compute D̂ in linear time [21].”
Accelerated Hierarchical Density Based Clustering (2017, methodology): “One of the most common techniques for asymptotic performance improvement in the face of pairwise statistical problems (in our case pairwise distance computations) are space tree algorithms [26].”
Fast approximate similarity search based on degree-reduced neighborhood graphs (2011, background): “In these .elds, some applications require to obtain a solution quickly, even if it is not always exact, rather than an exact solution after a long computation time.”
On Estimating $L_2^2$ Divergence (2014, methodology): “can be used to compute D̂ in linear time [17].”
Metric Learning and Manifolds: Preserving the Intrinsic Geometry (2017, background): “However, much work has been devoted to speeding up this task, and approximate algorithms are now available, which can run in linear time in n and have very good accuracy (Ram et al. (2010)).”
Fast Exact Max-Kernel Search (2012, background): “node). However, this makes the tree construction and tree search computational prohibitive for eﬃcient MKS. the time complexities of building and querying a cover trees have been analyzed extensively [16, 25], whereas kdtrees and metric trees have been analyzed only under very limited settings [21].”