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.8134046e-05
Overall Rank: 6,267 | 58.00%
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,337	Sliding-Window Top-k Queries on Uncertain Streams	2008	VLDB	7.3950425e-05
7,834	Mining Frequent Itemsets over Uncertain Databases	2012	VLDB	5.4283691e-05
10,451	Frequency Moments in Noisy Streaming and Distributed Data under Mismatch Ambiguity	2026	PODS	4.9605343e-05
12,491	Beyond Itemsets: Mining Frequent Featuresets over Structured Items	2015	VLDB	4.9605343e-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.00042804864
85	ULDBs: Databases with Uncertainty and Lineage	2006	VLDB	0.00035848027
124	Approximate Frequency Counts over Data Streams	2002	VLDB	0.00030503973
153	New Sampling-Based Summary Statistics for Improving Approximate Query Answers	1998	SIGMOD	0.0002855087
162	Robust and Efficient Fuzzy Match for Online Data Cleaning	2003	SIGMOD	0.00027626077
340	Trio: A System for Data, Uncertainty, and Lineage	2006	VLDB	0.00020548826
343	Model-Driven Data Acquisition in Sensor Networks	2004	VLDB	0.00020486383
371	Evaluating Probabilistic Queries over Imprecise Data	2003	SIGMOD	0.00019776963
591	Computing Iceberg Queries Efficiently	1998	VLDB	0.00015853273
597	ConQuer: Efficient Management of Inconsistent Databases	2005	SIGMOD	0.00015742369
826	Data Integration: The Teenage Years	2006	VLDB	0.00013599086
860	What’s Hot and What’s Not: Tracking Most Frequent Items Dynamically	2003	PODS	0.00013382689
1,126	Probabilistic Skylines on Uncertain Data	2007	VLDB	0.00011888563
1,520	Indexing Multi-Dimensional Uncertain Data with Arbitrary Probability Density Functions	2005	VLDB	0.00010358287
1,883	Efficient Computation of Iceberg Cubes with Complex Measures	2001	SIGMOD	9.4237043e-05
2,549	From Complete to Incomplete Information and Back	2007	SIGMOD	8.2889756e-05
2,749	Sketching Probabilistic Data Streams	2007	SIGMOD	8.0426455e-05
2,887	A Simpler and More Efficient Deterministic Scheme for Finding Frequent Items over Sliding Windows	2006	PODS	7.8903242e-05
2,996	Materialized Views in Probabilistic Databases: For Information Exchange and Query Optimization	2007	VLDB	7.7548593e-05
3,049	Estimating Statistical Aggregates on Probabilistic Data Streams	2007	PODS	7.6987705e-05
4,353	Diamond in the Rough: Finding Hierarchical Heavy Hitters in Multi-Dimensional Data	2004	SIGMOD	6.6322269e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	51	Efficient Query Evaluation on Probabilistic Databases	2004	VLDB
2	8,205	Probabilistic Histograms for Probabilistic Data	2009	VLDB
3	3,906	Ranking Continuous Probabilistic Datasets	2010	VLDB
4	371	Evaluating Probabilistic Queries over Imprecise Data	2003	SIGMOD
5	1,367	A Unified Approach to Ranking in Probabilistic Databases	2009	VLDB
6	3,049	Estimating Statistical Aggregates on Probabilistic Data Streams	2007	PODS
7	1,403	Ranking Queries on Uncertain Data: A Probabilistic Threshold Approach	2008	SIGMOD
8	2,749	Sketching Probabilistic Data Streams	2007	SIGMOD
9	911	Finding Frequent Items in Data Streams	2008	VLDB
10	7,834	Mining Frequent Itemsets over Uncertain Databases	2012	VLDB