Faster and Better Solution to Embed Lp Metrics by Tree Metrics

Summary: ELT: faster embedding of Lp metrics into tree metrics via HSTs, using a divide-and-conquer framework achieving O(log n) distortion. Key tricks: nearest-neighbor indexing and sampling to beat O(n^2); DCsam yields faster construction and stronger empirical distortion/runtime gains vs. prior methods. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 6285
Venue: SIGMOD
Year: 2022
Pagerank: 4.1945683e-05
Overall Rank: 11,335 | 21.15%
DOI: 10.1145/3514221.3517831

Incoming Non-self Citations Over Time

No non-self incoming citations found for this paper in this database.

Authors

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
7,654	LiteHST: A Tree Embedding based Method for Similarity Search	2023	SIGMOD	4.687476e-05

Outgoing Citations (Sorted by Pagerank)

Showing 9 of 9 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
2	R-Trees: A Dynamic Index Structure For Spatial Searching	1984	SIGMOD	0.0032169493
6	The R*-tree: An Efficient and Robust Access Method for Points and Rectangles	1990	SIGMOD	0.0016162015
562	Query-Aware Locality-Sensitive Hashing for Approximate Nearest Neighbor Search	2016	VLDB	0.00020091752
961	DBSCAN Revisited: Mis-Claim, Un-Fixability, and Approximation	2015	SIGMOD	0.00015001792
2,247	On Efficient Spatial Matching	2007	VLDB	9.2048219e-05
2,678	Effectively Learning Spatial Indices	2020	VLDB	8.3252088e-05
3,235	Online Minimum Matching in Real-Time Spatial Data: Experiments and Analysis	2016	VLDB	7.3355287e-05
6,006	Last-Mile Delivery Made Practical: An Efficient Route Planning Framework with Theoretical Guarantees	2020	VLDB	5.2415551e-05
6,973	The Simpler The Better: An Indexing Approach for Shared-Route Planning Queries	2020	VLDB	4.878479e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
5,273	Correlating XML Data Streams Using Tree-Edit Distance Embeddings	2003	PODS	5.5913399e-05
7,480	Towards Metric DBSCAN: Exact, Approximate, and Streaming Algorithms	2024	SIGMOD	4.7180617e-05
358	On The Marriage of Lp-norms and Edit Distance	2004	VLDB	0.0002599481
5,894	Fast Euclidean OPTICS with Bounded Precision in Low Dimensional Space	2018	SIGMOD	5.2864259e-05
9,061	Optimality and Scalability in Lattice Histogram Construction	2009	VLDB	4.4039656e-05
6,376	DET-LSH: A Locality-Sensitive Hashing Scheme with Dynamic Encoding Tree for Approximate Nearest Neighbor Search	2024	VLDB	5.0916875e-05
5,883	MapReduce and Streaming Algorithms for Diversity Maximization in Metric Spaces of Bounded Doubling Dimension	2017	VLDB	5.2890537e-05
3,199	Similarity Evaluation on Tree-structured Data	2005	SIGMOD	7.3927291e-05
11,477	Fast Parallel Algorithms for Euclidean Minimum Spanning Tree and Hierarchical Spatial Clustering*	2021	SIGMOD	4.1945683e-05
7,654	LiteHST: A Tree Embedding based Method for Similarity Search	2023	SIGMOD	4.687476e-05