Skip to main content

Permuting data on randomaccess block storage

Publication ,  Journal Article
Thonangi, R; Yang, J
Published in: Proceedings of the VLDB Endowment
January 1, 2013

Permutation is a fundamental operator for array data, with applications in, for example, changing matrix layouts and reorganizing data cubes. We consider the problem of permuting large quantities of data stored on secondary storage that supports fast random block accesses, such as solid state drives and distributed key-value stores. Faster random accesses open up interesting new opportunities for permutation. While external merge sort has often been used for permutation, it is an overkill that fails to exploit the property of permutation fully and carries unnecessary overhead in storing and comparing keys. We propose faster algorithms with lower memory requirements for a large, useful class of permutations. We also tackle practical challenges that traditional permutation algorithms have not dealt with, such as exploiting random block accesses more aggressively, considering the cost asymmetry between reads and writes, and handling arbitrary data dimension sizes (as opposed to perfect powers often assumed by previous work). As a result, our algorithms are faster and more broadly applicable.

Duke Scholars

Published In

Proceedings of the VLDB Endowment

DOI

EISSN

2150-8097

Publication Date

January 1, 2013

Volume

6

Issue

9

Start / End Page

721 / 732

Related Subject Headings

  • 4605 Data management and data science
  • 0807 Library and Information Studies
  • 0806 Information Systems
  • 0802 Computation Theory and Mathematics
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Thonangi, R., & Yang, J. (2013). Permuting data on randomaccess block storage. Proceedings of the VLDB Endowment, 6(9), 721–732. https://doi.org/10.14778/2536360.2536371
Thonangi, R., and J. Yang. “Permuting data on randomaccess block storage.” Proceedings of the VLDB Endowment 6, no. 9 (January 1, 2013): 721–32. https://doi.org/10.14778/2536360.2536371.
Thonangi R, Yang J. Permuting data on randomaccess block storage. Proceedings of the VLDB Endowment. 2013 Jan 1;6(9):721–32.
Thonangi, R., and J. Yang. “Permuting data on randomaccess block storage.” Proceedings of the VLDB Endowment, vol. 6, no. 9, Jan. 2013, pp. 721–32. Scopus, doi:10.14778/2536360.2536371.
Thonangi R, Yang J. Permuting data on randomaccess block storage. Proceedings of the VLDB Endowment. 2013 Jan 1;6(9):721–732.

Published In

Proceedings of the VLDB Endowment

DOI

EISSN

2150-8097

Publication Date

January 1, 2013

Volume

6

Issue

9

Start / End Page

721 / 732

Related Subject Headings

  • 4605 Data management and data science
  • 0807 Library and Information Studies
  • 0806 Information Systems
  • 0802 Computation Theory and Mathematics