Name
Abstract | ||
|---|---|---|
We explore in this paper a novel sampling algorithm, referred to as algorithm PAS (standing for proportion approximation sampling), to generate a high-quality online sample with the desired sample rate. The sampling quality refers to the consistency between the population proportion and the sample proportion of each categorical value in the database. Note that the state-of-the-art sampling algorithm to preserve the sampling quality has to examine the population proportion of each categorical value in a pilot sample a priori and is thus not applicable to incremental mining applications. To remedy this, algorithm PAS adaptively determines the inclusion probability of each incoming tuple in such a way that the sampling quality can be sequential/preserved while also guaranteeing the sample rate close to the user specified one. Importantly, PAS not only guarantees the proportion consistency of each categorical value but also excellently preserves the proportion consistency of multivariate statistics, which will be significantly beneficial to various data mining applications. For better execution efficiency, we further devise an algorithm, called algorithm EQAS (standing for efficient quality-aware sampling), which integrates PAS and random sampling to provide the flexibility of striking a compromise between the sampling quality and the sampling efficiency. As validated in experimental results on real and synthetic data, algorithm PAS can stably provide high-quality samples with corresponding computational overhead, whereas algorithm EQAS can flexibly generate samples with the desired balance between sampling quality and sampling efficiency |
Year | DOI | Venue |
|---|---|---|
2007 | 10.1109/TKDE.2007.1005 | IEEE Trans. Knowl. Data Eng. |
Keywords | Field | DocType |
population proportion,proportion consistency,sampling quality,incremental data mining,algorithm pas,random processes,proportion approximation sampling,sequential sampling,quality-aware sampling,algorithm eqas,state-of-the-art sampling algorithm,random sampling,incremental mining application,inclusion probability,data mining,efficient quality-aware sampling,sampling methods,categorical value,sampling efficiency,population proportion consistency,incremental data mining.,multivariate statistics,degradation,synthetic data,databases,approximation algorithms,probability,statistics | Data mining,Overhead (computing),Simple random sample,Categorical variable,Computer science,Sampling (signal processing),Population proportion,Synthetic data,Sampling (statistics),Lot quality assurance sampling | Journal |
Volume | Issue | ISSN |
19 | 4 | 1041-4347 |
Citations | PageRank | References |
0 | 0.34 | 26 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Kun-Ta Chuang | 1 | 252 | 44.61 |
| Keng-Pei Lin | 2 | 117 | 11.61 |
| Ming Chen | 3 | 6507 | 1277.71 |