Analysis of lexical signatures for improving information persistence on the World Wide Web

ABSTRACT

A <i>lexical signature</i> (LS) consisting of several key words from a Web document is often sufficient information for finding the document later, even if its URL has changed. We conduct a large-scale empirical study of nine methods for generating lexical signatures, including Phelps and Wilensky's original proposal (PW), seven of our own static variations, and one new dynamic method. We examine their performance on the Web over a 10-month period, and on a TREC data set, evaluating their ability to both (1) uniquely identify the original (possibly modified) document, and (2) locate other relevant documents if the original is lost. Lexical signatures chosen to minimize document frequency (DF) are good at unique identification but poor at finding relevant documents. PW works well on the relatively small TREC data set, but acts almost identically to DF on the Web, which contains billions of documents. Term-frequency-based lexical signatures (TF) are very easy to compute and often perform well, but are highly dependent on the ranking system of the search engine used. The term-frequency inverse-document-frequency- (TFIDF-) based method and hybrid methods (which combine DF with TF or TFIDF) seem to be the most promising candidates among static methods for generating effective lexical signatures. We propose a dynamic LS generator called <i>Test & Select</i> (TS) to mitigate LS conflict. TS outperforms all eight static methods in terms of both extracting the desired document and finding relevant information, over three different search engines. All LS methods show significant performance degradation as documents in the corpus are edited.

REFERENCES

• 1: Alberto Aimar , James Casey , Nikos Drakos , Ian Hannell , Arash Khodabandeh , Paolo Palazzi , Bertrand Rousseau , Mario Ruggier, WebLinker, a tool for managing WWW cross-references, Computer Networks and ISDN Systems, v.28 n.1-2, p.99-107, Dec. 1995 [doi>10.1016/0169-7552(95)00089-4]
• 2: Andrews, K., Kappe, F., and Maurer, H. 1995. The Hyper-G network information system. J. Univers. Comput. Sci. 1, 4 (April), 206--220.
• 3: Arms, W., Blanchi, C., and Overly, E. 1997. An architecture for information in digital libraries. D-Lib Mag. Available at http://www.dlib.org/dlib/february97/cnri/02arms1.html.
• 4: Berners-Lee, T., Fielding, R., and Frystyk, H. 1996. Hypertext transfer protocol---http/1.0. Available at http://www.w3.org/Protocols/HTTP/1.0/draft-ietf-http-spec.html.
• 5: Krishna Bharat , Andrei Broder, A technique for measuring the relative size and overlap of public Web search engines, Proceedings of the seventh international conference on World Wide Web 7, p.379-388, April 1998, Brisbane, Australia
• 6: Brian E. Brewington , George Cybenko, How dynamic is the Web?, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.33 n.1-6, p.257-276, June 2000
• 7: Junghoo Cho , Hector Garcia-Molina, The Evolution of the Web and Implications for an Incremental Crawler, Proceedings of the 26th International Conference on Very Large Data Bases, p.200-209, September 10-14, 2000
• 8: Michael L. Creech, Author-oriented link management, Proceedings of the fifth international World Wide Web conference on Computer networks and ISDN systems, p.1015-1025, May 1996, Paris, France
• 9: Douglis, F., Feldmann, A., Krishnamurthy, B., and Mogul, J. C. 1997. Rate of change and other metrics: A live study of the world wide web. In Proceedings of the USENIX Symposium on Internet Technologies and Systems. 147--158.
• 10: Fielding, R., Gettys, J., Mogul, J., Frystyk, H., Masinter, L., Leach, P., and Berners-Lee, T. 1999. Rfc 2616---hypertext transfer protocol---http/1.1. Available at http://www.w3.org/Protocols/ rfc2616/rfc2616.html.
• 11: Roy T. Fielding, Maintaining distributed hypertext infostructures: welcome to MOMspider's Web, Computer Networks and ISDN Systems, v.27 n.2, p.193-204, Nov. 1994
• 12: Fisher, R. A. 1966. Design of Experiments, 8th ed. Hafner (Macmillan), New York, NY.
• 13: C. Lee Giles , Kurt D. Bollacker , Steve Lawrence, CiteSeer: an automatic citation indexing system, Proceedings of the third ACM conference on Digital libraries, p.89-98, June 23-26, 1998, Pittsburgh, Pennsylvania, United States [doi>10.1145/276675.276685]
• 14: A. V. Goldberg , P. N. Yianilos, Towards an Archival Intermemory, Proceedings of the Advances in Digital Libraries Conference, p.147, April 22-24, 1998
• 15: Gulesian, M. 1996. Netscape livewire pro 1.0. Available at http://www.dbmsmag.com/9612d08. html.
• 16: Monika R. Henzinger , Allan Heydon , Michael Mitzenmacher , Marc Najork, Measuring index quality using random walks on the Web, Proceeding of the eighth international conference on World Wide Web, p.1291-1303, May 1999, Toronto, Canada
• 17: Monika R. Henzinger , Allan Heydon , Michael Mitzenmacher , Marc Najork, On near-uniform URL sampling, Proceedings of the 9th international World Wide Web conference on Computer networks : the international journal of computer and telecommunications netowrking, p.295-308, June 2000, Amsterdam, The Netherlands
• 18: David Ingham , Steve Caughey , Mark Little, Fixing the “broken-link” problem: the W3Objects approach, Proceedings of the fifth international World Wide Web conference on Computer networks and ISDN systems, p.1255-1268, May 1996, Paris, France
• 19: Ingham, D., Little, M., Caughey, S., and Shrivastava, S. 1995. W3Objects: Bringing object-oriented technology to the Web. In Proceedings of the 4th International World Wide Web Conference. 89--105.
• 20: Kalervo Järvelin , Jaana Kekäläinen, IR evaluation methods for retrieving highly relevant documents, Proceedings of the 23rd annual international ACM SIGIR conference on Research and development in information retrieval, p.41-48, July 24-28, 2000, Athens, Greece [doi>10.1145/345508.345545]
• 21: Steve Lawrence , C. Lee Giles, Context and Page Analysis for Improved Web Search, IEEE Internet Computing, v.2 n.4, p.38-46, July 1998 [doi>10.1109/4236.707689]
• 22: Lawrence, S. and Giles, C. L. 1998b. Searching the World Wide Web. Science 280, 5360 (April), 98--100.
• 23: Lawrence, S. and Giles, C. L. 1999. Accessibility of information on the Web. Nature 400, 107--109.
• 24: Steve Lawrence , C. Lee Giles , Kurt Bollacker, Digital Libraries and Autonomous Citation Indexing, Computer, v.32 n.6, p.67-71, June 1999 [doi>10.1109/2.769447]
• 25: Steve Lawrence , David M. Pennock , Gary William Flake , Robert Krovetz , Frans M. Coetzee , Eric Glover , Finn Årup Nielsen , Andries Kruger , C. Lee Giles, Persistence of Web References in Scientific Research, Computer, v.34 n.2, p.26-31, February 2001
• 26: Scott Mace , Udo Flohr , Rick Dobson , Tony Graham, Weaving a better Web, BYTE, v.23 n.3, p.58-68, Mar. 1998
• 27: Noreen, E. W. 1989. Computer-Intensive Methods for Testing Hypotheses: An Introduction. Wiley, New York, NY.
• 28: Oberholzer, G. and Wilde, E. 2002. Extended link visualization with DHTML: The Web as an open hypermedia system. Tech. rep. TIK-125. Computer Engineering and Networks Laboratory (TIK), ETH Zurich, Zurich, Switzerland.
• 29: Seung-Taek Park , David M. Pennock , C. Lee Giles , Robert Krovetz, Analysis of lexical signatures for finding lost or related documents, Proceedings of the 25th annual international ACM SIGIR conference on Research and development in information retrieval, August 11-15, 2002, Tampere, Finland [doi>10.1145/564376.564381]
• 30: Phelps, T. A. and Wilensky, R. 2000a. Robust hyperlinks: Cheap, everywhere, now. In Proceedings of Digital Documents and Electronic Publishing 2000 (DDEP00).
• 31: Thomas A. Phelps , Robert Wilensky, Robust Hyperlinks Cost Just Five Words Each, University of California at Berkeley, Berkeley, CA, 2000
• 32: Pitkow, J. 1998a. Web characterization activity: Answers to the W3C HTTP-NGs protocol design group's questions. World Wide Web Consortium (WWW.W3.org).
• 33: James E. Pitkow, Summary of WWW characterizations, Computer Networks and ISDN Systems, v.30 n.1-7, p.551-558, April 1, 1998
• 34: Reich, V. and Rosenthal, D. S. H. 2001. Lockss: A permanent Web publishing and access system. D-Lib Mag. 7, 6 (June), 55--68.
• 35: Rusmevichientong, P., Pennock, D. M., Lawrence, S., and Giles, C. L. 2001. Methods for sampling pages uniformly from the World Wide Web. In Proceedings of the AAAI Fall Symposium on Using Uncertainty Within Computation. 121--128.
• 36: Shafer, K., Weibel, S., Jul, E., and Fausey, J. 1996. Introduction to persistent uniform resource locators. In INET 96. Internet Society, Reston, Va.
• 37: Sollins, K. and Masinter, L. 1994. Functional Requirements for Uniform Resource Names, Network Working Group, RFC 1737. Available at http://www.faqs.org/rfcs/rfc1737.html.
• 38: Ellen M. Voorhees, Evaluation by highly relevant documents, Proceedings of the 24th annual international ACM SIGIR conference on Research and development in information retrieval, p.74-82, September 2001, New Orleans, Louisiana, United States [doi>10.1145/383952.383963]
• 39: Witten, I. H., Moffat, A., and Bell, T. C. 1999. Managing Gigabytes, 2nd ed. Harcourt Science and Technology Company, San Diego, CA.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval

General Terms:
Algorithms, Experimentation, Measurement, Performance, Reliability, Verification

Keywords:
Broken URLs, TREC, World Wide Web, dead links, digital libraries, indexing, information retrieval, inverse document frequency, lexical signatures, robust hyperlinks, search engines, term frequency