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.8354449e-05
Overall Rank: 6,252 | 57.97%
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,326	Sliding-Window Top-k Queries on Uncertain Streams	2008	VLDB	7.4227632e-05
7,810	Mining Frequent Itemsets over Uncertain Databases	2012	VLDB	5.4488716e-05
10,373	Frequency Moments in Noisy Streaming and Distributed Data under Mismatch Ambiguity	2026	PODS	4.9793485e-05
12,442	Beyond Itemsets: Mining Frequent Featuresets over Structured Items	2015	VLDB	4.9793485e-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.00042936299
84	ULDBs: Databases with Uncertainty and Lineage	2006	VLDB	0.00035963861
124	Approximate Frequency Counts over Data Streams	2002	VLDB	0.00030600691
153	New Sampling-Based Summary Statistics for Improving Approximate Query Answers	1998	SIGMOD	0.00028633995
161	Robust and Efficient Fuzzy Match for Online Data Cleaning	2003	SIGMOD	0.00027718195
337	Trio: A System for Data, Uncertainty, and Lineage	2006	VLDB	0.00020621631
343	Model-Driven Data Acquisition in Sensor Networks	2004	VLDB	0.00020519525
370	Evaluating Probabilistic Queries over Imprecise Data	2003	SIGMOD	0.00019846702
588	Computing Iceberg Queries Efficiently	1998	VLDB	0.00015906635
595	ConQuer: Efficient Management of Inconsistent Databases	2005	SIGMOD	0.00015798582
824	Data Integration: The Teenage Years	2006	VLDB	0.00013646923
858	What’s Hot and What’s Not: Tracking Most Frequent Items Dynamically	2003	PODS	0.000134266
1,124	Probabilistic Skylines on Uncertain Data	2007	VLDB	0.00011927351
1,518	Indexing Multi-Dimensional Uncertain Data with Arbitrary Probability Density Functions	2005	VLDB	0.00010396565
1,874	Efficient Computation of Iceberg Cubes with Complex Measures	2001	SIGMOD	9.4579757e-05
2,543	From Complete to Incomplete Information and Back	2007	SIGMOD	8.3182354e-05
2,738	Sketching Probabilistic Data Streams	2007	SIGMOD	8.07308e-05
2,875	A Simpler and More Efficient Deterministic Scheme for Finding Frequent Items over Sliding Windows	2006	PODS	7.9193665e-05
2,984	Materialized Views in Probabilistic Databases: For Information Exchange and Query Optimization	2007	VLDB	7.7830089e-05
3,038	Estimating Statistical Aggregates on Probabilistic Data Streams	2007	PODS	7.7270848e-05
4,348	Diamond in the Rough: Finding Hierarchical Heavy Hitters in Multi-Dimensional Data	2004	SIGMOD	6.6469144e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	51	Efficient Query Evaluation on Probabilistic Databases	2004	VLDB
2	8,206	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,365	A Unified Approach to Ranking in Probabilistic Databases	2009	VLDB
6	3,038	Estimating Statistical Aggregates on Probabilistic Data Streams	2007	PODS
7	1,396	Ranking Queries on Uncertain Data: A Probabilistic Threshold Approach	2008	SIGMOD
8	2,738	Sketching Probabilistic Data Streams	2007	SIGMOD
9	909	Finding Frequent Items in Data Streams	2008	VLDB
10	7,810	Mining Frequent Itemsets over Uncertain Databases	2012	VLDB