Algorithms For Querying And Processing Over Data Streams

Data stream model has appeared in a growing number of information-processing applications in the last decade, such as internet, sensor networks, network traffic monitoring, network security, data mining, financial monitoring, manufacturing, chronometer and many more. Compared with traditional data models, data stream model owns several distinguishing characteristics, (l)the volume of a stream is unbounded, (2)the rate of stream is very rapid, (3)tuple's arriving order cannot be controlled by applications, (4)each tuple can only be seen once, except that it is reserved for a special purpose.Because of features listed above, devising algorithms for querying and processing over data streams encounters following great challenges. At first, on seeing each new element in the data stream, stream algorithms are required to process it rapidly to update answers in real time. Secondly, compared to the volume of data stream seen so far, the main memory or disk storage that is available for computation is typically very small. Thirdly, for most problems, stream algorithms can only provide approximate answers, but with guaranteed precision in general. Finally, a good stream algorithm can still be efficient even when streams outside change a lot.Traditional data processing techniques can hardly be applied to process data streams directly. Despite the success in traditional applications, Database Management System(DBMS) is infeasible to process such data because DBMS can run a query only when all data are preloaded. Another traditional method, which is based on randomly accessing memory where all data are loaded, is also inapplicable for the volume of stream seen so far is greater than the memory size. This made researchers work out novel querying and processing techniques over data streams.In this paper, we have studied a few principal problems over data streams, and made several contributions.1. Mining frequent items over data streams is a basic problem over streams. We firstly propose a novel method, called hCount, which can estimate the fre-...