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: 9440
Venue: VLDB
Year: 2006
Pagerank: 7.082382e-05
Overall Rank: 3,447 | 76.05%
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,202	SPARK: Top-k Keyword Query in Relational Databases	2007	SIGMOD	0.0001333126
3,100	Answering Why-not Questions on Reverse Top-k Queries	2015	VLDB	7.5625111e-05
5,074	Branch-and-Bound Algorithm for Reverse Top-k Queries	2013	SIGMOD	5.7113169e-05
5,113	Efficient Computation of Regret-ratio Minimizing Set: A Compact Maxima Representative	2017	SIGMOD	5.6827696e-05
5,839	Why Not Yet: Fixing a Top-k Ranking that Is Not Fair to Individuals	2023	VLDB	5.3073497e-05
6,219	Reverse k-Ranks Query	2014	VLDB	5.1458862e-05
6,804	RRR: Rank-Regret Representative	2019	SIGMOD	4.917138e-05
7,273	Efficient and Generic Evaluation of Ranked Queries	2011	SIGMOD	4.775366e-05
11,197	rkHit: Representative Query with Uncertain Preference	2023	SIGMOD	4.1905499e-05
11,660	Top-k Queries over Digital Traces	2019	SIGMOD	4.1905499e-05
11,891	Query Reranking As A Service	2016	VLDB	4.1905499e-05
12,143	Answering Top-k Queries Over a Mixture of Attractive and Repulsive Dimensions	2012	VLDB	4.1905499e-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
8	Optimal Aggregation Algorithms for Middleware [Extended Abstract]	2001	PODS	0.0015436578
72	Combining Fuzzy Information from Multiple Systems	1996	PODS	0.00058498396
171	Fuzzy Queries in Multimedia Database Systems	1998	PODS	0.00038843975
428	The Onion Technique: Indexing for Linear Optimization Queries	2000	SIGMOD	0.0002349868
464	PREFER: A System for the Efficient Execution of Multiparametric Ranked Queries	2001	SIGMOD	0.00022476798
802	Evaluating Top-k Selection Queries	1999	VLDB	0.00016440813
1,171	Processing Queries By Linear Constraints	1997	PODS	0.00013507216
1,499	Efficient Searching with Linear Constraints (Extended Abstract)	1998	PODS	0.00011643887

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
1,183	On Two-Dimensional Indexability and Optimal Range Search Indexing (Extended Abstract)	1999	PODS	0.00013444058
11,833	Efficient Top-k Indexing via General Reductions	2016	PODS	4.1905499e-05
2,014	IO-Top-k: Index-access Optimized Top-k Query Processing	2006	VLDB	9.7982231e-05
3,911	Progressive and Selective Merge: Computing Top-K with Ad-hoc Ranking Functions	2007	SIGMOD	6.6343292e-05
2,967	Processing a Large Number of Continuous Preference Top-k Queries	2012	SIGMOD	7.7975455e-05
7,512	Ranking Large Temporal Data	2012	VLDB	4.7135369e-05
11,603	Dynamic Interleaving of Content and Structure for Robust Indexing of Semi-Structured Hierarchical Data	2020	VLDB	4.1905499e-05
12,119	Optimal Top-k Generation of Attribute Combinations based on Ranked Lists	2012	SIGMOD	4.1905499e-05
8,921	Efficient Indexes for Diverse Top-k Range Queries	2020	PODS	4.4229886e-05
7,273	Efficient and Generic Evaluation of Ranked Queries	2011	SIGMOD	4.775366e-05