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: 9641
Venue: VLDB
Year: 2007
Pagerank: 4.8221884e-05
Overall Rank: 7,135 | 50.37%
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,373	Robust and Efficient Algorithms for Rank Join Evaluation	2009	SIGMOD	5.5425231e-05
6,293	Ad-Hoc Aggregations of Ranked Lists in the Presence of Hierarchies	2008	SIGMOD	5.1257071e-05
8,129	Discovering the Skyline of Web Databases	2016	VLDB	4.5784968e-05
12,300	Skip-and-Prune: Cosine-based Top-K Query Processing for Efficient Context-Sensitive Document Retrieval	2009	SIGMOD	4.1945683e-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
7	Optimal Aggregation Algorithms for Middleware [Extended Abstract]	2001	PODS	0.0015496097
17	Optimizing Multi-Feature Queries for Image Databases	2000	VLDB	0.00096067547
72	Combining Fuzzy Information from Multiple Systems	1996	PODS	0.00058577335
91	M-tree: An Efficient Access Method for Similarity Search in Metric Spaces	1997	VLDB	0.0005181666
141	Selectivity Estimation Without the Attribute Value Independence Assumption	1997	VLDB	0.00041786333
169	Fuzzy Queries in Multimedia Database Systems	1998	PODS	0.00038895438
430	The Onion Technique: Indexing for Linear Optimization Queries	2000	SIGMOD	0.00023463938
465	PREFER: A System for the Efficient Execution of Multiparametric Ranked Queries	2001	SIGMOD	0.00022455702
552	Supporting Incremental Join Queries on Ranked Inputs	2001	VLDB	0.00020310903
674	Supporting Top-k Join Queries in Relational Databases	2003	VLDB	0.00018327585
805	Evaluating Top-k Selection Queries	1999	VLDB	0.00016437265
996	Approximating Multi-Dimensional Aggregate Range Queries Over Real Attributes	2000	SIGMOD	0.00014741524
1,096	Minimal Probing: Supporting Expensive Predicates for Top-k Queries	2002	SIGMOD	0.00014120512
1,808	Top-k Query Evaluation with Probabilistic Guarantees	2004	VLDB	0.00010486213
2,556	Probabilistic Optimization of Top N Queries	1999	VLDB	8.5465733e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
11,748	Durable Top-k Queries on Temporal Data	2018	VLDB	4.1945683e-05
4,186	Best Position Algorithms for Top-k Queries	2007	VLDB	6.3764858e-05
3,908	Progressive and Selective Merge: Computing Top-K with Ad-hoc Ranking Functions	2007	SIGMOD	6.6392878e-05
2,009	IO-Top-k: Index-access Optimized Top-k Query Processing	2006	VLDB	9.7977564e-05
2,976	Processing a Large Number of Continuous Preference Top-k Queries	2012	SIGMOD	7.789303e-05
7,513	Ranking Large Temporal Data	2012	VLDB	4.7180617e-05
12,111	Optimal Top-k Generation of Attribute Combinations based on Ranked Lists	2012	SIGMOD	4.1945683e-05
7,276	Efficient and Generic Evaluation of Ranked Queries	2011	SIGMOD	4.7798595e-05
7,963	Efficient Top-K Processing Over Query-Dependent Functions	2008	VLDB	4.613363e-05
1,808	Top-k Query Evaluation with Probabilistic Guarantees	2004	VLDB	0.00010486213