A comparison of techniques for estimating IDF values to generate lexical signatures for the web

ABSTRACT

For bounded datasets such as the TREC Web Track the computation of term frequency (TF) and inverse document frequency (IDF) is not difficult. However, since IDF cannot be directly calculated for the entire web, it must be estimated. We see a need to estimate accurate IDF values to generate TF-IDF based lexical signatures (LSs) of web pages. Future applications for generating such LSs require a real time IDF computation. Therefore we conducted a comparison study of different methods to estimate IDF values of web pages. Our objective is to investigate how accurate these estimation methods are compared to the a baseline. We use the Google N-grams as our baseline and compare it against two IDF estimation techniques which are based on: 1) a "local universe" consisting of textual content and the according document frequencies from copies of URLs from the Internet Archive and 2) "screen scraping", a technique to query the Google web interface for document frequencies. We found a term overlap of 70 to 80% between the results of the two methods and the baseline. We further discovered a great agreement in rank correlation of TF-IDF ranked terms between our methods. Kendall τ is approximately 0.8 and the M-Score (penalizing discordances in higher ranks) is even higher, it peaks at well above 0.9. These preliminary results lead us to the conclusion that both methods are appropriate for creating accurate IDF values for web pages.

REFERENCES

• 1: L. A. Adamic and B. A. Huberman. Zipf's Law and the Internet. Glottometrics, 3:143--150, 2002.
• 2: Judit Bar-Ilan , Mazlita Mat-Hassan , Mark Levene, Methods for comparing rankings of search engine results, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.50 n.10, p.1448-1463, 14 July 2006 [doi>10.1016/j.comnet.2005.10.020]
• 3: Wei-Tsen Milly Chiang , Markus Hagenbuchner , Ah Chung Tsoi, The WT10G dataset and the evolution of the web, Special interest tracks and posters of the 14th international conference on World Wide Web, May 10-14, 2005, Chiba, Japan [doi>10.1145/1062745.1062807]
• 4: Ronald Fagin , Ravi Kumar , D. Sivakumar, Comparing top k lists, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
• 5: A. Franz and T. Brants. All Our N-Gram are Belong to You. http://googleresearch.blogspot.com/2006/08/all-our-n-gram-are-belong-to-you.html.
• 6: Terry L. Harrison , Michael L. Nelson, Just-in-time recovery of missing web pages, Proceedings of the seventeenth conference on Hypertext and hypermedia, August 22-25, 2006, Odense, Denmark [doi>10.1145/1149941.1149971]
• 7: D. Hawking. Overview of the TREC-9 Web Track. In NIST Special Publication 500-249: TREC-9, pages 87--102, 2001.
• 8: Panagiotis G. Ipeirotis , Luis Gravano, Distributed search over the hidden web: hierarchical database sampling and selection, Proceedings of the 28th international conference on Very Large Data Bases, p.394-405, August 20-23, 2002, Hong Kong, China
• 9: Frank Keller , Mirella Lapata, Using the web to obtain frequencies for unseen bigrams, Computational Linguistics, v.29 n.3, p.459-484, September 2003 [doi>10.1162/089120103322711604]
• 10: M. Klein and M. L. Nelson. Approximating Document Frequency with Term Count Values. Technical Report arXiv:0807.3755, Old Dominion University, 2008.
• 11: M. Klein and M. L. Nelson. Revisiting Lexical Signatures to (Re-)Discover Web Pages. In Proceedings of ECDL '08, 2008.
• 12: Aleksander Kołcz , Abdur Chowdhury , Joshua Alspector, Improved robustness of signature-based near-replica detection via lexicon randomization, Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, August 22-25, 2004, Seattle, WA, USA [doi>10.1145/1014052.1014127]
• 13: G. Leech, L. P. Grayson, and A. Wilson. Word Frequencies in Written and Spoken English: based on the British National Corpus. Longman, London, 2001.
• 14: Y. Ling, X. Meng, and W. Meng. Automated extraction of hit numbers from search result pages. In Proceedings of WAIM '06, pages 73--84, 2006.
• 15: Frank McCown , Michael L. Nelson, Agreeing to disagree: search engines and their public interfaces, Proceedings of the 7th ACM/IEEE-CS joint conference on Digital libraries, June 18-23, 2007, Vancouver, BC, Canada [doi>10.1145/1255175.1255237]
• 16: Frank McCown , Joan A. Smith , Michael L. Nelson, Lazy preservation: reconstructing websites by crawling the crawlers, Proceedings of the 8th annual ACM international workshop on Web information and data management, November 10-10, 2006, Arlington, Virginia, USA [doi>10.1145/1183550.1183564]
• 17: P. Nakov and M. Hearst. A Study of Using Search Engine Page Hits as a Proxy for n-gram Frequencies. In Proceedings of RANLP '05, 2005.
• 18: Seung-Taek Park , David M. Pennock , C. Lee Giles , Robert Krovetz, Analysis of lexical signatures for improving information persistence on the World Wide Web, ACM Transactions on Information Systems (TOIS), v.22 n.4, p.540-572, October 2004 [doi>10.1145/1028099.1028101]
• 19: T. A. Phelps and R. Wilensky. Robust Hyperlinks Cost Just Five Words Each. Technical report, University of California at Berkeley, 2000.
• 20: Jessica Staddon , Philippe Golle , Bryce Zimny, Web-based inference detection, Proceedings of 16th USENIX Security Symposium on USENIX Security Symposium, p.1-16, August 06-10, 2007, Boston, MA
• 21: Kazunari Sugiyama , Kenji Hatano , Masatoshi Yoshikawa , Shunsuke Uemura, Refinement of TF-IDF schemes for web pages using their hyperlinked neighboring pages, Proceedings of the fourteenth ACM conference on Hypertext and hypermedia, August 26-30, 2003, Nottingham, UK [doi>10.1145/900051.900096]
• 22: M. Theall. Methodologies for Crawler Based Web Surveys. Internet Research: Electronic Networking and Applications, 12:124--138, 2002.
• 23: X. Wan and J. Yang. Wordrank-based Lexical Signatures for Finding Lost or Related Web Pages. In APWeb, pages 843--849, 2006.
• 24: X. Zhu and R. Rosenfeld. Improving Trigram Language Modeling with the World Wide Web. In Proceedings of ICASSP '01, pages 533--536, 2001.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.0 General

General Terms:
Design, Measurement, Performance

Keywords:
inverse document frequency, lexical signature