Fast construction of nets in low dimensional metrics, and their applications
By Sariel Har-Peled, Manor Mendel. SCG, 2004
355 citations recorded by the source corpus.
We present a near linear time algorithm for constructing hierarchical nets in finite metric spaces with constant doubling dimension. This data-structure is then applied to obtain improved algorithms for the following problems: Approximate nearest neighbor search, well-separated pair decomposition, spanner construction, compact representation scheme, doubling measure, and computation of the (approximate) Lipschitz constant of a function. In all cases, the running (preprocessing) time is near-linear and the space being used is linear.
View Paper: https://www.semanticscholar.org/paper/a93c0a867dcf4f232c2921999bc0db6c52f17257
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
- J. Langford
- Lihong Li
- Ravi Kumar
- Sergey Levine
- Alisa Chang
- Badih Ghazi
- Alekh Agarwal
- Kenneth L. Clarkson
Citations in the corpus
- Cover trees for nearest neighbor (2006, methodology): “The algorithms in (Krauthgamer & Lee, 2004a) and (Har-Peled & Mendel, 2006) eliminate the dependence on the aspect ratio but do not achieve linear space. single point insertions), and a batch query (which amortizes the query time over multiple queries).”
- Assouad's theorem with dimension independent of the snowflaking (2010, unknown): “[14] S. Har-Peled and M. Mendel.”
- Locally Private k-Means in One Round (2021, methodology): “The main new ingredient in our framework is the use of a hierarchical data structure called a net tree (Har-Peled and Mendel, 2006) to construct a private coreset3 of the input points.”
- Nearest-Neighbor Searching and Metric Space Dimensions (2005, methodology): “This permutation is used in [Cla03] and [ HPM05 ].”
- Geometric Approximation Algorithms (2011, methodology): “work, although it is essentially a simplification of Har-Peled and Mendel [HM04b] data-structure to the case of compressed quadtrees.”
- Measuring Sample Quality with Diffusions (2016, unknown): “More generally, if ‖·‖ is an `p norm, one can construct a 2-spanner with O(κdn) edges in O(κ ′ dn log(n)) expected time where κd is a constant that depends only on the norm ‖·‖ and the dimension d [39].”