Algorithmic Challenges in Web Search Engines
Open accessAbstract
In this paper, we describe six algorithmic problems that arise in web search engines and that are not or only partially solved: (1) Uniformly sampling of web pages; (2) modeling the web graph; (3) finding duplicate hosts; (4) finding top gainers and losers in data streams; (5) finding large dense bipartite graphs; and (6) understanding how eigenvectors partition the web.
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Cites
Normalized cuts and image segmentation
Shi, J., & Malik, J. (2000) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/34.868688 · Cited by 15,842 · see citing works
Chung, F. (1996) · Regional conference series in mathematics · doi:10.1090/cbms/092 · Cited by 5,918 · see citing works
On the resemblance and containment of documents
Broder, A. (2002) · Compression and Complexity of Sequences (SEQUENCES) · doi:10.1109/sequen.1997.666900 · Cited by 1,734 · see citing works
Accessibility of information on the web
Lawrence, S., & Giles, C. L. (1999) · Nature · doi:10.1038/21987 · Cited by 1,371 · see citing works
The Web as a Graph: Measurements, Models, and Methods
Kleinberg, J. M., Kumar, R., Raghavan, P., Rajagopalan, S., & Tomkins, A. (1999) · Lecture notes in computer science · doi:10.1007/3-540-48686-0_1 · Cited by 1,027 · see citing works
Trawling the Web for emerging cyber-communities
Kumar, R., Raghavan, P., Rajagopalan, S., & Tomkins, A. (1999) · Computer Networks · doi:10.1016/s1389-1286(99)00040-7 · Cited by 999 · see citing works
A random graph model for massive graphs
Aiello, W. A., Chung, F., & Lü, L. (2000) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/335305.335326 · Cited by 935 · see citing works
Inferring Web communities from link topology
Gibson, D., Kleinberg, J. M., & Raghavan, P. (1998) · doi:10.1145/276627.276652 · Cited by 775 · see citing works
Stochastic models for the Web graph
Kumar, R., Raghavan, P., Rajagopalan, S., Sivakumar, D., Tomkins, A., & Upfal, E. (2002) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.2000.892065 · Cited by 682 · see citing works
Lower Bounds for the Partitioning of Graphs
Donath, W. E., & Hoffman, A. J. (1973) · IBM Journal of Research and Development · doi:10.1147/rd.175.0420 · Cited by 669 · see citing works
Copy detection mechanisms for digital documents
Brin, S., Davis, J., & García-Molina, H. (1995) · Proceedings of the 1995 ACM SIGMOD international conference on Management of data - SIGMOD '95 · doi:10.1145/223784.223855 · Cited by 479 · see citing works
Henzinger, M. R., Heydon, A., Mitzenmacher, M., & Najork, M. (2000) · Computer Networks · doi:10.1016/s1389-1286(00)00055-4 · Cited by 269 · see citing works
Self-citationAccessibility of information on the Web
Lawrence, S., & Giles, C. L. (2000) · intelligence · doi:10.1145/333175.333181 · Cited by 230 · see citing works
Who links to whom: mining linkage between Web sites
Bharat, K. A., Chang, B.-W., Henzinger, M. R., et al. (2002) · doi:10.1109/icdm.2001.989500 · Cited by 167 · see citing works
Self-citationUsing PageRank to Characterize Web Structure
Pandurangan, G., Raghavan, P., & Upfal, E. (2002) · Lecture Notes in Computer Science · doi:10.1007/3-540-45655-4_36 · Cited by 164 · see citing works
Finding replicated Web collections
Cho, J., Shivakumar, N., & García-Molina, H. (2000) · ACM SIGMOD Record · doi:10.1145/335191.335429 · Cited by 138 · see citing works
Approximating Aggregate Queries about Web Pages via Random Walks
Bar-Yossef, Z., Berg, A., Chien, S., Fakcharoenphol, J., & Weitz, D. (2000) · Cited by 125 · see citing works
Mirror, mirror on the Web: a study of host pairs with replicated content
Bharat, K. A., & Broder, A. (1999) · Computer Networks · doi:10.1016/s1389-1286(99)00021-3 · Cited by 114 · see citing works
Methods for Sampling Pages Uniformly from the World Wide Web
Rusmevichientong, P., Pennock, D. M., Lawrence, S., et al. (2001) · Cited by 87 · see citing works
Finding replicated Web collections
Cho, J., Shivakumar, N., & García-Molina, H. (2000) · Proceedings - ACM-SIGMOD International Conference on Management of Data · doi:10.1145/342009.335429 · Cited by 60 · see citing works
Flagged first, then by citations
Research works printed but not linked: 1
- [15]15. M. Charikar, K. Chen, and M. Farach-Colton. "Finding Freqeunt Items in Data Streams." In Proceedings of the 29th International Colloquium on Automata, Languages, and Programming, pp. 693-703. New York: Springer, 2002.
Cited by
Sorted by citations
Monte Carlo Methods in PageRank Computation: When One Iteration is Sufficient
Avrachenkov, K., Litvak, N., Nemirovsky, D., & Osipova, N. (2007) · SIAM Journal on Numerical Analysis · doi:10.1137/050643799 · Cited by 250 · see citing works
Mining query logs: turning search usage data into knowledge
Silvestri, F. (2009) · Foundations and Trends® in Information Retrieval · doi:10.1561/1500000013 · Cited by 194 · see citing works
Using PageRank to Characterize Web Structure
Pandurangan, G., Raghavan, P., & Upfal, E. (2002) · Lecture Notes in Computer Science · doi:10.1007/3-540-45655-4_36 · Cited by 164 · see citing works
- Authors
- Henzinger, M. R.
- Corresponding author
- Henzinger, Monika R.
- ORCID
- Henzinger, Monika R.
- Venue
- Internet Mathematics
- Publisher
- Internet Mathematics
- Published
- 2004-01
- Volume
- 1
- Issue
- 1
- Pages
- 115-123
- ISSN
- 1542-7951 (ISSN-L)
- 1944-9488
- OpenAlex
- W2011918288
- Cited by
- 81
- References
- 20
- Citations by year
- 2025: 1 · 2024: 1 · 2023: 6 · 2022: 1 · 2019: 2 · 2018: 3 · 2016: 2 · 2015: 2 · 2014: 1 · 2013: 2 · 2012: 4
- FWCI
- 36.03
- Type
- journal article
- Language
- en
- Open access
- bronze
- doi.org
- Locations
- Internet Mathematics (publishedVersion)
- Project Euclid (Cornell University) (submittedVersion)
- Topics
- Physical Sciences › Computer Science › Information Systems › Information Retrieval and Search Behavior
- Physical Sciences › Computer Science › Information Systems › Web Data Mining and Analysis
- Physical Sciences › Computer Science › Artificial Intelligence › Algorithms and Data Compression
- Keywords
- search engines, streaming algorithms
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
