Feature-preserved sampling over streaming data
Kun-Ta Chuang, Hung-Leng Chen, Ming-Syan Chen⋆ · ACM Transactions on Knowledge Discovery from Data · 2009
In this article, we explore a novel sampling model, calledfeature preserved sampling(FPS) that sequentially generates a high-quality sample over sliding windows. The sampling quality we consider refers to the degree of consistency between the sample proportion and the population proportion of each attribute value in a window. Due to the time-variant nature of real-world datasets, users are more likely to be interested in the most recent data. However, previous works have not been able to generate a high-quality sample over sliding windows that precisely preserves up-to-date population characteristics. Motivated by this shortcoming, we have developed theFPSalgorithm, which has several advantages: (1) it sequentially generates a sample from a time-variant data source over sliding windows; (2) the execution time ofFPSis linear with respect to the database size; (3) therelativeproportional differences between the sample proportions and population proportions of most distinct attribute values are guaranteed to be below a specified error threshold, ε, while therelativeproportion differences of the remaining attribute values are as close to ε as possible, which ensures that the generated sample is of high quality; (4) the sample rate is close to the user specified rate so that a high quality sampling result can be obtained without increasing the sample size; (5) by a thorough analytical and empirical study, we prove thatFPShas acceptable space overheads, especially when the attribute values have Zipfian distributions, andFPScan also excellently preserve the population proportion of multivariate features in the sample; and (6)FPScan be applied to infinite streams and finite datasets equally, and the generated samples can be used for various applications. Our experiments on both real and synthetic data validate thatFPScan effectively obtain a high quality sample of the desired size. In addition, while using the sample generated byFPSin various mining applications, a significant improvement in efficiency can be achieved without compromising the model's precision.