微信服务号

微信订阅号

2025-4-25- 12
Home > Archive>Volume 14, Issue 1, 2003 >28-34
PDF HTML XML Export Cite reminder
A Massive Data Sort Algorithm Based on Serpentine Tape
Author:
Affiliation:

  • Article
    • | |
  • Metrics
    • |
  • Reference [11]
    • |
  • Related [20]
    • |
  • Cited by [5]
    • | |
  • Comments
    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.

    Reference
    [1]Knuth D. The Art of Computer Programming, Vol 3: Sorting and Searching. 2nd ed., Redwood, CA: Addison Wesley, 1973. 503～657.
    [2]Pang H, Carey MJ, Livny M. Memory-Adaptive external sorting. In: Agrawal R, Baker S, Bell DA, eds. Proceedings of the 19th International Conference on Very Large Data Bases. Dublin: Morgan Kaufmann, 1993. 618～629.
    [3]Aggarwal A, Plaxton CG. Optimal parallel sorting in multi-level storage. In: Sleator DD, ed. Proceedings of the 5th Annual ACM-SIAM Symposium on Discrete Algorithms. New York: ACM Press, 1994. 659～668.
    [4]Azar Y, Vishkin U. Tight comparison bounds on complexity of parallel sorting. SIAM Journal on Computing, 1987,16(3):458～464.
    [5]DeWitt DJ, Naughton JF, Schneider DA. Parallel sorting on a shared-nothing architecture using probabilistic splitting. In: Rishe N, ed. Proceedings of the 1st International Conference on Parallel and Distributed systems. IEEE Computer Society, 1991. 280～291.
    [6]Salzbergl B, Tsukerman A, Gray J, Stewart M, Uren S, Vaughan B. FastSort: a distributed single-input single-output external sort. In: Garcia-Molina H, ed. Proceedings of the International Conference on Management of Data. New York: ACM Press, 1990. 94～101.
    [7]Bitton D, DeWitt DJ, Hsiao DK, Menon J. A taxonomy of parallel sorting. ACM Computing Surveys, 1984,16(3):287～318.
    [8]Sandsta O. Improving the access time performance of serpentine. In: Acharya S, ed. Proceedings of the 15th International Conference on Data Engineering. Sydney: IEEE Computer Society, 1999. 542～551.
    [9]Yan WM, Wu WM. Data Structure. 2nd ed., Beijing: Tsinghua University Press, 1995. 298～299 (in Chinese).
    [10]Hillyer BK. On the modeling and performance characteristics of a serpentine tape. In: Gaither BD, ed. Proceedings of the ACM SIGMETRICS Conference on Measurement and Modeling of Computer Systems. New York: ACM Press, 1996. 170～179.
    [11]严蔚敏,吴伟民.数据结构.第2版,北京:清华大学出版社,1995.298～299.
    Comments
    Comments
    分享到微博
    Submit
Get Citation

李建中,张艳秋.基于蛇型磁带的海量数据排序算法.软件学报,2003,14(1):28-34

Copy
Share
Article Metrics
  • Abstract:5085
  • PDF: 5543
  • HTML: 0
  • Cited by: 0
History
  • Received:March 18,2002
  • Revised:August 14,2002
Links:Institute of Software, CASChina Computer FederationCASNSFC
You are the first2038665Visitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
Address：4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code：100190
Phone：010-62562563 Fax：010-62562533 Email：jos@iscas.ac.cn
Technical Support：Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063