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: h32bea10baf927d93
Venue: SIGMOD
Year: 2007
Pagerank: 5.926154e-05
Overall Rank: 5,985 | 59.77%
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,736	Mining Search Engine Query Logs via Suggestion Sampling	2008	VLDB	8.0758355e-05
5,808	Walk, Not Wait: Faster Sampling Over Online Social Networks	2015	VLDB	5.9876214e-05
7,469	Privacy Implications of Database Ranking	2015	VLDB	5.5187779e-05
8,065	Mining a Search Engine’s Corpus: Efficient Yet Unbiased Sampling and Aggregate Estimation	2011	SIGMOD	5.3952009e-05
8,547	Discovering the Skyline of Web Databases	2016	VLDB	5.3171862e-05
8,736	Progressive Deep Web Crawling Through Keyword Queries For Data Enrichment	2019	SIGMOD	5.2904354e-05
8,833	Unbiased Estimation of Size and Other Aggregates Over Hidden Web Databases	2010	SIGMOD	5.267646e-05
9,825	Aggregate Estimation Over Dynamic Hidden Web Databases	2014	VLDB	5.1251333e-05
9,857	Attribute Domain Discovery for Hidden Web Databases	2011	SIGMOD	5.1185704e-05
12,376	Query Reranking As A Service	2016	VLDB	4.9793485e-05
12,576	Rank Discovery From Web Databases	2013	VLDB	4.9793485e-05
12,753	An Access Cost-Aware Approach for Object Retrieval over Multiple Sources	2010	VLDB	4.9793485e-05
12,785	Privacy Preservation of Aggregates in Hidden Databases: Why and How?	2009	SIGMOD	4.9793485e-05
13,895	Aggregate Estimations over Location Based Services	2015	VLDB	-
14,053	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.00047863192
348	Crawling the Hidden Web	2001	VLDB	0.00020262145
372	Approximate Query Processing: Taming the TeraBytes! A Tutorial	2001	VLDB	0.00019720059
1,631	Automatic Discovery of Language Models for Text Databases	1999	SIGMOD	0.00010022634
1,826	Effective Use of Block-Level Sampling in Statistics Estimation	2004	SIGMOD	9.5575424e-05
3,871	A Bi-Level Bernoulli Scheme for Database Sampling	2004	SIGMOD	6.9543581e-05
4,610	Probe, Count, and Classify: Categorizing Hidden-Web Databases	2001	SIGMOD	6.5030302e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	12,785	Privacy Preservation of Aggregates in Hidden Databases: Why and How?	2009	SIGMOD
2	1,517	Distributed Search over the Hidden Web: Hierarchical Database Sampling and Selection	2002	VLDB
3	4,610	Probe, Count, and Classify: Categorizing Hidden-Web Databases	2001	SIGMOD
4	12,576	Rank Discovery From Web Databases	2013	VLDB
5	175	Simple Random Sampling from Relational Databases	1986	VLDB
6	14,053	HDSampler: Revealing Data Behind Web Form Interfaces	2009	SIGMOD
7	8,210	Approximating Aggregate Queries about Web Pages via Random Walks	2000	VLDB
8	8,833	Unbiased Estimation of Size and Other Aggregates Over Hidden Web Databases	2010	SIGMOD
9	9,856	Optimal Algorithms for Crawling a Hidden Database in the Web	2012	VLDB
10	12,675	Randomized Generalization for Aggregate Suppression Over Hidden Web Databases	2011	VLDB