An optimal external selection algorithm and its application in the Internet

Author

Leu, Fang-Cheng ; Chiou, Chuang-Chun ; Tsai, Yin-Te ; Tang, Chuan Yi

Author_Institution

Dept. of Comput. Sci., Nat. Tsing Hua Univ., Hsinchu, Taiwan

Volume

7

fYear

2001

fDate

2001

Firstpage

2150

Abstract

This paper presents an optimal sampling external selection (SES) algorithm to select k-th smallest item in large data sets for the two-level memory model. Based on the SES algorithm, two algorithms SES/DASK (dynamic assigned sorting key) and SES/FASK (fixed assigned sorting key) are also proposed which are applied to the worldwide selection problem in the Internet environment. We use the sampling information scheme to form an elegant and simple algorithm to reduce the number of disk I/Os. Especially, our algorithm is more efficient for the multiple selections

Keywords

Internet; digital storage; disc storage; optimisation; signal sampling; storage management; Internet; SES algorithm; SES/DASK; SES/FASK; data management; disk I/O; dynamic assigned sorting key; fixed assigned sorting key; large data sets; optimal external selection algorithm; sampling information; two-level memory model; Algorithm design and analysis; Application software; Central Processing Unit; Computer science; Information management; Internet; Sampling methods; Sorting;

fLanguage

English

Publisher

ieee

Conference_Titel

Communications, 2001. ICC 2001. IEEE International Conference on

Conference_Location

Helsinki

Print_ISBN

0-7803-7097-1

Type

conf

DOI

10.1109/ICC.2001.937037

Filename

937037