Probability Model Based Hidden Databases Sampling Approach

A great portion of data on the Web lies in the hidden databases of the deep Web. These databases can only be accessed through the query interfaces. Efficient and uniform data sampling approach is very important to other research work, for the data samples can give insight into the data quality, freshness and size information in the databases. However, the existing hidden database samplers are very inefficient, because lots of queries are wasted in the sampling walks. In this paper, we propose a probability model based sampling approach to solve this problem. First, we leverage the historical underflow walks to calculate the underflow probability of the attribute values. Based on the underflow probability, we give priority to execute the attribute values with largest underflow probability. The experimental results indicate that our approach can improve the sampling efficiency by detecting the underflow earlier and avoid many wasted queries.