Sorting hierarchical data in external memory for archiving
Sorting hierarchical data in external memory for archiving
复制标题
对外部存储器中的分层数据进行排序以进行归档
DOI：
--
复制
发表时间：
2008
影响因子：
2.5
通讯作者：
Stratis Viglas
中科院分区：
文献类型：
--
作者：
Ioannis Koltsidas;Heiko Müller;Stratis Viglas
对外部存储器中的分层数据进行排序对于各种应用都是必要的，包括归档科学数据和处理大型 XML 数据集。然而，迄今为止，对分层数据进行排序的主题还没有受到研究界的关注。在本文中，我们重点关注对远远超出物理内存大小的任意分层数据进行排序。我们提出了 HErMeS，这是一种概括了最广泛使用的外部存储器中平面数据排序技术的算法。 HErMeS 有效地利用分层结构来最大限度地减少磁盘访问次数并优化可用内存的使用。我们根据分层数据集的结构提取算法的理论界限。然后我们展示如何使用该算法来支持高效归档。我们使用多种工作负载进行了一项实验研究，并将 HErMeS 与最先进的方法进行了比较。我们的结果表明，我们的算法 (a) 满足其理论预期，(b) 允许可扩展的数据库归档，(c) 显着优于竞争对手。我们相信，这些结果证明我们的技术是解决外部存储器中分层数据排序问题的可行且可扩展的解决方案。
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.