Approximating Aggregate Queries about Web Pages via Random Walks
Summary: Random-walk based approach to approximate web-page aggregates; a novel walk on a dynamically built regular undirected graph yields near-uniform samples. Estimates search-engine coverage, domain composition, and average page size with strong empirical accuracy under limited resources. (summarized by gpt-5-nano on Feb 09 2026)
Incoming Non-self Citations Over Time
Authors
- 1. Ziv Bar-Yossef (University of California Berkeley)
- 2. Alexander Berg (University of California Berkeley)
- 3. Steve Chien (University of California Berkeley)
- 4. Jittat Fakcharoenphol (University of California Berkeley)
- 5. Dror Weitz (University of California Berkeley)
BibTeX Citation
@article{baryossef_vldb00,
title = {{Approximating Aggregate Queries about Web Pages via Random Walks}},
author = {Bar-Yossef, Ziv and Berg, Alexander and Chien, Steve and Fakcharoenphol, Jittat and Weitz, Dror},
journal = {PVLDB},
series = {{VLDB} '00},
pages = {535},
year = {2000}
}Incoming Citations (Sorted by Pagerank)
Showing 1 of 1 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 7,201 | An I/O-Efficient Disk-based Graph System for Scalable Second-Order Random Walk of Large Graphs | 2022 | VLDB | 5.6755554e-05 |
Previous
Page 1 / 1
Next
Outgoing Citations (Sorted by Pagerank)
Showing 0 of 0 cited papers.
Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.
| Rank | Cited Paper | Year | Venue | Pagerank |
|---|
Previous
Page 1 / 1
Next
Semantically Similar Papers
| # | Overall Rank | Paper | Year | Venue |
|---|---|---|---|---|
| 1 | 6,284 | Efficient Personalized PageRank Computation: A Spanning Forests Sampling Based Approach | 2022 | SIGMOD |
| 2 | 3,951 | READS: A Random Walk Approach for Efficient and Accurate Dynamic SimRank | 2017 | VLDB |
| 3 | 4,015 | The Web as a graph | 2000 | PODS |
| 4 | 7,903 | Mining a Search Engine’s Corpus: Efficient Yet Unbiased Sampling and Aggregate Estimation | 2011 | SIGMOD |
| 5 | 8,671 | Unbiased Estimation of Size and Other Aggregates Over Hidden Web Databases | 2010 | SIGMOD |
| 6 | 5,687 | Walk, Not Wait: Faster Sampling Over Online Social Networks | 2015 | VLDB |
| 7 | 1,396 | Estimating PageRank on Graph Streams | 2008 | PODS |
| 8 | 4,572 | On the Embeddability of Random Walk Distances | 2013 | VLDB |
| 9 | 1,958 | A General Framework for Estimating Graphlet Statistics via Random Walk | 2017 | VLDB |
| 10 | 5,868 | A Random Walk Approach to Sampling Hidden Databases | 2007 | SIGMOD |