| 本文已被：浏览 5661次 下载 6547次 |
码上扫一扫！ |
|
|
| 基于蛇型磁带的海量数据排序算法 |
|
李建中1,2, 张艳秋1
|
|
1.哈尔滨工业大学,计算机科学与技术学院,黑龙江,哈尔滨,150001;2.黑龙江大学,计算机科学技术学院,黑龙江,哈尔滨,150080
|
|
| 摘要: |
| 在数字图书馆和数据仓库中,需要解决海量数据的排序问题.利用蛇型磁带自身的物理特点,实现了一种高效的磁带排序算法STESort(serpentine tape external sort).与传统的2路归并磁带排序算法相比,STESort算法减少了磁带总定位时间.STESort算法具有更优的效率.STESort算法在提高排序效率的同时,通过减少磁头在磁带表面的移动次数延长了磁带的使用寿命.理论分析和实验结果表明,STESort算法优于传统的磁带排序算法,适合于海量数据排序. |
| 关键词: 蛇型磁带 海量信息 磁带排序算法 STESort(serpentine tape external sort) |
| DOI： |
| 分类号: |
| 基金项目:(Supported by the National Natural Science Foundation of China under Grant No.60273082 (国家自然科学基金); the National High-Tech Research and Development Plan of China under Grant No.2001AA41541 (国家高技术研究发展计划); the National Grand Fundamental Research 973 Program of China under Grant No.G1999032704 (国家重点基础研究发展规划(973)) |
|
| A Massive Data Sort Algorithm Based on Serpentine Tape |
|
LI Jian-Zhong,ZHANG Yan-Qiu
|
| Abstract: |
| In order to solve massive data sort in digital library and dataware house, a new highly efficient algorithm based on serpentine tape, named STESort (serpentine tape external sort), is provided in this paper. Taking full advantage of the characteristics of serpentine tape, the STESort algorithm reduces the whole seek time on tapes compared with traditional 2-way merge tape sort algorithm. Besides increasing the efficiency of tape sort, the STESort algorithm prolongs the duration of tapes by reducing the times of tape header moving on tape surface. The theoretical analysis and the experimental results show that the STESort algorithm is more efficient than the traditional tape sort algorithms. The STESort is suitable for massive data sort. |
| Key words: serpentine tape massive data tape sort algorithm STESort (serpentine tape external sort) |
