Efficient Top-K Processing Over Query-Dependent Functions

Summary: Efficiently answers top-k queries when each item’s score is an item-specific function of a query-time parameter. Workload-aware interval compression summarizes scores across parameter values, enabling pruning without evaluating all functions or materializing a full score table. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: ha72271dfdeb2dac6
Venue: VLDB
Year: 2008
Pagerank: 5.3324907e-05
Overall Rank: 8,458 | 43.16%
DOI: 10.14778/1453856.1453975

Incoming Non-self Citations Over Time

Authors

1. Lin Guo (Yahoo)
2. Sihem Amer Yahia (Yahoo)
3. Raghu Ramakrishnan (Yahoo)
4. Jayavel Shanmugasundaram (Yahoo)
5. Utkarsh Srivastava (Yahoo)
6. Erik Vee (Yahoo)

BibTeX Citation

@article{guo_vldb08,
        title = {{Efficient Top-K Processing Over Query-Dependent Functions}},
        author = {Guo, Lin and Yahia, Sihem Amer and Ramakrishnan, Raghu and Shanmugasundaram, Jayavel and Srivastava, Utkarsh and Vee, Erik},
        journal = {PVLDB},
        series = {{VLDB} '08},
        volume = {1},
        number = {1},
        pages = {1044--1055},
        doi = {10.14778/1453856.1453975},
        url = {https://doi.org/10.14778/1453856.1453975},
        year = {2008}
}

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
12,763	Database-support for Continuous Prediction Queries over Streaming Data	2010	VLDB	4.9769913e-05

Outgoing Citations (Sorted by Pagerank)

Showing 9 of 9 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.0010679903
172	Combining Fuzzy Information from Multiple Systems	1996	PODS	0.00026824625
284	Balancing Histogram Optimality and Practicality for Query Result Size Estimation	1995	SIGMOD	0.00022205848
396	On Saying "Enough Already!" in SQL	1997	SIGMOD	0.00019153354
418	PREFER: A System for the Efficient Execution of Multiparametric Ranked Queries	2001	SIGMOD	0.00018609134
451	Filtering Algorithms and Implementation for Very Fast Publish/Subscribe Systems	2001	SIGMOD	0.00018017347
962	RankSQL: Query Algebra and Optimization for Relational Top-k Queries	2005	SIGMOD	0.00012818013
1,122	Least Expected Cost Query Optimization: An Exercise in Utility	1999	PODS	0.00011933634
2,183	Probabilistic Optimization of Top N Queries	1999	VLDB	8.9044171e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	3,380	Ad-hoc Top-k Query Answering for Data Streams	2007	VLDB
2	12,329	Efficient Top-k Indexing via General Reductions	2016	PODS
3	2,008	IO-Top-k: Index-access Optimized Top-k Query Processing	2006	VLDB
4	1,477	Efficient Processing of Top-k Spatial Preference Queries	2011	VLDB
5	7,329	Anytime Measures for Top-k Algorithms	2007	VLDB
6	12,790	Skip-and-Prune: Cosine-based Top-K Query Processing for Efficient Context-Sensitive Document Retrieval	2009	SIGMOD
7	2,485	Processing a Large Number of Continuous Preference Top-k Queries	2012	SIGMOD
8	1,535	Top-k Query Evaluation with Probabilistic Guarantees	2004	VLDB
9	12,605	Optimal Top-k Generation of Attribute Combinations based on Ranked Lists	2012	SIGMOD
10	7,396	Efficient and Generic Evaluation of Ranked Queries	2011	SIGMOD