Sliding-Window Top-k Queries on Uncertain Streams

Summary: Unifies sliding-window top-k processing for uncertain streams, handling arrivals and expirations under tight space and time bounds. A single framework supports all top-k definitions, yielding compact synopses smaller than the window with efficient processing, validated on synthetic and real data. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 9676
Venue: VLDB
Year: 2008
Pagerank: 6.4652983e-05
Overall Rank: 4,080 | 71.62%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 7 of 7 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,162	k-Nearest Neighbors in Uncertain Graphs	2010	VLDB	0.0001358105
1,609	A Unified Approach to Ranking in Probabilistic Databases	2009	VLDB	0.00011150935
3,185	Top-k Queries on Uncertain Data: On Score Distribution and Typical Answers	2009	SIGMOD	7.4192604e-05
6,222	Reverse k-Ranks Query	2014	VLDB	5.1503175e-05
6,599	Local Differentially Private Heavy Hitter Detection in Data Streams with Bounded Memory	2024	SIGMOD	4.9973567e-05
6,632	Global Immutable Region Computation	2014	SIGMOD	4.984576e-05
7,929	Optimal Approximate Matrix Multiplication over Sliding Windows	2026	VLDB	4.613363e-05

Outgoing Citations (Sorted by Pagerank)

Showing 14 of 14 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
7	Optimal Aggregation Algorithms for Middleware [Extended Abstract]	2001	PODS	0.0015496097
74	Efficient Query Evaluation on Probabilistic Databases	2004	VLDB	0.00057857292
467	Evaluating Probabilistic Queries over Imprecise Data	2003	SIGMOD	0.00022443768
745	Distributed Top-K Monitoring	2003	SIGMOD	0.00017330487
1,268	The Dichotomy of Conjunctive Queries on Probabilistic Structures	2007	PODS	0.00012931993
1,707	Ranking Queries on Uncertain Data: A Probabilistic Threshold Approach	2008	SIGMOD	0.00010816111
1,784	Continuous Monitoring of Top-k Queries over Sliding Windows	2006	SIGMOD	0.00010567363
2,933	Answering Top-k Queries Using Views	2006	VLDB	7.8679669e-05
3,041	Sketching Probabilistic Data Streams	2007	SIGMOD	7.6697078e-05
3,385	Estimating Statistical Aggregates on Probabilistic Data Streams	2007	PODS	7.1580391e-05
4,031	Approximate Quantiles and the Order of the Stream	2006	PODS	6.5121141e-05
4,504	Efficiently Answering Top-k Typicality Queries on Large Databases	2007	VLDB	6.1327917e-05
4,711	Answering Top-k Queries with Multi-Dimensional Selections: The Ranking Cube Approach	2006	VLDB	5.9790683e-05
5,796	Finding Frequent Items in Probabilistic Data	2008	SIGMOD	5.3240234e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
1,707	Ranking Queries on Uncertain Data: A Probabilistic Threshold Approach	2008	SIGMOD	0.00010816111
4,930	Static Optimization of Conjunctive Queries with Sliding Windows Over Infinite Streams	2004	SIGMOD	5.8213082e-05
8,594	Stream Frequency over Interval Queries	2019	VLDB	4.4891331e-05
3,041	Sketching Probabilistic Data Streams	2007	SIGMOD	7.6697078e-05
745	Distributed Top-K Monitoring	2003	SIGMOD	0.00017330487
7,834	Sketch-based Querying of Distributed Sliding-Window Data Streams	2012	VLDB	4.6382551e-05
9,044	Efficient Approximation of Certain and Possible Answers for Ranking and Window Queries over Uncertain Data	2023	VLDB	4.4039656e-05
3,185	Top-k Queries on Uncertain Data: On Score Distribution and Typical Answers	2009	SIGMOD	7.4192604e-05
3,665	Ad-hoc Top-k Query Answering for Data Streams	2007	VLDB	6.8633354e-05
1,784	Continuous Monitoring of Top-k Queries over Sliding Windows	2006	SIGMOD	0.00010567363