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: 5147
Venue: SIGMOD
Year: 2015
Pagerank: 5.9425753e-05
Overall Rank: 6,219 | 57.34%
DOI: 10.1145/2723372.2751521

Incoming Non-self Citations Over Time

Authors

1. Michael Cochez (University of Jyvaskyla)
2. Hao Mou (University of Jyvaskyla)

BibTeX Citation

@inproceedings{cochez_sigmod15,
        title = {{Twister Tries: Approximate Hierarchical Agglomerative Clustering for Average Distance in Linear Time}},
        author = {Cochez, Michael and Mou, Hao},
        series = {{SIGMOD} '15},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/2723372.2751521},
        url = {https://dl.acm.org/doi/10.1145/2723372.2751521},
        year = {2015}
}

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
11,581	ParChain: A Framework for Parallel Hierarchical Agglomerative Clustering using Nearest-Neighbor Chain	2022	VLDB	5.093636e-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
1	2,567	ClusterJoin: A Similarity Joins Framework using Map-Reduce	2014	VLDB
2	11,581	ParChain: A Framework for Parallel Hierarchical Agglomerative Clustering using Nearest-Neighbor Chain	2022	VLDB
3	8,728	Computing A Well-Representative Summary of Conjunctive Query Results	2024	PODS
4	9,402	Approximation Algorithms for Co-Clustering	2008	PODS
5	2,253	Approximation Algorithms for Clustering Uncertain Data	2008	PODS
6	4,366	Solving k-center Clustering (with Outliers) in MapReduce and Streaming, almost as Accurately as Sequentially	2019	VLDB
7	12,550	The Power of Two Min-Hashes for Similarity Search among Hierarchical Data Objects	2008	PODS
8	11,144	Improved Approximation Algorithms for Relational Clustering	2024	PODS
9	7,291	Incremental and Effective Data Summarization for Dynamic Hierarchical Clustering	2004	SIGMOD
10	12,816	Data Bubbles for Non-Vector Data: Speeding-up Hierarchical Clustering in Arbitrary Metric Spaces	2003	VLDB