All-Distances Sketches, Revisited: HIP Estimators for Massive Graphs Analysis

Summary: Unified exposition of All-Distances Sketches (ADS) plus Historic Inverse Probability (HIP) estimators for scalable, near-linear per-node sketching of massive graphs. HIP halves variance of prior neighborhood-size estimates, yields polynomial gains for broader queries, is unbiased/simple, and empirically outperforms HyperLogLog. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: he8a36e75cd93ed88
Venue: PODS
Year: 2014
Pagerank: 7.996482e-05
Overall Rank: 2,789 | 81.31%
DOI: 10.1145/2594538.2594546

Incoming Non-self Citations Over Time

Authors

1. Edith Cohen (Microsoft)

BibTeX Citation

@inproceedings{cohen_pods14,
        address = {New York, NY, USA},
        series = {{PODS} '14},
        title = {{All-Distances Sketches, Revisited: HIP Estimators for Massive Graphs Analysis}},
        url = {https://dl.acm.org/doi/10.1145/2594538.2594546},
        doi = {10.1145/2594538.2594546},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Cohen, Edith},
        year = {2014}
}

Incoming Citations (Sorted by Pagerank)

Showing 10 of 10 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
4,511	Approximately Counting Triangles in Large Graph Streams Including Edge Duplicates with a Fixed Memory Usage	2018	VLDB	6.5538597e-05
5,998	SetSketch: Filling the Gap between MinHash and HyperLogLog	2021	VLDB	5.9035525e-05
6,138	Approximate Distinct Counts for Billions of Datasets	2019	SIGMOD	5.8575652e-05
7,075	UltraLogLog: A Practical and More Space-Efficient Alternative to HyperLogLog for Approximate Distinct Counting	2024	VLDB	5.5911909e-05
7,096	Better Cardinality Estimators for HyperLogLog, PCSA, and Beyond	2023	PODS	5.5853839e-05
8,579	Sampling Big Ideas in Query Optimization	2023	PODS	5.2958113e-05
9,083	An Efficient Algorithm for Distance-based Structural Graph Clustering	2023	SIGMOD	5.209913e-05
10,299	Shared Load(ing): Efficient Bulk Loading into Optimized Storage	2020	CIDR	5.0302708e-05
10,394	Effective Structurally Similar Community Search in Large Temporal Graphs	2027	SIGMOD	4.9605343e-05
12,380	An Efficient MapReduce Cube Algorithm for Varied Data Distributions	2016	SIGMOD	4.9605343e-05

Outgoing Citations (Sorted by Pagerank)

Showing 4 of 4 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
3	Pregel: A System for Large-Scale Graph Processing	2010	SIGMOD	0.0012089097
192	Fast Exact Shortest-Path Distance Queries on Large Networks by Pruned Landmark Labeling	2013	SIGMOD	0.00025740385
495	An Optimal Algorithm for the Distinct Elements Problem	2010	PODS	0.00017347522
3,549	Tighter Estimation using Bottom k Sketches	2008	VLDB	7.1896874e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	7,375	Toward a Distance Oracle for Billion-Node Graphs	2014	VLDB
2	2,430	gSketch: On Query Estimation in Graph Streams	2012	VLDB
3	5,998	SetSketch: Filling the Gap between MinHash and HyperLogLog	2021	VLDB
4	3,778	Efficient Algorithms for Densest Subgraph Discovery on Large Directed Graphs	2020	SIGMOD
5	9,083	An Efficient Algorithm for Distance-based Structural Graph Clustering	2023	SIGMOD
6	8,937	Fully Dynamic Betweenness Centrality Maintenance on Massive Networks	2016	VLDB
7	10,520	Efficient Anchored Densest Subgraph Discovery: Improved Time Complexity and Practical Performance	2026	SIGMOD
8	4,869	Vertex and Hyperedge Connectivity in Dynamic Graph Streams	2015	PODS
9	1,153	Graph Sketches: Sparsification, Spanners, and Subgraphs	2012	PODS
10	6,138	Approximate Distinct Counts for Billions of Datasets	2019	SIGMOD