In:
PLOS ONE, Public Library of Science (PLoS), Vol. 17, No. 4 ( 2022-4-5), p. e0266295-
Abstract:
Big streaming data environment concerns a complicated scenario where data to be processed continuously flow into a processing unit and certainly cause a memory overflow problem. This obstructs the adaptation of deploying all existing classic sorting algorithms because the data to be sorted must be entirely stored inside the fixed-size storage including the space in internal and external storage devices. Generally, it is always assumed that the size of each data chunk is not larger than the size of storage ( M ) but in fact the size of the entire stream ( n ) is usually much larger than M . In this paper, a new fast continuous streaming sorting is proposed to cope with the constraint of storage overflow. The algorithm was tested with various real data sets consisting of 10,000 to 17,000,000 numbers and different storage sizes ranging from 0.01 n to 0.50 n . It was found that the feasible lower bound of storage size is 0.35 n with 100% sorting accuracy. The sorting time outperforms bubble sort, quick sort, insertion sort, and merge sort when data size is greater than 1,000,000 numbers. Remarkably, the sorting time of the proposed algorithm is 1,452 times less than the sorting time of external merge sort and 28.1767 times less than the sorting time of streaming data sort. The time complexity of proposed algorithm is O ( n ) while the space complexity is O ( M ).
Type of Medium:
Online Resource
ISSN:
1932-6203
DOI:
10.1371/journal.pone.0266295
DOI:
10.1371/journal.pone.0266295.g001
DOI:
10.1371/journal.pone.0266295.g002
DOI:
10.1371/journal.pone.0266295.g003
DOI:
10.1371/journal.pone.0266295.g004
DOI:
10.1371/journal.pone.0266295.g005
DOI:
10.1371/journal.pone.0266295.g006
DOI:
10.1371/journal.pone.0266295.g007
DOI:
10.1371/journal.pone.0266295.t001
DOI:
10.1371/journal.pone.0266295.t002
DOI:
10.1371/journal.pone.0266295.t003
DOI:
10.1371/journal.pone.0266295.t004
DOI:
10.1371/journal.pone.0266295.t005
DOI:
10.1371/journal.pone.0266295.t006
DOI:
10.1371/journal.pone.0266295.t007
DOI:
10.1371/journal.pone.0266295.s001
DOI:
10.1371/journal.pone.0266295.r001
DOI:
10.1371/journal.pone.0266295.r002
DOI:
10.1371/journal.pone.0266295.r003
DOI:
10.1371/journal.pone.0266295.r004
Language:
English
Publisher:
Public Library of Science (PLoS)
Publication Date:
2022
detail.hit.zdb_id:
2267670-3
Permalink