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.1743861e-05
Overall Rank: 3,578 | 76.02%
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,321	Secure kNN Computation on Encrypted Databases	2009	SIGMOD	8.6338201e-05
8,084	Evaluating Top-k Queries with Inconsistency Degrees	2020	VLDB	5.3751435e-05
8,209	A New Approach for Processing Ranked Subsequence Matching Based on Ranked Union	2011	SIGMOD	5.3610809e-05
8,213	Distributed Threshold Querying of General Functions by a Difference of Monotonic Representation	2011	VLDB	5.3607592e-05
9,739	Towards Indexing Functions: Answering Scalar Product Queries	2014	SIGMOD	5.1187707e-05
10,371	QueryArtisan: Generating Data Manipulation Codes for Ad-hoc Analysis in Data Lakes	2025	VLDB	5.0010514e-05
12,648	Optimal Top-k Generation of Attribute Combinations based on Ranked Lists	2012	SIGMOD	4.9605343e-05
12,671	Answering Top-k Queries Over a Mixture of Attractive and Repulsive Dimensions	2012	VLDB	4.9605343e-05
12,708	Exact Indexing for Support Vector Machines	2011	SIGMOD	4.9605343e-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.0010688884
146	Efficient Processing of Spatial Joins Using R-trees	1993	SIGMOD	0.000289618
404	Bottom-Up Computation of Sparse and Iceberg CUBEs	1999	SIGMOD	0.00019034819
413	Fuzzy Queries in Multimedia Database Systems	1998	PODS	0.00018638335
1,554	Incremental Distance Join Algorithms for Spatial Databases	1998	SIGMOD	0.00010236406
2,019	IO-Top-k: Index-access Optimized Top-k Query Processing	2006	VLDB	9.1666472e-05
2,880	KLEE: A Framework for Distributed Top-k Query Algorithms	2005	VLDB	7.8948229e-05
4,668	Answering Top-k Queries with Multi-Dimensional Selections: The Ranking Cube Approach	2006	VLDB	6.4622135e-05
6,517	Ranking Objects by Exploiting Relationships: Computing Top-K over Aggregation	2006	SIGMOD	5.7425601e-05
6,818	CURE for Cubes: Cubing Using a ROLAP Engine	2006	VLDB	5.6589988e-05
7,521	Boolean + Ranking: Querying a Database by K-Constrained Optimization	2006	SIGMOD	5.4881075e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	8,473	Efficient Top-K Processing Over Query-Dependent Functions	2008	VLDB
2	3,078	Towards Robust Indexing for Ranked Queries	2006	VLDB
3	4,730	Optimal Join Algorithms Meet Top-k	2020	SIGMOD
4	3,391	Ad-hoc Top-k Query Answering for Data Streams	2007	VLDB
5	8,127	Ranking Large Temporal Data	2012	VLDB
6	2,019	IO-Top-k: Index-access Optimized Top-k Query Processing	2006	VLDB
7	3,623	Best Position Algorithms for Top-k Queries	2007	VLDB
8	7,413	Efficient and Generic Evaluation of Ranked Queries	2011	SIGMOD
9	7,637	Processing Top-k Join Queries	2010	VLDB
10	12,648	Optimal Top-k Generation of Attribute Combinations based on Ranked Lists	2012	SIGMOD