Efficent sampling procedure for small storage devices - Agrawal, Rohit (2013)
Sampling is concerned with the selection of a subset of individuals from within a statistical population to estimate characteristics of the whole population. For large, multi-dimensional databases, algorithms for data analytics might require multiple iterations over the whole database which can be very expensive in terms of time. However, in many applications, approximate (rather than exact) answers to queries are often more than satisfactory. For such applications, by drilling down to a sample of members, one can quickly analyze a large multidimensional database with a focus on data trends or approximate information in the initial stage. In this project, a distance based sampling algorithm DSSC (Distance based Sampling for Streaming data with Continuous attributes) is proposed. DSSC can be used in applications which require a high quality sample but are limited in terms of memory and processing power, such as mobile devices. Preliminary results on data sets show that DSSC is robust to noise and requires little memory space. We prove that the cost of an incoming transaction is at most O(n.|T|).