Para acceder a los documentos con el texto completo, por favor, siga el siguiente enlace: http://hdl.handle.net/2117/25227

Two-way replacement selection
Martínez Palau, Xavier; Domínguez Sal, David; Larriba Pey, Josep
Universitat Politècnica de Catalunya. Departament d'Arquitectura de Computadors; Universitat Politècnica de Catalunya. DAMA-UPC - Data Management Group
The performance of external sorting using merge sort is highly dependent on the length of the runs generated. One of the most commonly used run generation strategies is Replacement Selection (RS) because, on average, it generates runs that are twice the size of the memory available. However, the length of the runs generated by RS is downsized for data with certain characteristics, like inputs sorted inversely with respect to the desired output order. The goal of this paper is to propose and analyze two-way replacement selection (2WRS), which is a generalization of RS obtained by implementing two heaps instead of the single heap implemented by RS. The appropriate management of these two heaps allows generating runs larger than the memory available in a stable way, i.e. independent from the characteristics of the datasets. Depending on the changing characteristics of the input dataset, 2WRS assigns a new data record to one or the other heap, and grows or shrinks each heap, accommodating to the growing or decreasing tendency of the dataset. On average, 2WRS creates runs of at least the length generated by RS, and longer for datasets that combine increasing and decreasing data subsets. We tested both algorithms on large datasets with different characteristics and 2WRS achieves speedups at least similar to RS, and over 2.5 when RS fails to generate large runs.
Àrees temàtiques de la UPC::Informàtica::Programació
Sorting (Electronic computers)
Sorting
Out of core sorting
Heap sort
External sorting
Replacement selection
Merge sort
Run formation
Programació (Ordinadors)
info:eu-repo/semantics/publishedVersion
Artículo
Association for Computing Machinery (ACM)
         

Mostrar el registro completo del ítem

Documentos relacionados

Otros documentos del mismo autor/a

Domínguez Sal, David; Martínez Bazán, Norbert; Muntés Mulero, Víctor; Baleta Ferrer, Pedro; Larriba Pey, Josep
Prat Pérez, Arnau; Domínguez Sal, David; Larriba Pey, Josep
Domínguez Sal, David; Pérez Casany, Marta; Larriba Pey, Josep
Prat Pérez, Arnau; Domínguez Sal, David; Larriba Pey, Josep; Troncoso, Pedro
Martínez Bazán, Norbert; Muntés Mulero, Víctor; Gómez Villamor, Sergio; Domínguez Sal, David; Águila Lorente, Miguel Ángel; Larriba Pey, Josep