Managing duplicates in a web archive

ABSTRACT

Crawlers harvest the web by iteratively downloading documents referenced by URLs. It is frequent to find different URLs that refer to the same document, leading crawlers to download duplicates. Hence, web archives built through incremental crawls waste space storing these documents. In this paper, we study the existence of duplicates within a web archive and discuss strategies to eliminate them at storage level during the crawl. We present a storage system architecture that addresses the requirements of web archives and detail its implementation and evaluation. The system is now supporting an archive for the Portuguese web replacing previous NFS-based storage servers. Experimental results showed that the elimination of duplicates can improve storage throughput. The web storage system outperformed NFS based storage by 68% in read operations and by 50% in write operations.¹

REFERENCES

• 1: B. Berliner. CVS II: Parallelizing software development. In Proceedings of the USENIX Winter 1990 Technical Conference, pages 341--352, Berkeley, CA, 1990, USENIX Association.
• 2: Krishna Bharat , Andrei Broder, Mirror, mirror on the Web: a study of host pairs with replicated content, Proceeding of the eighth international conference on World Wide Web, p.1579-1590, May 1999, Toronto, Canada
• 3: S. Brin, J. Davis, and H. García-Molina. Copy detection mechanisms for digital documents. pages 398--409, 1995.
• 4: Sergey Brin , Lawrence Page, The anatomy of a large-scale hypertextual Web search engine, Computer Networks and ISDN Systems, v.30 n.1-7, p.107-117, April 1, 1998
• 5: T. Burkard. Herodotus: A peer-to-peer web archival system, 2002.
• 6: M. Burner and B. Kahle. WWW Archive File Format Specification, September 1996.
• 7: B. Callaghan, B. Pawlowski, and P. Staubach. RFC 1813: NFS Version 3 Protocol Specification. Sun Microsystems, Inc., June 1995.
• 8: J. Campos. Versus: a web repository. Master thesis, 2003.
• 9: N. Cardoso, M. J. Silva, and M. Costa. The XLDB Group at CLEF'2004.
• 10: W. Cathro and T. Boston. Development of a digital services architecture at the national library of australia. EduCause, Australasia 2003, page 24, 2003.
• 11: Junghoo Cho , Hector Garcia-Molina, Estimating frequency of change, ACM Transactions on Internet Technology (TOIT), v.3 n.3, p.256-290, August 2003 [doi>10.1145/857166.857170]
• 12: J. Cho, H. Garcia-Molina, T. Haveliwala, W. Lam, A. Paepcke, S. Raghavan, and G. Wesley. Stanford webbase components and applications. Technical report, Stanford Database Group, July 2004.
• 13: B. F. Cooper, A. Crespo, and H. Garcia-Molina. The stanford archival repository project: Preserving our digital past. Technical report 2002-47, Department of Computer Science, Stanford University, October 2002.
• 14: Arturo Crespo , Hector Garcia-Molina, Archival storage for digital libraries, Proceedings of the third ACM conference on Digital libraries, p.69-78, June 23-26, 1998, Pittsburgh, Pennsylvania, United States [doi>10.1145/276675.276683]
• 15: L. Daigle, D. van Gulik, R. Iannella, and P. Faltstrom. Uniform Resource Names (URN) Namespace Definition Mechanisms, October 2002.
• 16: T. Denehy and W. Hsu. Duplicate management for reference data. Technical report RJ 10305, IBM Research, October 2003.
• 17: Dennis Fetterly , Mark Manasse , Marc Najork , Janet Wiener, A large-scale study of the evolution of web pages, Proceedings of the 12th international conference on World Wide Web, May 20-24, 2003, Budapest, Hungary [doi>10.1145/775152.775246]
• 18: Raphael A. Finkel , Arkady Zaslavsky , Krisztián Monostori , Heinz Schmidt, Signature extraction for overlap detection in documents, Proceedings of the twenty-fifth Australasian conference on Computer science, p.59-64, January 01, 2002, Melbourne, Victoria, Australia
• 19: D. Gomes, A. L. Santos, and M. J. Silva. Webstore: A manager for incremental storage of contents. DI/FCUL TR 04--15, Department of Informatics, University of Lisbon, November 2004.
• 20: Daniel Gomes , Mário J. Silva, Characterizing a national community web, ACM Transactions on Internet Technology (TOIT), v.5 n.3, p.508-531, August 2005 [doi>10.1145/1084772.1084775]
• 21: Y. Hafri and C. Djeraba. Dominos: A new web crawler's design. In 4th International Web Archiving Workshop (IWAW04), Bath, UK, September 2004.
• 22: J. Hakala. Collecting and preserving the web: Developing and testing the nedlib harvester. RLG Diginews, 5(2), April 2001.
• 23: Allan Heydon , Marc Najork, Mercator: A scalable, extensible Web crawler, World Wide Web, v.2 n.4, p.219-229, 1999 [doi>10.1023/A:1019213109274]
• 24: R. J. Honicky and E. L. Miller. A fast algorithm for online placement and reorganization of replicated data. Nice, France, Apr. 2003.
• 25: Terence Kelly , Jeffrey Mogul, Aliasing on the world wide web: prevalence and performance implications, Proceedings of the 11th international conference on World Wide Web, May 07-11, 2002, Honolulu, Hawaii, USA [doi>10.1145/511446.511484]
• 26: C. Lampos, M. Eirinaki, D. Jevtuchova, and M. Vazirgiannis. Archiving the greek web. In 4th International Web Archiving Workshop (IWAW04), Bath, UK, September 2004.
• 27: J. MacDonald. Versioned file archiving, compression, and distribution.
• 28: J. Mogul. A trace-based analysis of duplicate suppression in HTTP. Technical Report 99/2, Compaq Computer Corporation Western Research Laboratory, November 1999.
• 29: Norman Noronha , João P. Campos , Daniel Gomes , Mário J. Silva , José Luis Borbinha, A Deposit for Digital Collections, Proceedings of the 5th European Conference on Research and Advanced Technology for Digital Libraries, p.200-212, September 04-09, 2001
• 30: Anna Patterson, Why Writing Your Own Search Engine Is Hard, Queue, v.2 n.2, April 2004 [doi>10.1145/988392.988407]
• 31: K. Persson. Kulturarw description. http://www.kb.se/kw3/ENG/Description.htm, March 2005.
• 32: M. O. Rabin, PROBABILISTIC ALGORITHM IN FINITE FIELDS, Massachusetts Institute of Technology, Cambridge, MA, 1979
• 33: Sean Rhea , Patrick Eaton , Dennis Geels , Hakim Weatherspoon , Ben Zhao , John Kubiatowicz, Awarded Best Student Paper! - Pond: The OceanStore Prototype, Proceedings of the 2nd USENIX Conference on File and Storage Technologies, March 31-31, 2003, San Francisco, CA
• 34: Ohad Rodeh , Avi Teperman, zFS " A Scalable Distributed File System Using Object Disks, Proceedings of the 20 th IEEE/11 th NASA Goddard Conference on Mass Storage Systems and Technologies (MSS'03), p.207, April 07-10, 2003
• 35: N. Shivakumar and H. García-Molina. SCAM: A copy detection mechanism for digital documents. In Proceedings of the Second Annual Conference on the Theory and Practice of Digital Libraries, 1995.
• 36: Narayanan Shivakumar , Hector Garcia-Molina, Finding Near-Replicas of Documents and Servers on the Web, Selected papers from the International Workshop on The World Wide Web and Databases, p.204-212, March 27-28, 1998
• 37: Design and Implementation of a High-Performance Distributed Web Crawler, Proceedings of the 18th International Conference on Data Engineering, p.357, February 26-March 01, 2002
• 38: M. J. Silva. Searching and archiving the web with tumba! In CAPSI 2003 - 4a. Conferência da Associaĉão Portuguesa de Sistemas de Informaĉão, Porto, Portugal, November 2003.
• 39: Diomidis Spinellis, The decay and failures of web references, Communications of the ACM, v.46 n.1, p.71-77, January 2003 [doi>10.1145/602421.602422]
• 40: L. L. You and C. Karamanolis. Evaluation of efficient archival storage techniques. In 21st IEEE/12th NASA Goddard Conference on Mass Storage Systems and Technologies, College Park, MD, April 2004.

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.2 Storage Management

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.3 File Systems Management
          Subjects: Distributed file systems

  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.7 Digital Libraries
          Subjects: Dissemination

  I. Computing Methodologies
  I.7 DOCUMENT AND TEXT PROCESSING
      I.7.1 Document and Text Editing
          Subjects: Document management

General Terms:
Design, Management