{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T12:07:36Z","timestamp":1763467656231,"version":"3.41.0"},"reference-count":39,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2004,10,1]],"date-time":"2004-10-01T00:00:00Z","timestamp":1096588800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Inf. Syst."],"published-print":{"date-parts":[[2004,10]]},"abstract":"<jats:p>A &lt;i&gt;lexical signature&lt;\/i&gt; (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 &lt;i&gt;Test &amp; Select&lt;\/i&gt; (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.<\/jats:p>","DOI":"10.1145\/1028099.1028101","type":"journal-article","created":{"date-parts":[[2005,1,26]],"date-time":"2005-01-26T16:35:53Z","timestamp":1106757353000},"page":"540-572","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":25,"title":["Analysis of lexical signatures for improving information persistence on the World Wide Web"],"prefix":"10.1145","volume":"22","author":[{"given":"Seung-Taek","family":"Park","sequence":"first","affiliation":[{"name":"Yahoo! Research Labs, Pasadena, CA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"David M.","family":"Pennock","sequence":"additional","affiliation":[{"name":"Yahoo! Research Labs, Pasadena, CA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"C. Lee","family":"Giles","sequence":"additional","affiliation":[{"name":"The Pennsylvania State University, University Park, PA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Robert","family":"Krovetz","sequence":"additional","affiliation":[{"name":"Ask Jeeves, Piscataway, NJ"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2004,10]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/0169-7552(95)00089-4"},{"key":"e_1_2_1_2_1","first-page":"4","article-title":"The Hyper-G network information system","volume":"1","author":"Andrews K.","year":"1995","unstructured":"Andrews , K. , Kappe , F. , and Maurer , H. 1995 . The Hyper-G network information system . J. Univers. Comput. Sci. 1 , 4 (April), 206--220.]] Andrews, K., Kappe, F., and Maurer, H. 1995. The Hyper-G network information system. J. Univers. Comput. Sci. 1, 4 (April), 206--220.]]","journal-title":"J. Univers. Comput. Sci."},{"key":"e_1_2_1_3_1","unstructured":"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.]]  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.]]"},{"key":"e_1_2_1_4_1","doi-asserted-by":"crossref","unstructured":"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.]]   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.]]","DOI":"10.17487\/rfc1945"},{"volume-title":"Proceedings of the 7th International World Wide Web Conference {WWW7}. 379--388","author":"Bharat K.","key":"e_1_2_1_5_1","unstructured":"Bharat , K. and Broder , A. Z . 1998. A technique for measuring the relative size and overlap of public Web search engines . In Proceedings of the 7th International World Wide Web Conference {WWW7}. 379--388 .]] Bharat, K. and Broder, A. Z. 1998. A technique for measuring the relative size and overlap of public Web search engines. In Proceedings of the 7th International World Wide Web Conference {WWW7}. 379--388.]]"},{"key":"e_1_2_1_6_1","doi-asserted-by":"crossref","unstructured":"Brewington B. E. and Cybenko G. 2000. How dynamic is the Web? Comput. Netw. (Amsterdam The Netherlands: 1999) 33 1--6 257--276.]] 10.1016\/S1389-1286(00)00045-1   Brewington B. E. and Cybenko G. 2000. How dynamic is the Web? Comput. Netw. (Amsterdam The Netherlands: 1999) 33 1--6 257--276.]] 10.1016\/S1389-1286(00)00045-1","DOI":"10.1016\/S1389-1286(00)00045-1"},{"volume-title":"Proceedings of the 26th International Conference on Very Large Databases. 117--128","author":"Cho J.","key":"e_1_2_1_7_1","unstructured":"Cho , J. and Garcia-Molina , H . 2000. The evolution of the Web and implications for an incremental crawler . In Proceedings of the 26th International Conference on Very Large Databases. 117--128 .]] Cho, J. and Garcia-Molina, H. 2000. The evolution of the Web and implications for an incremental crawler. In Proceedings of the 26th International Conference on Very Large Databases. 117--128.]]"},{"key":"e_1_2_1_8_1","volume-title":"Proceedings of the 5th International World Wide Web Conference.]]","author":"Creech M. L.","year":"1996","unstructured":"Creech , M. L. 1996 . Author-oriented link management . In Proceedings of the 5th International World Wide Web Conference.]] Creech, M. L. 1996. Author-oriented link management. In Proceedings of the 5th International World Wide Web Conference.]]"},{"volume-title":"Proceedings of the USENIX Symposium on Internet Technologies and Systems. 147--158","author":"Douglis F.","key":"e_1_2_1_9_1","unstructured":"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 .]] 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.]]"},{"key":"e_1_2_1_10_1","doi-asserted-by":"crossref","unstructured":"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.]]   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.]]","DOI":"10.17487\/rfc2616"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/0169-7552(94)90133-3"},{"key":"e_1_2_1_12_1","volume-title":"Design of Experiments","author":"Fisher R. A.","unstructured":"Fisher , R. A. 1966. Design of Experiments , 8 th ed. Hafner (Macmillan) , New York, NY .]] Fisher, R. A. 1966. Design of Experiments, 8th ed. Hafner (Macmillan), New York, NY.]]","edition":"8"},{"key":"e_1_2_1_13_1","doi-asserted-by":"crossref","unstructured":"Giles C. L. Bollacker K. and Lawrence S. 1998. CiteSeer: An automatic citation indexing system. In Digital Libraries 98---The Third ACM Conference on Digital Libraries (Pittsburgh PA) I. Witten R. Akscyn and F. M. Shipman III Eds. ACM Press New York NY 89--98.]] 10.1145\/276675.276685   Giles C. L. Bollacker K. and Lawrence S. 1998. CiteSeer: An automatic citation indexing system. In Digital Libraries 98---The Third ACM Conference on Digital Libraries (Pittsburgh PA) I. Witten R. Akscyn and F. M. Shipman III Eds. ACM Press New York NY 89--98.]] 10.1145\/276675.276685","DOI":"10.1145\/276675.276685"},{"volume-title":"IEEE Advances in Digital Libraries. (ADL '98","author":"Goldberg A.","key":"e_1_2_1_14_1","unstructured":"Goldberg , A. and Yianilos , P. N . 1998. Towards an archival intermemory . In IEEE Advances in Digital Libraries. (ADL '98 , Santa Barbara, (CA). IEEE Computer Society Press, Los Alamitos, CA, 147--156.]] Goldberg, A. and Yianilos, P. N. 1998. Towards an archival intermemory. In IEEE Advances in Digital Libraries. (ADL '98, Santa Barbara, (CA). IEEE Computer Society Press, Los Alamitos, CA, 147--156.]]"},{"key":"e_1_2_1_15_1","unstructured":"Gulesian M. 1996. Netscape livewire pro 1.0. Available at http:\/\/www.dbmsmag.com\/9612d08. html.]]  Gulesian M. 1996. Netscape livewire pro 1.0. Available at http:\/\/www.dbmsmag.com\/9612d08. html.]]"},{"volume-title":"Proceedings of the 8th International World Wide Web Conference. 213--225","author":"Henzinger M. R.","key":"e_1_2_1_16_1","unstructured":"Henzinger , M. R. , Heydon , A. , Mitzenmacher , M. , and Najork , M . 1999. Measuring index quality using random walks on the Web . In Proceedings of the 8th International World Wide Web Conference. 213--225 .]] Henzinger, M. R., Heydon, A., Mitzenmacher, M., and Najork, M. 1999. Measuring index quality using random walks on the Web. In Proceedings of the 8th International World Wide Web Conference. 213--225.]]"},{"volume-title":"Proceedings of the 9th International World Wide Web Conference. 295--308","author":"Henzinger M. R.","key":"e_1_2_1_17_1","unstructured":"Henzinger , M. R. , Heydon , A. , Mitzenmacher , M. , and Najork , M . 2000. On near-uniform URL sampling . In Proceedings of the 9th International World Wide Web Conference. 295--308 .]] Henzinger, M. R., Heydon, A., Mitzenmacher, M., and Najork, M. 2000. On near-uniform URL sampling. In Proceedings of the 9th International World Wide Web Conference. 295--308.]]"},{"volume-title":"Proceedings of the 5th International World Wide Web Conference.]]","author":"Ingham D.","key":"e_1_2_1_18_1","unstructured":"Ingham , D. , Caughey , S. , and Little , M . 1996. Fixing the 'broken-link' problem: The W3Objects approach . In Proceedings of the 5th International World Wide Web Conference.]] Ingham, D., Caughey, S., and Little, M. 1996. Fixing the 'broken-link' problem: The W3Objects approach. In Proceedings of the 5th International World Wide Web Conference.]]"},{"volume-title":"Proceedings of the 4th International World Wide Web Conference. 89--105","author":"Ingham D.","key":"e_1_2_1_19_1","unstructured":"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 .]] 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.]]"},{"key":"e_1_2_1_20_1","volume-title":"Proceedings of SIGIR","author":"Jarvelin K.","year":"2000","unstructured":"Jarvelin , K. and Kekalainen , J . 2000. IR evaluation methods for retrieving highly relevant documents . In Proceedings of SIGIR 2000 . 41--48.]] 10.1145\/345508.345545 Jarvelin, K. and Kekalainen, J. 2000. IR evaluation methods for retrieving highly relevant documents. In Proceedings of SIGIR 2000. 41--48.]] 10.1145\/345508.345545"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/4236.707689"},{"key":"e_1_2_1_22_1","doi-asserted-by":"crossref","first-page":"5360","DOI":"10.1126\/science.280.5360.98","article-title":"Searching the World Wide Web","volume":"280","author":"Lawrence S.","year":"1998","unstructured":"Lawrence , S. and Giles , C. L. 1998 b. Searching the World Wide Web . Science 280 , 5360 (April), 98--100.]] Lawrence, S. and Giles, C. L. 1998b. Searching the World Wide Web. Science 280, 5360 (April), 98--100.]]","journal-title":"Science"},{"key":"e_1_2_1_23_1","doi-asserted-by":"crossref","first-page":"107","DOI":"10.1038\/21987","article-title":"Accessibility of information on the Web","volume":"400","author":"Lawrence S.","year":"1999","unstructured":"Lawrence , S. and Giles , C. L. 1999 . Accessibility of information on the Web . Nature 400 , 107 -- 109 .]] Lawrence, S. and Giles, C. L. 1999. Accessibility of information on the Web. Nature 400, 107--109.]]","journal-title":"Nature"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/2.769447"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/2.901164"},{"key":"e_1_2_1_26_1","first-page":"55","article-title":"Weaving a better Web","volume":"23","author":"Mace S.","year":"1998","unstructured":"Mace , S. , Flohr , U. , Dobson , R. , and Graham , T. 1998 . Weaving a better Web . Byte 23 , 3, 55 -- 68 .]] Mace, S., Flohr, U., Dobson, R., and Graham, T. 1998. Weaving a better Web. Byte 23, 3, 55--68.]]","journal-title":"Byte"},{"volume-title":"Computer-Intensive Methods for Testing Hypotheses: An Introduction","author":"Noreen E. W.","key":"e_1_2_1_27_1","unstructured":"Noreen , E. W. 1989. Computer-Intensive Methods for Testing Hypotheses: An Introduction . Wiley , New York, NY .]] Noreen, E. W. 1989. Computer-Intensive Methods for Testing Hypotheses: An Introduction. Wiley, New York, NY.]]"},{"key":"e_1_2_1_28_1","volume-title":"DHTML: The Web as an open hypermedia system. Tech. rep. TIK-125. Computer Engineering and Networks Laboratory (TIK), ETH Zurich","author":"Oberholzer G.","year":"2002","unstructured":"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 .]] 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.]]"},{"volume-title":"Proceedings of the 25th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval. 11--18","author":"Park S. T.","key":"e_1_2_1_29_1","unstructured":"Park , S. T. , Pennock , D. M. , Giles , C. L. , and Krovetz , R . 2002. Analysis of lexical signatures for finding lost or related documents . In Proceedings of the 25th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval. 11--18 .]] 10.1145\/564376.564381 Park, S. T., Pennock, D. M., Giles, C. L., and Krovetz, R. 2002. Analysis of lexical signatures for finding lost or related documents. In Proceedings of the 25th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval. 11--18.]] 10.1145\/564376.564381"},{"volume-title":"Proceedings of Digital Documents and Electronic Publishing 2000 (DDEP00)","author":"Phelps T. A.","key":"e_1_2_1_30_1","unstructured":"Phelps , T. A. and Wilensky , R . 2000a. Robust hyperlinks: Cheap, everywhere, now . In Proceedings of Digital Documents and Electronic Publishing 2000 (DDEP00) .]] Phelps, T. A. and Wilensky, R. 2000a. Robust hyperlinks: Cheap, everywhere, now. In Proceedings of Digital Documents and Electronic Publishing 2000 (DDEP00).]]"},{"key":"e_1_2_1_31_1","unstructured":"Phelps T. A. and Wilensky R. 2000b. Robust hyperlinks cost just five words each. Tech. rep. UCB\/\/CSD-00-1091. University of California Berkeley Berkely CA.]]   Phelps T. A. and Wilensky R. 2000b. Robust hyperlinks cost just five words each. Tech. rep. UCB\/\/CSD-00-1091. University of California Berkeley Berkely CA.]]"},{"volume-title":"Web characterization activity: Answers to the W3C HTTP-NGs protocol design group's questions","author":"Pitkow J.","key":"e_1_2_1_32_1","unstructured":"Pitkow , J. 1998a. Web characterization activity: Answers to the W3C HTTP-NGs protocol design group's questions . World Wide Web Consortium (WWW.W 3.org).]] Pitkow, J. 1998a. Web characterization activity: Answers to the W3C HTTP-NGs protocol design group's questions. World Wide Web Consortium (WWW.W3.org).]]"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0169-7552(98)00066-X"},{"key":"e_1_2_1_34_1","first-page":"6","article-title":"Lockss: A permanent Web publishing and access system","volume":"7","author":"Reich V.","year":"2001","unstructured":"Reich , V. and Rosenthal , D. S. H. 2001 . Lockss: A permanent Web publishing and access system . D-Lib Mag. 7 , 6 (June), 55--68.]] Reich, V. and Rosenthal, D. S. H. 2001. Lockss: A permanent Web publishing and access system. D-Lib Mag. 7, 6 (June), 55--68.]]","journal-title":"D-Lib Mag."},{"volume-title":"Proceedings of the AAAI Fall Symposium on Using Uncertainty Within Computation. 121--128","author":"Rusmevichientong P.","key":"e_1_2_1_35_1","unstructured":"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 .]] 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.]]"},{"key":"e_1_2_1_36_1","unstructured":"Shafer K. Weibel S. Jul E. and Fausey J. 1996. Introduction to persistent uniform resource locators. In INET 96. Internet Society Reston Va.]]  Shafer K. Weibel S. Jul E. and Fausey J. 1996. Introduction to persistent uniform resource locators. In INET 96. Internet Society Reston Va.]]"},{"key":"e_1_2_1_37_1","doi-asserted-by":"crossref","unstructured":"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.]]   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.]]","DOI":"10.17487\/rfc1737"},{"key":"e_1_2_1_38_1","volume-title":"Proceedings of the SIGIR","author":"Voorhees E. M.","year":"2001","unstructured":"Voorhees , E. M. 2001 . Evaluation by highly relevant documents . In Proceedings of the SIGIR 2001. 74--80.]] 10.1145\/383952.383963 Voorhees, E. M. 2001. Evaluation by highly relevant documents. In Proceedings of the SIGIR 2001. 74--80.]] 10.1145\/383952.383963"},{"key":"e_1_2_1_39_1","unstructured":"Witten I. H. Moffat A. and Bell T. C. 1999. Managing Gigabytes 2nd ed. Harcourt Science and Technology Company San Diego CA.]]  Witten I. H. Moffat A. and Bell T. C. 1999. Managing Gigabytes 2nd ed. Harcourt Science and Technology Company San Diego CA.]]"}],"container-title":["ACM Transactions on Information Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1028099.1028101","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1028099.1028101","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T16:31:16Z","timestamp":1750264276000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1028099.1028101"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004,10]]},"references-count":39,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2004,10]]}},"alternative-id":["10.1145\/1028099.1028101"],"URL":"https:\/\/doi.org\/10.1145\/1028099.1028101","relation":{},"ISSN":["1046-8188","1558-2868"],"issn-type":[{"type":"print","value":"1046-8188"},{"type":"electronic","value":"1558-2868"}],"subject":[],"published":{"date-parts":[[2004,10]]},"assertion":[{"value":"2004-10-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}