{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,1,9]],"date-time":"2023-01-09T13:50:56Z","timestamp":1673272256806},"reference-count":11,"publisher":"Association for Computing Machinery (ACM)","issue":"1-2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2010,9]]},"abstract":"<jats:p>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.<\/jats:p>\n          <jats:p>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.<\/jats:p>","DOI":"10.14778\/1920841.1920952","type":"journal-article","created":{"date-parts":[[2014,6,24]],"date-time":"2014-06-24T12:17:57Z","timestamp":1403612277000},"page":"871-881","source":"Crossref","is-referenced-by-count":4,"title":["Two-way replacement selection"],"prefix":"10.14778","volume":"3","author":[{"given":"Xavier","family":"Martinez-Palau","sequence":"first","affiliation":[{"name":"Universitat Polit\u00e8cnica de Catalunya, Barcelona"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"David","family":"Dominguez-Sal","sequence":"additional","affiliation":[{"name":"Universitat Polit\u00e8cnica de Catalunya, Barcelona"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Josep Lluis","family":"Larriba-Pey","sequence":"additional","affiliation":[{"name":"Universitat Polit\u00e8cnica de Catalunya, Barcelona"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2010,9]]},"reference":[{"key":"e_1_2_1_1_1","first-page":"112","article-title":"A measure of transaction processing power","volume":"31","author":"Anon","year":"1985","journal-title":"Datamation"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/366552.366556"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132960.1132964"},{"key":"e_1_2_1_4_1","volume-title":"The Art of Computer Programming","author":"Knuth D.","year":"1998","edition":"2"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.14778\/1453856.1453983"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2003.1209012"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/276304.276346"},{"key":"e_1_2_1_9_1","unstructured":"Minute sort web page. http:\/\/sortbenchmark.org.  Minute sort web page. http:\/\/sortbenchmark.org."},{"key":"e_1_2_1_10_1","volume-title":"Design and Analysis of Experiments","author":"Mongomery D.","year":"2000","edition":"5"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-006-0005-2"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/69.494169"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/1920841.1920952","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T11:39:43Z","timestamp":1672227583000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/1920841.1920952"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,9]]},"references-count":11,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2010,9]]}},"alternative-id":["10.14778\/1920841.1920952"],"URL":"https:\/\/doi.org\/10.14778\/1920841.1920952","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2010,9]]}}}