Anytime Measures for Top-k Algorithms

Summary: Anytime measures for top-k queries on large multi-attribute data, examining TA and TA-Sorted. A probabilistic framework yields, at any moment, the confidence that the top-k is identified, enabling early stopping and runtime savings. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 9642
Venue: VLDB
Year: 2007
Pagerank: 4.8175888e-05
Overall Rank: 7,133 | 50.43%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 4 of 4 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
5,379	Robust and Efficient Algorithms for Rank Join Evaluation	2009	SIGMOD	5.5375923e-05
6,292	Ad-Hoc Aggregations of Ranked Lists in the Presence of Hierarchies	2008	SIGMOD	5.1209778e-05
8,132	Discovering the Skyline of Web Databases	2016	VLDB	4.5741104e-05
12,308	Skip-and-Prune: Cosine-based Top-K Query Processing for Efficient Context-Sensitive Document Retrieval	2009	SIGMOD	4.1905499e-05

Outgoing Citations (Sorted by Pagerank)

Showing 15 of 15 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
8	Optimal Aggregation Algorithms for Middleware [Extended Abstract]	2001	PODS	0.0015436578
17	Optimizing Multi-Feature Queries for Image Databases	2000	VLDB	0.00095799341
72	Combining Fuzzy Information from Multiple Systems	1996	PODS	0.00058498396
91	M-tree: An Efficient Access Method for Similarity Search in Metric Spaces	1997	VLDB	0.00051785122
141	Selectivity Estimation Without the Attribute Value Independence Assumption	1997	VLDB	0.00041819767
171	Fuzzy Queries in Multimedia Database Systems	1998	PODS	0.00038843975
428	The Onion Technique: Indexing for Linear Optimization Queries	2000	SIGMOD	0.0002349868
464	PREFER: A System for the Efficient Execution of Multiparametric Ranked Queries	2001	SIGMOD	0.00022476798
551	Supporting Incremental Join Queries on Ranked Inputs	2001	VLDB	0.00020310856
673	Supporting Top-k Join Queries in Relational Databases	2003	VLDB	0.00018325667
802	Evaluating Top-k Selection Queries	1999	VLDB	0.00016440813
995	Approximating Multi-Dimensional Aggregate Range Queries Over Real Attributes	2000	SIGMOD	0.00014745185
1,093	Minimal Probing: Supporting Expensive Predicates for Top-k Queries	2002	SIGMOD	0.00014123221
1,805	Top-k Query Evaluation with Probabilistic Guarantees	2004	VLDB	0.00010479371
2,552	Probabilistic Optimization of Top N Queries	1999	VLDB	8.5540341e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
11,756	Durable Top-k Queries on Temporal Data	2018	VLDB	4.1905499e-05
4,178	Best Position Algorithms for Top-k Queries	2007	VLDB	6.3757762e-05
3,911	Progressive and Selective Merge: Computing Top-K with Ad-hoc Ranking Functions	2007	SIGMOD	6.6343292e-05
2,014	IO-Top-k: Index-access Optimized Top-k Query Processing	2006	VLDB	9.7982231e-05
2,967	Processing a Large Number of Continuous Preference Top-k Queries	2012	SIGMOD	7.7975455e-05
7,512	Ranking Large Temporal Data	2012	VLDB	4.7135369e-05
12,119	Optimal Top-k Generation of Attribute Combinations based on Ranked Lists	2012	SIGMOD	4.1905499e-05
7,273	Efficient and Generic Evaluation of Ranked Queries	2011	SIGMOD	4.775366e-05
7,966	Efficient Top-K Processing Over Query-Dependent Functions	2008	VLDB	4.6089395e-05
1,805	Top-k Query Evaluation with Probabilistic Guarantees	2004	VLDB	0.00010479371