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: 4036
Venue: SIGMOD
Year: 2008
Pagerank: 5.3189104e-05
Overall Rank: 5,807 | 59.65%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 3 of 3 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
4,328	Sliding-Window Top-k Queries on Uncertain Streams	2008	VLDB	6.2765138e-05
7,633	Mining Frequent Itemsets over Uncertain Databases	2012	VLDB	4.6869557e-05
11,960	Beyond Itemsets: Mining Frequent Featuresets over Structured Items	2015	VLDB	4.1905499e-05

Outgoing Citations (Sorted by Pagerank)

Showing 20 of 20 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
74	Efficient Query Evaluation on Probabilistic Databases	2004	VLDB	0.00057797415
103	ULDBs: Databases with Uncertainty and Lineage	2006	VLDB	0.00049520051
155	Robust and Efficient Fuzzy Match for Online Data Cleaning	2003	SIGMOD	0.00040666376
168	Approximate Frequency Counts over Data Streams	2002	VLDB	0.0003915627
184	New Sampling-Based Summary Statistics for Improving Approximate Query Answers	1998	SIGMOD	0.00036655704
300	Trio: A System for Data, Uncertainty, and Lineage	2006	VLDB	0.00028503742
463	Evaluating Probabilistic Queries over Imprecise Data	2003	SIGMOD	0.00022497894
477	Model-Driven Data Acquisition in Sensor Networks	2004	VLDB	0.00022205608
598	Computing Iceberg Queries Efficiently	1998	VLDB	0.00019431661
677	ConQuer: Efficient Management of Inconsistent Databases	2005	SIGMOD	0.00018250681
874	What’s Hot and What’s Not: Tracking Most Frequent Items Dynamically	2003	PODS	0.0001568356
889	Data Integration: The Teenage Years	2006	VLDB	0.00015548507
1,181	Probabilistic Skylines on Uncertain Data	2007	VLDB	0.00013447487
1,568	Indexing Multi-Dimensional Uncertain Data with Arbitrary Probability Density Functions	2005	VLDB	0.0001131667
1,967	Efficient Computation of Iceberg Cubes with Complex Measures	2001	SIGMOD	9.9108189e-05
2,493	From Complete to Incomplete Information and Back	2007	SIGMOD	8.6470623e-05
2,766	A Simpler and More Efficient Deterministic Scheme for Finding Frequent Items over Sliding Windows	2006	PODS	8.1559016e-05
3,047	Sketching Probabilistic Data Streams	2007	SIGMOD	7.6537004e-05
3,391	Estimating Statistical Aggregates on Probabilistic Data Streams	2007	PODS	7.1427968e-05
4,463	Diamond in the Rough: Finding Hierarchical Heavy Hitters in Multi-Dimensional Data	2004	SIGMOD	6.1563782e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
74	Efficient Query Evaluation on Probabilistic Databases	2004	VLDB	0.00057797415
8,092	Probabilistic Histograms for Probabilistic Data	2009	VLDB	4.5847443e-05
4,094	Ranking Continuous Probabilistic Datasets	2010	VLDB	6.4510938e-05
463	Evaluating Probabilistic Queries over Imprecise Data	2003	SIGMOD	0.00022497894
1,612	A Unified Approach to Ranking in Probabilistic Databases	2009	VLDB	0.00011142757
3,391	Estimating Statistical Aggregates on Probabilistic Data Streams	2007	PODS	7.1427968e-05
1,703	Ranking Queries on Uncertain Data: A Probabilistic Threshold Approach	2008	SIGMOD	0.00010820803
3,047	Sketching Probabilistic Data Streams	2007	SIGMOD	7.6537004e-05
831	Finding Frequent Items in Data Streams	2008	VLDB	0.00016094846
7,633	Mining Frequent Itemsets over Uncertain Databases	2012	VLDB	4.6869557e-05