Weighted Random sampling based hierarchical amnesic synopses for data streams

Maintaining a synopsis structure dynamically from data stream is vital for a variety of streaming data applications, such as approximate query or data mining. In many cases, the significance of data item in streams decays with age: this item perhaps conveys critical information first, but, as time goes by, it gets less and less important until it eventually becomes useless. This characteristic is termed amnesic. Random Sampling is often used in construction of synopsis for streaming data. This paper proposed a Weighted Random Sampling based Hierarchical Amnesic Synopses which includes the amnesic characteristic of data stream in the generation of synopsis. The construction methods for weighted random sampling with and without replacement are discussed. We experimentally evaluate the proposed synopsis structure.