A Random Walk Approach to Sampling Hidden Databases

Summary: Random-walk over the interface query space to obtain a uniform sample of a hidden backend database accessed via form-like web interfaces. Fixed vs random attribute ordering and a probabilistic rejection technique improve sample quality; extensive experiments show accuracy and efficiency. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 3949
Venue: SIGMOD
Year: 2007
Pagerank: 6.0613238e-05
Overall Rank: 5,868 | 59.75%
DOI: 10.1145/1247480.1247550

Incoming Non-self Citations Over Time

Authors

1. Arjun Dasgupta (University of Texas)
2. Gautam Das (University of Texas)
3. Heikki Mannila (Helsinki Institute for Information Technology; Helsinki University of Technology; University of Helsinki)

BibTeX Citation

@inproceedings{dasgupta_sigmod07,
        title = {{A Random Walk Approach to Sampling Hidden Databases}},
        author = {Dasgupta, Arjun and Das, Gautam and Mannila, Heikki},
        series = {{SIGMOD} '07},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/1247480.1247550},
        url = {https://dl.acm.org/doi/10.1145/1247480.1247550},
        year = {2007}
}

Incoming Citations (Sorted by Pagerank)

Showing 15 of 15 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
2,683	Mining Search Engine Query Logs via Suggestion Sampling	2008	VLDB	8.2608808e-05
5,687	Walk, Not Wait: Faster Sampling Over Online Social Networks	2015	VLDB	6.1211881e-05
7,320	Privacy Implications of Database Ranking	2015	VLDB	5.6454465e-05
7,903	Mining a Search Engine’s Corpus: Efficient Yet Unbiased Sampling and Aggregate Estimation	2011	SIGMOD	5.5182155e-05
8,378	Discovering the Skyline of Web Databases	2016	VLDB	5.4387677e-05
8,671	Unbiased Estimation of Size and Other Aggregates Over Hidden Web Databases	2010	SIGMOD	5.3876663e-05
8,705	Progressive Deep Web Crawling Through Keyword Queries For Data Enrichment	2019	SIGMOD	5.3807913e-05
9,650	Aggregate Estimation Over Dynamic Hidden Web Databases	2014	VLDB	5.2427667e-05
9,684	Attribute Domain Discovery for Hidden Web Databases	2011	SIGMOD	5.2352357e-05
12,083	Query Reranking As A Service	2016	VLDB	5.093636e-05
12,285	Rank Discovery From Web Databases	2013	VLDB	5.093636e-05
12,462	An Access Cost-Aware Approach for Object Retrieval over Multiple Sources	2010	VLDB	5.093636e-05
12,495	Privacy Preservation of Aggregates in Hidden Databases: Why and How?	2009	SIGMOD	5.093636e-05
13,582	Aggregate Estimations over Location Based Services	2015	VLDB	-
13,742	HDSampler: Revealing Data Behind Web Form Interfaces	2009	SIGMOD	-

Outgoing Citations (Sorted by Pagerank)

Showing 7 of 7 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
36	Accurate Estimation Of The Number Of Tuples Satisfying A Condition	1984	SIGMOD	0.00048351457
340	Crawling the Hidden Web	2001	VLDB	0.00020711119
363	Approximate Query Processing: Taming the TeraBytes! A Tutorial	2001	VLDB	0.0002005475
1,601	Automatic Discovery of Language Models for Text Databases	1999	SIGMOD	0.00010239819
1,806	Effective Use of Block-Level Sampling in Statistics Estimation	2004	SIGMOD	9.7112151e-05
3,803	A Bi-Level Bernoulli Scheme for Database Sampling	2004	SIGMOD	7.1114677e-05
4,524	Probe, Count, and Classify: Categorizing Hidden-Web Databases	2001	SIGMOD	6.6457031e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	12,495	Privacy Preservation of Aggregates in Hidden Databases: Why and How?	2009	SIGMOD
2	1,483	Distributed Search over the Hidden Web: Hierarchical Database Sampling and Selection	2002	VLDB
3	4,524	Probe, Count, and Classify: Categorizing Hidden-Web Databases	2001	SIGMOD
4	12,285	Rank Discovery From Web Databases	2013	VLDB
5	173	Simple Random Sampling from Relational Databases	1986	VLDB
6	13,742	HDSampler: Revealing Data Behind Web Form Interfaces	2009	SIGMOD
7	8,054	Approximating Aggregate Queries about Web Pages via Random Walks	2000	VLDB
8	8,671	Unbiased Estimation of Size and Other Aggregates Over Hidden Web Databases	2010	SIGMOD
9	9,683	Optimal Algorithms for Crawling a Hidden Database in the Web	2012	VLDB
10	12,384	Randomized Generalization for Aggregate Suppression Over Hidden Web Databases	2011	VLDB