Finding Frequent Items in Probabilistic Data

Summary: Possible-world semantics define likely frequent items in probabilistic data, capturing structure beyond simple expected frequency. Exact offline algorithms (quadratic/cubic) and sublinear-memory streaming sampling with provable accuracy and confidence-based ranking, validated on real and synthetic data. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: ha9e4b29b5bb3d722
Venue: SIGMOD
Year: 2008
Pagerank: 5.8326825e-05
Overall Rank: 6,255 | 57.96%
DOI: 10.1145/1376616.1376698

Incoming Non-self Citations Over Time

Authors

1. Qin Zhang (Hong Kong University of Science and Technology)
2. Feifei Li (Florida State University)
3. Ke Yi (Hong Kong University of Science and Technology)

BibTeX Citation

@inproceedings{zhang_sigmod08,
        title = {{Finding Frequent Items in Probabilistic Data}},
        author = {Zhang, Qin and Li, Feifei and Yi, Ke},
        series = {{SIGMOD} '08},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/1376616.1376698},
        url = {https://dl.acm.org/doi/10.1145/1376616.1376698},
        year = {2008}
}

Incoming Citations (Sorted by Pagerank)

Showing 4 of 4 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
3,328	Sliding-Window Top-k Queries on Uncertain Streams	2008	VLDB	7.4194442e-05
7,817	Mining Frequent Itemsets over Uncertain Databases	2012	VLDB	5.4462922e-05
10,385	Frequency Moments in Noisy Streaming and Distributed Data under Mismatch Ambiguity	2026	PODS	4.9769913e-05
12,448	Beyond Itemsets: Mining Frequent Featuresets over Structured Items	2015	VLDB	4.9769913e-05

Outgoing Citations (Sorted by Pagerank)

Showing 21 of 21 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
51	Efficient Query Evaluation on Probabilistic Databases	2004	VLDB	0.00042926566
84	ULDBs: Databases with Uncertainty and Lineage	2006	VLDB	0.00035960573
124	Approximate Frequency Counts over Data Streams	2002	VLDB	0.00030586757
153	New Sampling-Based Summary Statistics for Improving Approximate Query Answers	1998	SIGMOD	0.00028621958
161	Robust and Efficient Fuzzy Match for Online Data Cleaning	2003	SIGMOD	0.00027705594
337	Trio: A System for Data, Uncertainty, and Lineage	2006	VLDB	0.00020613834
343	Model-Driven Data Acquisition in Sensor Networks	2004	VLDB	0.00020510274
370	Evaluating Probabilistic Queries over Imprecise Data	2003	SIGMOD	0.00019837998
588	Computing Iceberg Queries Efficiently	1998	VLDB	0.00015899635
595	ConQuer: Efficient Management of Inconsistent Databases	2005	SIGMOD	0.00015791577
824	Data Integration: The Teenage Years	2006	VLDB	0.00013641217
858	What’s Hot and What’s Not: Tracking Most Frequent Items Dynamically	2003	PODS	0.00013420431
1,125	Probabilistic Skylines on Uncertain Data	2007	VLDB	0.00011921893
1,518	Indexing Multi-Dimensional Uncertain Data with Arbitrary Probability Density Functions	2005	VLDB	0.0001039208
1,875	Efficient Computation of Iceberg Cubes with Complex Measures	2001	SIGMOD	9.4535173e-05
2,543	From Complete to Incomplete Information and Back	2007	SIGMOD	8.3143504e-05
2,738	Sketching Probabilistic Data Streams	2007	SIGMOD	8.0692701e-05
2,876	A Simpler and More Efficient Deterministic Scheme for Finding Frequent Items over Sliding Windows	2006	PODS	7.9156746e-05
2,985	Materialized Views in Probabilistic Databases: For Information Exchange and Query Optimization	2007	VLDB	7.7794901e-05
3,039	Estimating Statistical Aggregates on Probabilistic Data Streams	2007	PODS	7.723493e-05
4,349	Diamond in the Rough: Finding Hierarchical Heavy Hitters in Multi-Dimensional Data	2004	SIGMOD	6.6437679e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	51	Efficient Query Evaluation on Probabilistic Databases	2004	VLDB
2	8,193	Probabilistic Histograms for Probabilistic Data	2009	VLDB
3	3,893	Ranking Continuous Probabilistic Datasets	2010	VLDB
4	370	Evaluating Probabilistic Queries over Imprecise Data	2003	SIGMOD
5	1,360	A Unified Approach to Ranking in Probabilistic Databases	2009	VLDB
6	3,039	Estimating Statistical Aggregates on Probabilistic Data Streams	2007	PODS
7	1,397	Ranking Queries on Uncertain Data: A Probabilistic Threshold Approach	2008	SIGMOD
8	2,738	Sketching Probabilistic Data Streams	2007	SIGMOD
9	911	Finding Frequent Items in Data Streams	2008	VLDB
10	7,817	Mining Frequent Itemsets over Uncertain Databases	2012	VLDB