Fast Construction of Nets in Low Dimensional Metrics, and Their Applications

Abstract

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, 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.

41 pages. Extensive clean-up of minor English errors

References in corpus (2)

• On metric Ramsey-type phenomena
• Coresets for $k$-Means and $k$-Median Clustering and their Applications

Cited by in corpus (46)

• Measuring Sample Quality with Stein's Method
• Ramsey partitions and proximity data structures
• Demand-Aware Network Designs of Bounded Degree
• Linear-Space Approximate Distance Oracles for Planar, Bounded-Genus, and Minor-Free Graphs
• Maximum Margin Multiclass Nearest Neighbors
• New Constructions of SSPDs and their Applications
• A Nonlinear Approach to Dimension Reduction
• Fast Clustering with Lower Bounds: No Customer too Far, No Shop too Small
• Greedy Strategy Works for $k$-Center Clustering with Outliers and Coreset Construction
• Mutiscale Mapper: A Framework for Topological Summarization of Data and Maps
• A light metric spanner
• Maximum gradient embeddings and monotone clustering
• A Practical Index Structure Supporting Fréchet Proximity Queries Among Trajectories
• Towards Metric DBSCAN: Exact, Approximate, and Streaming Algorithms
• Optimal Euclidean spanners: really short, thin and lanky
• Approximate Greedy Clustering and Distance Selection for Graph Metrics
• Snowflake universality of Wasserstein spaces
• Sublinear data structures for short Fréchet queries
• Nearly optimal classification for semimetrics
• Supervised Learning of Labeled Pointcloud Differences via Cover-Tree Entropy Reduction
• Functions with average smoothness: structure, algorithms, and learning
• Fully Dynamic k-Center Clustering in Doubling Metrics
• Linear-Size Approximations to the Vietoris-Rips Filtration
• Can't See The Forest for the Trees: Navigating Metric Spaces by Bounded Hop-Diameter Spanners
• From Hierarchical Partitions to Hierarchical Covers: Optimal Fault-Tolerant Spanners for Doubling Metrics
• Dvoretzky-type theorem for Ahlfors regular spaces
• Classification in asymmetric spaces via sample compression
• Locally Private k-Means in One Round
• Linear-Size Universal Discretization of Geometric Center-Based Problems in Fixed Dimensions
• A Composable Coreset for k-Center in Doubling Metrics
• Near-linear time approximation schemes for Steiner tree and forest in low-dimensional spaces
• Random Rates for 0-Extension and Low-Diameter Decompositions
• Fast C-K-R Partitions of Sparse Graphs
• Faster Clustering via Preprocessing
• Embedding snowflakes of Carnot groups into bounded dimensional Euclidean spaces with optimal distortion
• Algorithmic interpretations of fractal dimension
• Relaxed spanners for directed disk graphs
• Geodesic Spanners for Points in ${\mathbb{R}}^3$ amid Axis-parallel Boxes
• Sharp finiteness principles for Lipschitz selections: long version
• How to Complete a Doubling Metric
• On Geometric Alignment in Low Doubling Dimension
• Randomized Incremental Construction of Net-Trees
• Fault-tolerant additive weighted geometric spanners
• Local Doubling Dimension of Point Sets
• Embedding Metrics into Ultrametrics and Graphs into Spanning Trees with Constant Average Distortion
• Optimal Approximate Distance Oracle for Planar Graphs