Twister Tries: Approximate Hierarchical Agglomerative Clustering for Average Distance in Linear Time

Summary: Twister Tries with locality-sensitive hashing enable approximate average-distance hierarchical agglomerative clustering for data. Achieves O(n) time and O(n) space, unlike O(n^2) baselines, with analytic and empirical validation on diverse datasets. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 5085
Venue: SIGMOD
Year: 2015
Pagerank: 6.2885419e-05
Overall Rank: 4,296 | 70.12%
DOI: 10.1145/2723372.2751521

Incoming Non-self Citations Over Time

Authors

1. Michael Cochez
2. Hao Mou

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
11,383	ParChain: A Framework for Parallel Hierarchical Agglomerative Clustering using Nearest-Neighbor Chain	2022	VLDB	4.1945683e-05

Outgoing Citations (Sorted by Pagerank)

Showing 0 of 0 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
34	Similarity Search in High Dimensions via Hashing	1999	VLDB	0.00076637636
11,383	ParChain: A Framework for Parallel Hierarchical Agglomerative Clustering using Nearest-Neighbor Chain	2022	VLDB	4.1945683e-05
10,927	Computing A Well-Representative Summary of Conjunctive Query Results	2024	PODS	4.1945683e-05
9,257	Approximation Algorithms for Co-Clustering	2008	PODS	4.3690661e-05
1,860	Approximation Algorithms for Clustering Uncertain Data	2008	PODS	0.0001028857
4,083	Solving k-center Clustering (with Outliers) in MapReduce and Streaming, almost as Accurately as Sequentially	2019	VLDB	6.4638932e-05
12,357	The Power of Two Min-Hashes for Similarity Search among Hierarchical Data Objects	2008	PODS	4.1945683e-05
10,924	Improved Approximation Algorithms for Relational Clustering	2024	PODS	4.1945683e-05
6,799	Incremental and Effective Data Summarization for Dynamic Hierarchical Clustering	2004	SIGMOD	4.9232394e-05
12,623	Data Bubbles for Non-Vector Data: Speeding-up Hierarchical Clustering in Arbitrary Metric Spaces	2003	VLDB	4.1945683e-05