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: 3905
Venue: SIGMOD
Year: 2007
Pagerank: 7.3597562e-05
Overall Rank: 3,500 | 75.99%
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,319	Secure kNN Computation on Encrypted Databases	2009	SIGMOD	8.7577497e-05
8,026	A New Approach for Processing Ranked Subsequence Matching Based on Ranked Union	2011	SIGMOD	5.5049255e-05
8,029	Distributed Threshold Querying of General Functions by a Difference of Monotonic Representation	2011	VLDB	5.5045998e-05
8,133	Evaluating Top-k Queries with Inconsistency Degrees	2020	VLDB	5.4813895e-05
9,525	Towards Indexing Functions: Answering Scalar Product Queries	2014	SIGMOD	5.2555551e-05
10,109	QueryArtisan: Generating Data Manipulation Codes for Ad-hoc Analysis in Data Lakes	2025	VLDB	5.1347137e-05
12,308	Optimal Top-k Generation of Attribute Combinations based on Ranked Lists	2012	SIGMOD	5.093636e-05
12,331	Answering Top-k Queries Over a Mixture of Attractive and Repulsive Dimensions	2012	VLDB	5.093636e-05
12,368	Exact Indexing for Support Vector Machines	2011	SIGMOD	5.093636e-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.0010828372
145	Efficient Processing of Spatial Joins Using R-trees	1993	SIGMOD	0.00029548428
393	Bottom-Up Computation of Sparse and Iceberg CUBEs	1999	SIGMOD	0.0001934104
402	Fuzzy Queries in Multimedia Database Systems	1998	PODS	0.00019072958
1,525	Incremental Distance Join Algorithms for Spatial Databases	1998	SIGMOD	0.00010493702
1,967	IO-Top-k: Index-access Optimized Top-k Query Processing	2006	VLDB	9.3804693e-05
2,813	KLEE: A Framework for Distributed Top-k Query Algorithms	2005	VLDB	8.0975254e-05
4,587	Answering Top-k Queries with Multi-Dimensional Selections: The Ranking Cube Approach	2006	VLDB	6.6170389e-05
6,374	Ranking Objects by Exploiting Relationships: Computing Top-K over Aggregation	2006	SIGMOD	5.8945632e-05
6,658	CURE for Cubes: Cubing Using a ROLAP Engine	2006	VLDB	5.8104851e-05
7,352	Boolean + Ranking: Querying a Database by K-Constrained Optimization	2006	SIGMOD	5.6353412e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	3,007	Towards Robust Indexing for Ranked Queries	2006	VLDB
2	8,281	Efficient Top-K Processing Over Query-Dependent Functions	2008	VLDB
3	5,601	Optimal Join Algorithms Meet Top-k	2020	SIGMOD
4	7,934	Ranking Large Temporal Data	2012	VLDB
5	3,317	Ad-hoc Top-k Query Answering for Data Streams	2007	VLDB
6	1,967	IO-Top-k: Index-access Optimized Top-k Query Processing	2006	VLDB
7	3,702	Best Position Algorithms for Top-k Queries	2007	VLDB
8	7,299	Efficient and Generic Evaluation of Ranked Queries	2011	SIGMOD
9	7,550	Processing Top-k Join Queries	2010	VLDB
10	12,308	Optimal Top-k Generation of Attribute Combinations based on Ranked Lists	2012	SIGMOD