Towards Robust Indexing for Ranked Queries

Summary: Introduces sequentially layered indexing for robust top-k query answering under arbitrary linear rankings. Robustness minimizes top-k tuple counts for all k; provides a necessary and sufficient condition, an exact O(n^d log n) construction, and an efficient O(2^d n (log n)^{r(d)-1}) approximation with experiments. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 9439
Venue: VLDB
Year: 2006
Pagerank: 7.069675e-05
Overall Rank: 3,463 | 75.91%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 12 of 12 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,201	SPARK: Top-k Keyword Query in Relational Databases	2007	SIGMOD	0.0001334371
3,095	Answering Why-not Questions on Reverse Top-k Queries	2015	VLDB	7.5692859e-05
5,095	Branch-and-Bound Algorithm for Reverse Top-k Queries	2013	SIGMOD	5.7021328e-05
5,116	Efficient Computation of Regret-ratio Minimizing Set: A Compact Maxima Representative	2017	SIGMOD	5.6830089e-05
5,826	Why Not Yet: Fixing a Top-k Ranking that Is Not Fair to Individuals	2023	VLDB	5.3124507e-05
6,222	Reverse k-Ranks Query	2014	VLDB	5.1503175e-05
6,816	RRR: Rank-Regret Representative	2019	SIGMOD	4.9173197e-05
7,276	Efficient and Generic Evaluation of Ranked Queries	2011	SIGMOD	4.7798595e-05
11,195	rkHit: Representative Query with Uncertain Preference	2023	SIGMOD	4.1945683e-05
11,655	Top-k Queries over Digital Traces	2019	SIGMOD	4.1945683e-05
11,883	Query Reranking As A Service	2016	VLDB	4.1945683e-05
12,135	Answering Top-k Queries Over a Mixture of Attractive and Repulsive Dimensions	2012	VLDB	4.1945683e-05

Outgoing Citations (Sorted by Pagerank)

Showing 8 of 8 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
72	Combining Fuzzy Information from Multiple Systems	1996	PODS	0.00058577335
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
805	Evaluating Top-k Selection Queries	1999	VLDB	0.00016437265
1,172	Processing Queries By Linear Constraints	1997	PODS	0.00013505441
1,502	Efficient Searching with Linear Constraints (Extended Abstract)	1998	PODS	0.00011643406

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
1,182	On Two-Dimensional Indexability and Optimal Range Search Indexing (Extended Abstract)	1999	PODS	0.00013455963
11,825	Efficient Top-k Indexing via General Reductions	2016	PODS	4.1945683e-05
2,009	IO-Top-k: Index-access Optimized Top-k Query Processing	2006	VLDB	9.7977564e-05
3,908	Progressive and Selective Merge: Computing Top-K with Ad-hoc Ranking Functions	2007	SIGMOD	6.6392878e-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
11,599	Dynamic Interleaving of Content and Structure for Robust Indexing of Semi-Structured Hierarchical Data	2020	VLDB	4.1945683e-05
12,111	Optimal Top-k Generation of Attribute Combinations based on Ranked Lists	2012	SIGMOD	4.1945683e-05
8,919	Efficient Indexes for Diverse Top-k Range Queries	2020	PODS	4.427232e-05
7,276	Efficient and Generic Evaluation of Ranked Queries	2011	SIGMOD	4.7798595e-05