In recent years, the deep web has become ex- tremely popular. Like any other data source, data mining on the deep web can produce important insights or summaries of results. However, data mining on the deep web is cha...In recent years, the deep web has become ex- tremely popular. Like any other data source, data mining on the deep web can produce important insights or summaries of results. However, data mining on the deep web is chal- lenging because the databases cannot be accessed directly, and therefore, data mining must be performed by sampling the datasets. The samples, in turn, can only be obtained by querying deep web databases with specific inputs. In this pa- per, we target two related data mining problems, association mining and differential rule mining. These are proposed to ex- tract high-level summaries of the differences in data provided by different deep web data sources in the same domain. We develop stratified sampling methods to perform these min- ing tasks on a deep web source. Our contributions include a novel greedy stratification approach, which recursively pro- cesses the query space of a deep web data source, and con- siders both the estimation error and the sampling costs. We have also developed an optimized sample allocation method that integrates estimation error and sampling costs. Our ex- perimental results show that our algorithms effectively and consistently reduce sampling costs, compared with a strat- ified sampling method that only considers estimation error. In addition, compared with simple random sampling, our al- gorithm has higher sampling accuracy and lower sampling costs.展开更多
文摘In recent years, the deep web has become ex- tremely popular. Like any other data source, data mining on the deep web can produce important insights or summaries of results. However, data mining on the deep web is chal- lenging because the databases cannot be accessed directly, and therefore, data mining must be performed by sampling the datasets. The samples, in turn, can only be obtained by querying deep web databases with specific inputs. In this pa- per, we target two related data mining problems, association mining and differential rule mining. These are proposed to ex- tract high-level summaries of the differences in data provided by different deep web data sources in the same domain. We develop stratified sampling methods to perform these min- ing tasks on a deep web source. Our contributions include a novel greedy stratification approach, which recursively pro- cesses the query space of a deep web data source, and con- siders both the estimation error and the sampling costs. We have also developed an optimized sample allocation method that integrates estimation error and sampling costs. Our ex- perimental results show that our algorithms effectively and consistently reduce sampling costs, compared with a strat- ified sampling method that only considers estimation error. In addition, compared with simple random sampling, our al- gorithm has higher sampling accuracy and lower sampling costs.
