2007 · 90 citations · 15 references
ComputingComputer ScienceData ManagementData MiningDatabasesDatabase ManagementQuery ProcessingSampling TheoryData DistributionData Distribution AnalysisDatabase Query InterfacesQuery Interface DesignRandom Walk SimulationUniform Random Sampling
A large part of the data on the World Wide Web is hidden behind form-like interfaces. These interfaces interact with a hidden back-end database to provide answers to user queries. Generating a uniform random sample of this hidden database by using only the publicly available interface gives us access to the underlying data distribution. In this paper, we propose a random walk scheme over the query space provided by the interface to sample such databases. We discuss variants where the query space is visualized as a fixed and random ordering of attributes. We also propose techniques to further improve the sample quality by using a probabilistic rejection based approach. We conduct extensive experiments to illustrate the accuracy and efficiency of our techniques.
15
Equation of State Calculations by Fast Computing Machines
N. Metropolis, Arianna W. Rosenbluth, M. N. Rosenbluth et al. · The Journal of Chemical Physics · 1953 · 37.1K citations
Monte Carlo sampling methods using Markov chains and their applications
W. Keith Hastings · Biometrika · 1970 · 15.2K citations
Random sampling with a reservoir
Jeffrey Scott Vitter · ACM Transactions on Mathematical Software · 1985 · 1.8K citations · Full text
Accessibility of information on the web
Steve Lawrence, C. Lee Giles · Nature · 1999 · 1.4K citations
Steve Lawrence, C. Lee Giles · Science · 1998 · 974 citations