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: 9630
Venue: VLDB
Year: 2006
Pagerank: 7.8583548e-05
Overall Rank: 3,007 | 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
930	SPARK: Top-k Keyword Query in Relational Databases	2007	SIGMOD	0.0001312728
2,895	Answering Why-not Questions on Reverse Top-k Queries	2015	VLDB	7.9829449e-05
4,514	Branch-and-Bound Algorithm for Reverse Top-k Queries	2013	SIGMOD	6.6500719e-05
4,727	Efficient Computation of Regret-ratio Minimizing Set: A Compact Maxima Representative	2017	SIGMOD	6.5362946e-05
5,278	Why Not Yet: Fixing a Top-k Ranking that Is Not Fair to Individuals	2023	VLDB	6.2856584e-05
5,796	Reverse k-Ranks Query	2014	VLDB	6.0859929e-05
6,592	RRR: Rank-Regret Representative	2019	SIGMOD	5.830041e-05
7,299	Efficient and Generic Evaluation of Ranked Queries	2011	SIGMOD	5.6513289e-05
11,397	rkHit: Representative Query with Uncertain Preference	2023	SIGMOD	5.093636e-05
11,850	Top-k Queries over Digital Traces	2019	SIGMOD	5.093636e-05
12,083	Query Reranking As A Service	2016	VLDB	5.093636e-05
12,331	Answering Top-k Queries Over a Mixture of Attractive and Repulsive Dimensions	2012	VLDB	5.093636e-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.0010828372
170	Combining Fuzzy Information from Multiple Systems	1996	PODS	0.00027376361
333	The Onion Technique: Indexing for Linear Optimization Queries	2000	SIGMOD	0.0002089582
402	Fuzzy Queries in Multimedia Database Systems	1998	PODS	0.00019072958
407	PREFER: A System for the Efficient Execution of Multiparametric Ranked Queries	2001	SIGMOD	0.00019021441
635	Evaluating Top-k Selection Queries	1999	VLDB	0.00015527042
1,219	Processing Queries By Linear Constraints	1997	PODS	0.00011620957
1,561	Efficient Searching with Linear Constraints (Extended Abstract)	1998	PODS	0.00010361147

Semantically Similar Papers

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