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: 9926
Venue: VLDB
Year: 2008
Pagerank: 5.4574671e-05
Overall Rank: 8,281 | 43.19%
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,466	Database-support for Continuous Prediction Queries over Streaming Data	2010	VLDB	5.093636e-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.0010828372
170	Combining Fuzzy Information from Multiple Systems	1996	PODS	0.00027376361
274	Balancing Histogram Optimality and Practicality for Query Result Size Estimation	1995	SIGMOD	0.00022645621
380	On Saying "Enough Already!" in SQL	1997	SIGMOD	0.00019563191
407	PREFER: A System for the Efficient Execution of Multiparametric Ranked Queries	2001	SIGMOD	0.00019021441
441	Filtering Algorithms and Implementation for Very Fast Publish/Subscribe Systems	2001	SIGMOD	0.00018407547
973	RankSQL: Query Algebra and Optimization for Relational Top-k Queries	2005	SIGMOD	0.00012874284
1,104	Least Expected Cost Query Optimization: An Exercise in Utility	1999	PODS	0.00012157634
2,149	Probabilistic Optimization of Top N Queries	1999	VLDB	9.0821709e-05

Semantically Similar Papers

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