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: 9832
Venue: VLDB
Year: 2007
Pagerank: 5.6779179e-05
Overall Rank: 7,185 | 50.71%
DOI: 10.1145/1325851.1325954

Incoming Non-self Citations Over Time

Authors

1. Benjamin Arai (University of California Riverside)
2. Gautam Das (University of Texas, Arlington)
3. Dimitrios Gunopulos (University of California Riverside)
4. Nick Koudas (University of Toronto)

BibTeX Citation

@article{arai_vldb07,
        title = {{Anytime Measures for Top-k Algorithms}},
        author = {Arai, Benjamin and Das, Gautam and Gunopulos, Dimitrios and Koudas, Nick},
        journal = {PVLDB},
        series = {{VLDB} '07},
        pages = {914--925},
        doi = {10.1145/1325851.1325954},
        url = {https://doi.org/10.1145/1325851.1325954},
        year = {2007}
}

Incoming Citations (Sorted by Pagerank)

Showing 4 of 4 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
5,138	Robust and Efficient Algorithms for Rank Join Evaluation	2009	SIGMOD	6.3495536e-05
6,175	Ad-Hoc Aggregations of Ranked Lists in the Presence of Hierarchies	2008	SIGMOD	5.9508648e-05
8,378	Discovering the Skyline of Web Databases	2016	VLDB	5.4387677e-05
12,494	Skip-and-Prune: Cosine-based Top-K Query Processing for Efficient Context-Sensitive Document Retrieval	2009	SIGMOD	5.093636e-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
5	Optimal Aggregation Algorithms for Middleware [Extended Abstract]	2001	PODS	0.0010828372
56	M-tree: An Efficient Access Method for Similarity Search in Metric Spaces	1997	VLDB	0.00040719947
101	Selectivity Estimation Without the Attribute Value Independence Assumption	1997	VLDB	0.00034376651
108	Optimizing Multi-Feature Queries for Image Databases	2000	VLDB	0.00033228866
170	Combining Fuzzy Information from Multiple Systems	1996	PODS	0.00027376361
333	The Onion Technique: Indexing for Linear Optimization Queries	2000	SIGMOD	0.0002089582
402	Fuzzy Queries in Multimedia Database Systems	1998	PODS	0.00019072958
407	PREFER: A System for the Efficient Execution of Multiparametric Ranked Queries	2001	SIGMOD	0.00019021441
499	Supporting Incremental Join Queries on Ranked Inputs	2001	VLDB	0.00017431827
509	Supporting Top-k Join Queries in Relational Databases	2003	VLDB	0.00017220967
635	Evaluating Top-k Selection Queries	1999	VLDB	0.00015527042
827	Minimal Probing: Supporting Expensive Predicates for Top-k Queries	2002	SIGMOD	0.00013769938
850	Approximating Multi-Dimensional Aggregate Range Queries Over Real Attributes	2000	SIGMOD	0.00013619394
1,519	Top-k Query Evaluation with Probabilistic Guarantees	2004	VLDB	0.00010513777
2,149	Probabilistic Optimization of Top N Queries	1999	VLDB	9.0821709e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	11,954	Durable Top-k Queries on Temporal Data	2018	VLDB
2	3,702	Best Position Algorithms for Top-k Queries	2007	VLDB
3	3,500	Progressive and Selective Merge: Computing Top-K with Ad-hoc Ranking Functions	2007	SIGMOD
4	1,967	IO-Top-k: Index-access Optimized Top-k Query Processing	2006	VLDB
5	2,427	Processing a Large Number of Continuous Preference Top-k Queries	2012	SIGMOD
6	7,934	Ranking Large Temporal Data	2012	VLDB
7	12,308	Optimal Top-k Generation of Attribute Combinations based on Ranked Lists	2012	SIGMOD
8	7,299	Efficient and Generic Evaluation of Ranked Queries	2011	SIGMOD
9	8,281	Efficient Top-K Processing Over Query-Dependent Functions	2008	VLDB
10	1,519	Top-k Query Evaluation with Probabilistic Guarantees	2004	VLDB