Sorting hierarchical data in external memory for archiving

Ioannis Koltsidas, Heiko Müller, Stratis D. Viglas

Research output: Contribution to journalArticlepeer-review


Sorting hierarchical data in external memory is necessary for a wide variety of applications including archiving scientific data and dealing with large XML datasets. The topic of sorting hierarchical data, however, has received little attention from the research community so far. In this paper we focus on sorting arbitrary hierarchical data that far exceed the size of physical memory. We propose HErMeS, an algorithm that generalizes the most widely-used techniques for sorting flat data in external memory. HErMeS efficiently exploits the hierarchical structure to minimize the number of disk accesses and optimize the use of available memory. We extract the theoretical bounds of the algorithm with respect to the structure of the hierarchical dataset. We then show how the algorithm can be used to support efficient archiving. We have conducted an experimental study using several workloads and comparing HErMeS to the state-of-the-art approaches. Our results show that our algorithm (a) meets its theoretical expectations, (b) allows for scalable database archiving, and (c) outperforms the competition by a significant factor. These results, we believe, prove our technique to be a viable and scalable solution to the problem of sorting hierarchical data in external memory.
Original languageEnglish
Pages (from-to)1205-1216
Number of pages12
JournalProceedings of the VLDB Endowment (PVLDB)
Issue number1
Publication statusPublished - 1 Aug 2008


Dive into the research topics of 'Sorting hierarchical data in external memory for archiving'. Together they form a unique fingerprint.

Cite this