Investigation and Development of Stream Processing Algorithms for Predominant Item Extraction from Big Data Systems
Open AccessData streaming systems have their foundations and applications in many domains, such as database systems, network monitoring, data mining, algorithms, sensor networks, theory and statistics. Therefore, there has been a substantial interest in the design of algorithms that process data streams using single-pass (or on-the-fly) algorithms to provide up to the moment analysis and statistics on current arrival streams. The frequent items problem is one of the most heavily studied questions in data streams. It's popular due to its simplicity to state, and its intuitive interest and value. The frequent items problem is to process a stream of items and find all those that occur more than a given fraction of the time (frequency). The volume of data stream is extremely large that can hardly be stored in main memory for on-line processing. The challenge of this problem is to find the most frequent item(s) in streams of large volume using very limited space. Many applications rely directly or indirectly on finding the frequent items, and implementations are in use in large-scale industrial systems. In this work, we investigate previous efforts for finding most frequent item(s), and introduce novel algorithms that have better performance. Firstly, we investigate the algorithm Majority that extracts single item with occurrence of more than 50% overall processed stream. Next, we introduce our novel Cyber-Physical Stream (CPS) algorithm that retrieves the most frequent item of frequency as low as 2% in time complexity of linear time, and show how CPS performs better compared to previous efforts, and that the efficiency of CPS increases by increasing the volume of the stream. Moreover, we propose a design of an analog device that holds CPS algorithm to extract items from large data streams. Secondly, we introduce and investigate a novel algorithm called Multi-Buffer Based algorithm that extracts the most frequent k items over a very large volume streams using very limited space in time complexity of linear time. Next, we compare our algorithm Multi-Buffer Based to previous effort, such as Frequent algorithm and SpaceSaving algorithm and show that Multi-Buffer Based performs better as indicated by out experiments.Finally, We propose an efficient Frequent Sequence Stream algorithm for identifying the top k most frequent subsequences over very large data streams. Our Frequent Sequence Stream algorithm gains its efficiency by its time complexity of linear time and very limited space complexity. With a pre-specification of subsequence window size S and k value, in very high probabilities, the Sequence Stream algorithm retrieve the top k most frequent subsequences of size S using sliding window technique.Moreover, we point out several major factors, which influence the result accuracy such as stream size, range of stream alphabet, frequency of predominant and quantity of our buffer sets.
- All rights reserved
Notice to Authors
If you are the author of this work and you have any questions about the information on this page, please use the Contact form to get in touch with us.
| Thumbnail | Title | Date Uploaded | Visibility | Actions |
|---|---|---|---|---|
|
|
Alhudhaif_gwu_0075A_12507.pdf | 2018-01-16 | Open Access |
|