Finding Global Icebergs over Distributed Data Sets

Summary: Find global icebergs across many nodes despite items that are globally frequent but locally rare, avoiding prohibitive raw-data shipping. Introduce sampling and CountSketch-based distributed protocols with provable accuracy; CountSketch cuts communication by an order of magnitude while maintaining high accuracy. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: hdef5d1323500626d
Venue: PODS
Year: 2006
Pagerank: 5.8350139e-05
Overall Rank: 6,201 | 58.44%
DOI: 10.1145/1142351.1142394

Incoming Non-self Citations Over Time

Authors

1. Qi (George) Zhao (Georgia Institute of Technology)
2. Mitsunori Ogihara (University of Rochester)
3. Haixun Wang (IBM)
4. Jun (Jim) Xu (Georgia Institute of Technology)

BibTeX Citation

@inproceedings{zhao_pods06,
        address = {New York, NY, USA},
        series = {{PODS} '06},
        title = {{Finding Global Icebergs over Distributed Data Sets}},
        url = {https://dl.acm.org/doi/10.1145/1142351.1142394},
        doi = {10.1145/1142351.1142394},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Zhao, Qi (George) and Ogihara, Mitsunori and Wang, Haixun and Xu, Jun (Jim)},
        year = {2006}
}

Incoming Citations (Sorted by Pagerank)

Showing 5 of 5 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
5,664	Building Wavelet Histograms on Large Data in MapReduce	2012	VLDB	6.0293278e-05
8,213	Distributed Threshold Querying of General Functions by a Difference of Monotonic Representation	2011	VLDB	5.3607592e-05
8,800	CoopStore: Optimizing Precomputed Summaries for Aggregation	2020	VLDB	5.2602992e-05
11,921	MinMax Sampling: A Near-optimal Global Summary for Aggregation in the Wide Area	2022	SIGMOD	4.9605343e-05
12,398	Scalable Approximate Query Tracking over Highly Distributed Data Streams	2016	SIGMOD	4.9605343e-05

Outgoing Citations (Sorted by Pagerank)

Showing 10 of 10 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
124	Approximate Frequency Counts over Data Streams	2002	VLDB	0.00030503973
565	Distributed Top-K Monitoring	2003	SIGMOD	0.00016238411
591	Computing Iceberg Queries Efficiently	1998	VLDB	0.00015853273
713	Approximate Counts and Quantiles over Sliding Windows	2004	PODS	0.00014582248
738	Adaptive Filters for Continuous Queries over Distributed Data Streams	2003	SIGMOD	0.0001432185
860	What’s Hot and What’s Not: Tracking Most Frequent Items Dynamically	2003	PODS	0.00013382689
874	Spectral Bloom Filters	2003	SIGMOD	0.00013298839
1,052	Chain: Operator Scheduling for Memory Minimization in Data Stream Systems	2003	SIGMOD	0.00012262678
1,105	Scalable Distributed Stream Processing	2003	CIDR	0.00011960796
5,666	Distributed Set-Expression Cardinality Estimation	2004	VLDB	6.0281748e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	12,398	Scalable Approximate Query Tracking over Highly Distributed Data Streams	2016	SIGMOD
2	1,883	Efficient Computation of Iceberg Cubes with Complex Measures	2001	SIGMOD
3	8,213	Distributed Threshold Querying of General Functions by a Difference of Monotonic Representation	2011	VLDB
4	2,184	Summarizing and Mining Inverse Distributions on Data Streams via Dynamic Inverse Sampling	2005	VLDB
5	7,889	Sketch-based Querying of Distributed Sliding-Window Data Streams	2012	VLDB
6	6,267	Finding Frequent Items in Probabilistic Data	2008	SIGMOD
7	14,374	Communication-Efficient Distributed Mining of Association Rules	2001	SIGMOD
8	911	Finding Frequent Items in Data Streams	2008	VLDB
9	2,472	Holistic Aggregates in a Networked World: Distributed Tracking of Approximate Quantiles	2005	SIGMOD
10	591	Computing Iceberg Queries Efficiently	1998	VLDB