Towards Robust Indexing for Ranked Queries

Summary: Introduces robust layered indexes for top-k queries, minimizing tuples in the first k layers for every linear ranking function. Characterizes robustness exactly and provides polynomial-time exact and dimension-aware approximate constructions with improved empirical performance. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: h2545d3cae95a2358
Venue: VLDB
Year: 2006
Pagerank: 7.6867401e-05
Overall Rank: 3,068 | 79.38%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Dong Xin (University of Illinois Urbana-Champaign)
2. Chen Chen (University of Illinois Urbana-Champaign)
3. Jiawei Han (University of Illinois Urbana-Champaign)

BibTeX Citation

@article{xin_vldb06,
        title = {{Towards Robust Indexing for Ranked Queries}},
        author = {Xin, Dong and Chen, Chen and Han, Jiawei},
        journal = {PVLDB},
        series = {{VLDB} '06},
        pages = {235--246},
        year = {2006}
}

Incoming Citations (Sorted by Pagerank)

Showing 12 of 12 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
942	SPARK: Top-k Keyword Query in Relational Databases	2007	SIGMOD	0.00012956137
2,955	Answering Why-not Questions on Reverse Top-k Queries	2015	VLDB	7.8102237e-05
4,614	Branch-and-Bound Algorithm for Reverse Top-k Queries	2013	SIGMOD	6.5014577e-05
4,831	Efficient Computation of Regret-ratio Minimizing Set: A Compact Maxima Representative	2017	SIGMOD	6.3897334e-05
5,353	Why Not Yet: Fixing a Top-k Ranking that Is Not Fair to Individuals	2023	VLDB	6.1637765e-05
5,913	Reverse k-Ranks Query	2014	VLDB	5.9500931e-05
6,716	RRR: Rank-Regret Representative	2019	SIGMOD	5.6993087e-05
7,394	Efficient and Generic Evaluation of Ranked Queries	2011	SIGMOD	5.5370795e-05
11,712	rkHit: Representative Query with Uncertain Preference	2023	SIGMOD	4.9793485e-05
12,150	Top-k Queries over Digital Traces	2019	SIGMOD	4.9793485e-05
12,376	Query Reranking As A Service	2016	VLDB	4.9793485e-05
12,622	Answering Top-k Queries Over a Mixture of Attractive and Repulsive Dimensions	2012	VLDB	4.9793485e-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
5	Optimal Aggregation Algorithms for Middleware [Extended Abstract]	2001	PODS	0.0010679641
172	Combining Fuzzy Information from Multiple Systems	1996	PODS	0.00026835705
342	The Onion Technique: Indexing for Linear Optimization Queries	2000	SIGMOD	0.00020530255
412	Fuzzy Queries in Multimedia Database Systems	1998	PODS	0.00018694414
418	PREFER: A System for the Efficient Execution of Multiparametric Ranked Queries	2001	SIGMOD	0.00018617842
643	Evaluating Top-k Selection Queries	1999	VLDB	0.00015217076
1,237	Processing Queries By Linear Constraints	1997	PODS	0.00011396286
1,589	Efficient Searching with Linear Constraints (Extended Abstract)	1998	PODS	0.00010139591

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	1,559	On Two-Dimensional Indexability and Optimal Range Search Indexing (Extended Abstract)	1999	PODS
2	12,323	Efficient Top-k Indexing via General Reductions	2016	PODS
3	2,006	IO-Top-k: Index-access Optimized Top-k Query Processing	2006	VLDB
4	3,566	Progressive and Selective Merge: Computing Top-K with Ad-hoc Ranking Functions	2007	SIGMOD
5	2,485	Processing a Large Number of Continuous Preference Top-k Queries	2012	SIGMOD
6	8,102	Ranking Large Temporal Data	2012	VLDB
7	12,096	Dynamic Interleaving of Content and Structure for Robust Indexing of Semi-Structured Hierarchical Data	2020	VLDB
8	12,599	Optimal Top-k Generation of Attribute Combinations based on Ranked Lists	2012	SIGMOD
9	7,776	Efficient Indexes for Diverse Top-k Range Queries	2020	PODS
10	7,394	Efficient and Generic Evaluation of Ranked Queries	2011	SIGMOD