Title:	ON EFFICIENTLY CREATING TEMPORALLY BIASED SAMPLES OVER DATA STREAMS: BEYOND MEMORYLESS FUNCTIONS
Author(s):	George Lagogiannis and Christos Makris
ISBN:	978-989-8704-21-4
Editors:	Yingcai Xiao, Ajith P. Abraham and Jörg Roth
Year:	2020
Edition:	Single
Keywords:	Temporally Biased Sample, Stream, Markov Chains
Type:	Full
First Page:	157
Last Page:	164
Language:	English
Cover:
Full Contents:	click to dowload
Paper Abstract:	When creating a sample over a data stream, we sometimes need to give a priority to the recent past, over the distant one. This can be achieved if the probability of each stream element to exist in the sample decays as time passes, according to a bias-function. In order to obtain such a sample, one has to access some elements of the sample when a stream element arrives. For the exponential bias-function, according to which the probability of a sample-element to be deleted at each time-point, is the same for all sample elements, the number of needed accesses is O(1). For any other bias-function, one needs to access O(n) elements per incoming stream element, where n is the sample-size. In this paper we present an algorithm that achieves O(1) amortized accesses for any bias-function such that at each time-point, the probability of a sample-element to be deleted increases over time.
	Go Back