Progressive and Selective Merge: Computing Top-K with Ad-hoc Ranking Functions

Summary: Progressive and Selective Merge: top-k with ad-hoc ranking functions. Index-merge over tree indices; double-heap for progressive search and generation; join-signature materialization prunes empty-states, enabling ~10x speed-up. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: h37a71a8f82014fb0
Venue: SIGMOD
Year: 2007
Pagerank: 7.2015969e-05
Overall Rank: 3,566 | 76.03%
DOI: 10.1145/1247480.1247494

Incoming Non-self Citations Over Time

Authors

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

BibTeX Citation

@inproceedings{xin_sigmod07,
        title = {{Progressive and Selective Merge: Computing Top-K with Ad-hoc Ranking Functions}},
        author = {Xin, Dong and Han, Jiawei and Chang, Kevin Chen-Chuan},
        series = {{SIGMOD} '07},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/1247480.1247494},
        url = {https://dl.acm.org/doi/10.1145/1247480.1247494},
        year = {2007}
}

Incoming Citations (Sorted by Pagerank)

Showing 9 of 9 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
2,307	Secure kNN Computation on Encrypted Databases	2009	SIGMOD	8.6665657e-05
8,062	Evaluating Top-k Queries with Inconsistency Degrees	2020	VLDB	5.3955302e-05
8,186	A New Approach for Processing Ranked Subsequence Matching Based on Ranked Union	2011	SIGMOD	5.3814143e-05
8,189	Distributed Threshold Querying of General Functions by a Difference of Monotonic Representation	2011	VLDB	5.3810913e-05
9,702	Towards Indexing Functions: Answering Scalar Product Queries	2014	SIGMOD	5.1381851e-05
10,337	QueryArtisan: Generating Data Manipulation Codes for Ad-hoc Analysis in Data Lakes	2025	VLDB	5.0200193e-05
12,599	Optimal Top-k Generation of Attribute Combinations based on Ranked Lists	2012	SIGMOD	4.9793485e-05
12,622	Answering Top-k Queries Over a Mixture of Attractive and Repulsive Dimensions	2012	VLDB	4.9793485e-05
12,659	Exact Indexing for Support Vector Machines	2011	SIGMOD	4.9793485e-05

Outgoing Citations (Sorted by Pagerank)

Showing 11 of 11 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
146	Efficient Processing of Spatial Joins Using R-trees	1993	SIGMOD	0.00029061754
403	Bottom-Up Computation of Sparse and Iceberg CUBEs	1999	SIGMOD	0.0001910396
412	Fuzzy Queries in Multimedia Database Systems	1998	PODS	0.00018694414
1,552	Incremental Distance Join Algorithms for Spatial Databases	1998	SIGMOD	0.00010275036
2,006	IO-Top-k: Index-access Optimized Top-k Query Processing	2006	VLDB	9.199795e-05
2,874	KLEE: A Framework for Distributed Top-k Query Algorithms	2005	VLDB	7.9221111e-05
4,648	Answering Top-k Queries with Multi-Dimensional Selections: The Ranking Cube Approach	2006	VLDB	6.4867043e-05
6,502	Ranking Objects by Exploiting Relationships: Computing Top-K over Aggregation	2006	SIGMOD	5.7643387e-05
6,795	CURE for Cubes: Cubing Using a ROLAP Engine	2006	VLDB	5.6804621e-05
7,497	Boolean + Ranking: Querying a Database by K-Constrained Optimization	2006	SIGMOD	5.5089205e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	8,449	Efficient Top-K Processing Over Query-Dependent Functions	2008	VLDB
2	3,068	Towards Robust Indexing for Ranked Queries	2006	VLDB
3	4,752	Optimal Join Algorithms Meet Top-k	2020	SIGMOD
4	8,102	Ranking Large Temporal Data	2012	VLDB
5	3,379	Ad-hoc Top-k Query Answering for Data Streams	2007	VLDB
6	2,006	IO-Top-k: Index-access Optimized Top-k Query Processing	2006	VLDB
7	3,656	Best Position Algorithms for Top-k Queries	2007	VLDB
8	7,394	Efficient and Generic Evaluation of Ranked Queries	2011	SIGMOD
9	7,615	Processing Top-k Join Queries	2010	VLDB
10	12,599	Optimal Top-k Generation of Attribute Combinations based on Ranked Lists	2012	SIGMOD