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: 10324
Venue: VLDB
Year: 2010
Pagerank: 5.4548122e-05
Overall Rank: 8,319 | 42.93%
DOI: 10.14778/1920841.1920952

Incoming Non-self Citations Over Time

Authors

1. Xavier Martinez-Palau (Polytechnic University of Catalonia)
2. David Dominguez-Sal (Polytechnic University of Catalonia)
3. Josep Lluis Larriba-Pey (Polytechnic University of Catalonia)

BibTeX Citation

@article{martinezpalau_vldb10,
        title = {{Two-way Replacement Selection}},
        author = {Martinez-Palau, Xavier and Dominguez-Sal, David and Larriba-Pey, Josep Lluis},
        journal = {PVLDB},
        series = {{VLDB} '10},
        volume = {3},
        number = {1},
        pages = {871--884},
        doi = {10.14778/1920841.1920952},
        url = {https://doi.org/10.14778/1920841.1920952},
        year = {2010}
}

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
2,378	The Uncracked Pieces in Database Cracking	2014	VLDB	8.6682285e-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,801	Memory Management during Run Generation in External Sorting	1998	SIGMOD	9.7286236e-05
5,808	Sorting Hierarchical Data in External Memory for Archiving	2008	VLDB	6.0801876e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	4,177	SIMD- and Cache-Friendly Algorithm for Sorting an Array of Structures	2015	VLDB
2	12,033	A Study of Sorting Algorithms on Approximate Memory	2016	SIGMOD
3	7,705	A Study of Sort Algorithms for Multiprocessor Database Machines	1986	VLDB
4	11,220	Sorting on Byte-Addressable Storage: The Resurgence of Tree Structure	2024	VLDB
5	3,842	FastSort: A Distributed Single-Input Single-Output External Sort	1990	SIGMOD
6	4,708	Memory-Adaptive External Sorting	1993	VLDB
7	8,451	Buffering and Read-Ahead Strategies for External Mergesort	1998	VLDB
8	14,432	Stable Set and Multiset Operations in Optimal Time and Space	1988	PODS
9	4,955	Dynamic Memory Adjustment for External Mergesort	1997	VLDB
10	1,801	Memory Management during Run Generation in External Sorting	1998	SIGMOD