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: 1401
Venue: PODS
Year: 2006
Pagerank: 5.9914746e-05
Overall Rank: 6,060 | 58.43%
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,522	Building Wavelet Histograms on Large Data in MapReduce	2012	VLDB	6.1871697e-05
8,029	Distributed Threshold Querying of General Functions by a Difference of Monotonic Representation	2011	VLDB	5.5045998e-05
8,616	CoopStore: Optimizing Precomputed Summaries for Aggregation	2020	VLDB	5.4004741e-05
11,562	MinMax Sampling: A Near-optimal Global Summary for Aggregation in the Wide Area	2022	SIGMOD	5.093636e-05
12,054	Scalable Approximate Query Tracking over Highly Distributed Data Streams	2016	SIGMOD	5.093636e-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
122	Approximate Frequency Counts over Data Streams	2002	VLDB	0.00031260115
550	Distributed Top-K Monitoring	2003	SIGMOD	0.0001663758
577	Computing Iceberg Queries Efficiently	1998	VLDB	0.00016235949
691	Approximate Counts and Quantiles over Sliding Windows	2004	PODS	0.00014927798
722	Adaptive Filters for Continuous Queries over Distributed Data Streams	2003	SIGMOD	0.00014627248
838	What’s Hot and What’s Not: Tracking Most Frequent Items Dynamically	2003	PODS	0.0001370404
862	Spectral Bloom Filters	2003	SIGMOD	0.00013532857
1,027	Chain: Operator Scheduling for Memory Minimization in Data Stream Systems	2003	SIGMOD	0.00012563656
1,090	Scalable Distributed Stream Processing	2003	CIDR	0.0001224178
5,516	Distributed Set-Expression Cardinality Estimation	2004	VLDB	6.1895841e-05

Semantically Similar Papers

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