On sorting strings in external memory

@inproceedings{citeulike:1139900, abstract = {) Lars Arge Paolo Ferragina y Roberto Grossi z Jeffrey Scott Vitter x Abstract. In this paper we address for the first time the I/O complexity of the problem of sorting strings in external memory, which is a fundamental component of many large-scale text applications. In the standard unit-cost RAM comparison model, the complexity of sorting K strings of total length N is \Theta(K log 2 K+N). By analogy, in the external memory (or I/O) model, where the internal memory has size M and the block...}, address = {El Paso}, author = {Arge, Lars and Ferragina, Paolo and Grossi, Roberto and Vitter, Jeffrey S. }, booktitle = {Proceedings of the 29th Annual ACM Symposium on Theory of Computing}, citeulike-article-id = {1139900}, keywords = {algorithm}, pages = {540--548}, posted-at = {2007-03-04 15:33:26}, priority = {2}, publisher = {ACM Press}, title = {On sorting strings in external memory}, url = {http://citeseer.ist.psu.edu/arge97sorting.html}, year = {1997} }

TY - CONF ID - citeulike:1139900 L3 - citeulike-article-id:1139900 TI - On sorting strings in external memory T2 - Proceedings of the 29th Annual ACM Symposium on Theory of Computing SP - 540 EP - 548 AD - El Paso PB - ACM Press N2 - ) Lars Arge Paolo Ferragina y Roberto Grossi z Jeffrey Scott Vitter x Abstract. In this paper we address for the first time the I/O complexity of the problem of sorting strings in external memory, which is a fundamental component of many large-scale text applications. In the standard unit-cost RAM comparison model, the complexity of sorting K strings of total length N is \Theta(K log 2 K+N). By analogy, in the external memory (or I/O) model, where the internal memory has size M and the block... KW - algorithm AU - Arge, Lars AU - Ferragina, Paolo AU - Grossi, Roberto AU - Vitter, Jeffrey PY - 1997/// UR - http://citeseer.ist.psu.edu/arge97sorting.html ER -