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.6831067e-05
Overall Rank: 3,070 | 79.37%
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.00012950177
2,958	Answering Why-not Questions on Reverse Top-k Queries	2015	VLDB	7.80653e-05
4,616	Branch-and-Bound Algorithm for Reverse Top-k Queries	2013	SIGMOD	6.4983802e-05
4,833	Efficient Computation of Regret-ratio Minimizing Set: A Compact Maxima Representative	2017	SIGMOD	6.3867086e-05
5,359	Why Not Yet: Fixing a Top-k Ranking that Is Not Fair to Individuals	2023	VLDB	6.1608586e-05
5,916	Reverse k-Ranks Query	2014	VLDB	5.9472799e-05
6,721	RRR: Rank-Regret Representative	2019	SIGMOD	5.6966108e-05
7,396	Efficient and Generic Evaluation of Ranked Queries	2011	SIGMOD	5.5344583e-05
11,718	rkHit: Representative Query with Uncertain Preference	2023	SIGMOD	4.9769913e-05
12,156	Top-k Queries over Digital Traces	2019	SIGMOD	4.9769913e-05
12,382	Query Reranking As A Service	2016	VLDB	4.9769913e-05
12,628	Answering Top-k Queries Over a Mixture of Attractive and Repulsive Dimensions	2012	VLDB	4.9769913e-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.0010679903
172	Combining Fuzzy Information from Multiple Systems	1996	PODS	0.00026824625
342	The Onion Technique: Indexing for Linear Optimization Queries	2000	SIGMOD	0.00020520649
413	Fuzzy Queries in Multimedia Database Systems	1998	PODS	0.00018686769
418	PREFER: A System for the Efficient Execution of Multiparametric Ranked Queries	2001	SIGMOD	0.00018609134
643	Evaluating Top-k Selection Queries	1999	VLDB	0.0001521012
1,239	Processing Queries By Linear Constraints	1997	PODS	0.00011391184
1,590	Efficient Searching with Linear Constraints (Extended Abstract)	1998	PODS	0.00010134811

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,329	Efficient Top-k Indexing via General Reductions	2016	PODS
3	2,008	IO-Top-k: Index-access Optimized Top-k Query Processing	2006	VLDB
4	3,567	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,109	Ranking Large Temporal Data	2012	VLDB
7	12,102	Dynamic Interleaving of Content and Structure for Robust Indexing of Semi-Structured Hierarchical Data	2020	VLDB
8	12,605	Optimal Top-k Generation of Attribute Combinations based on Ranked Lists	2012	SIGMOD
9	7,784	Efficient Indexes for Diverse Top-k Range Queries	2020	PODS
10	7,396	Efficient and Generic Evaluation of Ranked Queries	2011	SIGMOD