Two-way Replacement Selection

Summary: Two-way Replacement Selection (2WRS) generalizes RS with two heaps to generate runs larger than memory in a stable, dataset-agnostic way. Adaptive heap management and per-record assignment keep run lengths at least RS, often longer, with speedups up to 2.5x when RS fails on tricky inputs. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 10133
Venue: VLDB
Year: 2010
Pagerank: 4.5839826e-05
Overall Rank: 8,112 | 43.57%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
2,987	The Uncracked Pieces in Database Cracking	2014	VLDB	7.7787088e-05

Outgoing Citations (Sorted by Pagerank)

Showing 2 of 2 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
1,290	Memory Management during Run Generation in External Sorting	1998	SIGMOD	0.00012795586
5,207	Sorting Hierarchical Data in External Memory for Archiving	2008	VLDB	5.6297675e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
4,655	SIMD- and Cache-Friendly Algorithm for Sorting an Array of Structures	2015	VLDB	6.0221672e-05
11,832	A Study of Sorting Algorithms on Approximate Memory	2016	SIGMOD	4.1945683e-05
7,460	A Study of Sort Algorithms for Multiprocessor Database Machines	1986	VLDB	4.7241128e-05
11,009	Sorting on Byte-Addressable Storage: The Resurgence of Tree Structure	2024	VLDB	4.1945683e-05
2,666	FastSort: A Distributed Single-Input Single-Output External Sort	1990	SIGMOD	8.3422378e-05
4,741	Memory-Adaptive External Sorting	1993	VLDB	5.95905e-05
8,004	Buffering and Read-Ahead Strategies for External Mergesort	1998	VLDB	4.6085722e-05
14,232	Stable Set and Multiset Operations in Optimal Time and Space	1988	PODS	-
4,832	Dynamic Memory Adjustment for External Mergesort	1997	VLDB	5.8924168e-05
1,290	Memory Management during Run Generation in External Sorting	1998	SIGMOD	0.00012795586