Sliding-Window Top-k Queries on Uncertain Streams

Summary: Introduces the first framework for sliding-window top-k queries over uncertain streams, handling both tuple arrivals and expirations despite possible-worlds explosion. Supports existing top-k semantics via compact, sub-window-size synopses with strong efficiency guarantees. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: 9867
Venue: VLDB
Year: 2008
Pagerank: 7.2710351e-05
Overall Rank: 3,599 | 75.31%
DOI: 10.14778/1453856.1453892

Incoming Non-self Citations Over Time

Authors

1. Cheqing Jin (East China University of Science and Technology)
2. Ke Yi (Hong Kong University of Science and Technology)
3. Lei Chen (Hong Kong University of Science and Technology)
4. Jeffrey Xu Yu (Chinese University of Hong Kong)
5. Xuemin Lin (National ICT Australia; University of New South Wales)

BibTeX Citation

@article{jin_vldb08,
        title = {{Sliding-Window Top-k Queries on Uncertain Streams}},
        author = {Jin, Cheqing and Yi, Ke and Chen, Lei and Yu, Jeffrey Xu and Lin, Xuemin},
        journal = {PVLDB},
        series = {{VLDB} '08},
        volume = {6},
        number = {10},
        doi = {10.14778/1453856.1453892},
        url = {https://doi.org/10.14778/1453856.1453892},
        year = {2008}
}

Incoming Citations (Sorted by Pagerank)

Showing 8 of 8 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,049	k-Nearest Neighbors in Uncertain Graphs	2010	VLDB	0.00012415522
1,327	A Unified Approach to Ranking in Probabilistic Databases	2009	VLDB	0.00011141552
3,049	Top-k Queries on Uncertain Data: On Score Distribution and Typical Answers	2009	SIGMOD	7.8151597e-05
5,796	Reverse k-Ranks Query	2014	VLDB	6.0859929e-05
6,830	Global Immutable Region Computation	2014	SIGMOD	5.759977e-05
7,548	Local Differentially Private Heavy Hitter Detection in Data Streams with Bounded Memory	2024	SIGMOD	5.6021153e-05
8,247	Optimal Approximate Matrix Multiplication over Sliding Windows	2026	VLDB	5.4574671e-05
10,156	Frequency Moments in Noisy Streaming and Distributed Data under Mismatch Ambiguity	2026	PODS	5.093636e-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
5	Optimal Aggregation Algorithms for Middleware [Extended Abstract]	2001	PODS	0.0010828372
50	Efficient Query Evaluation on Probabilistic Databases	2004	VLDB	0.00043596705
359	Evaluating Probabilistic Queries over Imprecise Data	2003	SIGMOD	0.0002023153
550	Distributed Top-K Monitoring	2003	SIGMOD	0.0001663758
1,041	The Dichotomy of Conjunctive Queries on Probabilistic Structures	2007	PODS	0.00012453494
1,363	Ranking Queries on Uncertain Data: A Probabilistic Threshold Approach	2008	SIGMOD	0.00011025316
1,513	Continuous Monitoring of Top-k Queries over Sliding Windows	2006	SIGMOD	0.00010530872
2,525	Answering Top-k Queries Using Views	2006	VLDB	8.4653166e-05
2,697	Sketching Probabilistic Data Streams	2007	SIGMOD	8.2451054e-05
2,988	Estimating Statistical Aggregates on Probabilistic Data Streams	2007	PODS	7.8907087e-05
4,321	Efficiently Answering Top-k Typicality Queries on Large Databases	2007	VLDB	6.7617825e-05
4,587	Answering Top-k Queries with Multi-Dimensional Selections: The Ranking Cube Approach	2006	VLDB	6.6170389e-05
5,604	Approximate Quantiles and the Order of the Stream	2006	PODS	6.1533846e-05
6,120	Finding Frequent Items in Probabilistic Data	2008	SIGMOD	5.9693818e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	1,363	Ranking Queries on Uncertain Data: A Probabilistic Threshold Approach	2008	SIGMOD
2	4,596	Static Optimization of Conjunctive Queries with Sliding Windows Over Infinite Streams	2004	SIGMOD
3	8,603	Stream Frequency over Interval Queries	2019	VLDB
4	2,697	Sketching Probabilistic Data Streams	2007	SIGMOD
5	550	Distributed Top-K Monitoring	2003	SIGMOD
6	7,713	Sketch-based Querying of Distributed Sliding-Window Data Streams	2012	VLDB
7	9,194	Efficient Approximation of Certain and Possible Answers for Ranking and Window Queries over Uncertain Data	2023	VLDB
8	3,049	Top-k Queries on Uncertain Data: On Score Distribution and Typical Answers	2009	SIGMOD
9	3,317	Ad-hoc Top-k Query Answering for Data Streams	2007	VLDB
10	1,513	Continuous Monitoring of Top-k Queries over Sliding Windows	2006	SIGMOD