Building a distributed full-text index for the web

ABSTRACT

We identify crucial design issues in building a distributed inverted index for a large collection of Web pages. We introduce a novel pipelining technique for structuring the core index-building system that substantially reduces the index construction time. We also propose a storage scheme for creating and managing inverted files using an embedded database system. We suggest and compare different strategies for collecting global statistics from distributed inverted indexes. Finally, we present performance results from experiments on a testbed distributed Web indexing system that we have implemented.

REFERENCES

• 1: Anh Ngoc Vo , Alistair Moffat, Compressed inverted files with reduced decoding overheads, Proceedings of the 21st annual international ACM SIGIR conference on Research and development in information retrieval, p.290-297, August 24-28, 1998, Melbourne, Australia [doi>10.1145/290941.291011]
• 2: David C. Blair, An extended relational document retrieval model, Information Processing and Management: an International Journal, v.24 n.3, p.349-371, May 1988 [doi>10.1016/0306-4573(88)90101-X]
• 3: Eric W. Brown, Fast evaluation of structured queries for information retrieval, Proceedings of the 18th annual international ACM SIGIR conference on Research and development in information retrieval, p.30-38, July 09-13, 1995, Seattle, Washington, United States [doi>10.1145/215206.215329]
• 4: Eric W. Brown , James P. Callan , W. Bruce Croft, Fast Incremental Indexing for Full-Text Information Retrieval, Proceedings of the 20th International Conference on Very Large Data Bases, p.192-202, September 12-15, 1994
• 5: Eric W. Brown , James P. Callan , W. Bruce Croft , J. Eliot B. Moss, Supporting full-text information retrieval with a persistent object store, Proceedings of the 4th international conference on extending database technology on Advances in database technology, p.365-378, May 1994, Cambridge, United Kingdom
• 6: CCITT. 1988. Recommendation X.209, Specification of Basic Encoding Rules for Abstract Syntax Notation one (ASN. 1).
• 7: Soumen Chakrabarti , S. Muthukrishnan, Resource scheduling for parallel database and scientific applications, Proceedings of the eighth annual ACM symposium on Parallel algorithms and architectures, p.329-335, June 24-26, 1996, Padua, Italy [doi>10.1145/237502.237577]
• 8: 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
• 9: CRASWELL, N., HAWKING,D.,AND THISTLEWALTE, P. 1999. Merging results from isolated search engines. In Proceedings of the 10th Australasian Database Conference (January).
• 10: Owen de Kretser , Alistair Moffat , Tim Shimmin , Justin Zobel, Methodologies for Distributed Information Retrieval, Proceedings of the The 18th International Conference on Distributed Computing Systems, p.66, May 26-29, 1998
• 11: Chris Faloutsos , Stavros Christodoulakis, Signature files: an access method for documents and its analytical performance evaluation, ACM Transactions on Information Systems (TOIS), v.2 n.4, p.267-288, Oct. 1984 [doi>10.1145/2275.357411]
• 12: Hector Garcia-Molina , Jennifer Widom , Jeffrey D. Ullman, Database System Implementation, Prentice-Hall, Inc., Upper Saddle River, NJ, 1999
• 13: GORSSMAN,D.A.AND DRISCOLL, J. R. 1992. Structuring text within a relation system. In Proceedigns of the 3rd International Conference on Database and Expert System Applications (September), 72-77.
• 14: GRAVANO, L., CHANG, K., GARCIA-MOLINA, H., LAGOZE,C.,AND PAEPCKE, A. 1997. STARTS-stanford protocol for internet retrieval and search. http://www-db.stanford.edu/ gravano/starts.html.
• 15: HAWKING,D.AND CRASWELL, N. 1998. Overview of TREC-7 very large collection track. In Proceedings of the Seventh Text Retrieval Conference (November), 91-104.
• 16: Jun Hirai , Sriram Raghavan , Hector Garcia-Molina , Andreas Paepcke, WebBase: a repository of Web pages, Proceedings of the 9th international World Wide Web conference on Computer networks : the international journal of computer and telecommunications netowrking, p.277-293, June 2000, Amsterdam, The Netherlands
• 17: INKTOMI. 2000. Inktomi WebMap. http://www.inktomi.com/webmap/.
• 18: Byeong-Soo Jeong , Edward Omiecinski, Inverted File Partitioning Schemes in Multiple Disk Systems, IEEE Transactions on Parallel and Distributed Systems, v.6 n.2, p.142-153, February 1995 [doi>10.1109/71.342125]
• 19: Steve Lawrence , C. Lee Giles, Inquirus, the NECI meta search engine, Proceedings of the seventh international conference on World Wide Web 7, p.95-105, April 1998, Brisbane, Australia
• 20: LAWRENCE,S.AND GILES, C. L. 1999. Accessibility of information on the web. Nature 400, 107-109.
• 21: Udi Manber , Gene Myers, Suffix arrays: a new method for on-line string searches, Proceedings of the first annual ACM-SIAM symposium on Discrete algorithms, p.319-327, January 22-24, 1990, San Francisco, California, United States
• 22: Ian A. MacLeod , Patrick Martin , Brent Nordin, A design of a distributed full text retrieval system, Proceedings of the 9th annual international ACM SIGIR conference on Research and development in information retrieval, p.131-137, September 1986, Palazzo dei Congressi, Pisa, Italy [doi>10.1145/253168.253197]
• 23: MELNIK, S., GARCIA-MOLINA, H., YANG,B.,AND RAGHAVAN, S. 2000. Building a distributed full-text index for the web. Technical Report SIDL-WP-2000-0140 (July), Stanford Digital Library Project, Computer Science Dept., Stanford University. Available at www-diglib.stanford.edu/cgibin/get/SIDL-WP-2000-0140.
• 24: Alistair Moffat , Timothy A. H. Bell, In situ generation of compressed inverted files, Journal of the American Society for Information Science, v.46 n.7, p.537-550, Aug. 1995 [doi>10.1002/(SICI)1097-4571(199508)46:7<537::AID-ASI7>3.0.CO;2-P]
• 25: Alistair Moffat , Justin Zobel, Self-indexing inverted files for fast text retrieval, ACM Transactions on Information Systems (TOIS), v.14 n.4, p.349-379, Oct. 1996 [doi>10.1145/237496.237497]
• 26: OLSON, M., BOSTIC, K., AND SELTZER, M. 1999. Berkeley DB. In Proceedings of the 1999 Summer Usenix Technical Conference (June).
• 27: Berthier A. Ribeiro-Neto , Ramurti A. Barbosa, Query performance for tightly coupled distributed digital libraries, Proceedings of the third ACM conference on Digital libraries, p.182-190, June 23-26, 1998, Pittsburgh, Pennsylvania, United States [doi>10.1145/276675.276695]
• 28: Berthier Ribeiro-Neto , Edleno S. Moura , Marden S. Neubert , Nivio Ziviani, Efficient distributed algorithms to build inverted files, Proceedings of the 22nd annual international ACM SIGIR conference on Research and development in information retrieval, p.105-112, August 15-19, 1999, Berkeley, California, United States [doi>10.1145/312624.312663]
• 29: SALTON, G. 1989. Information Retrieval: Data Structures and Algorithms. Addison-Wesley, Reading, Massachussetts.
• 30: Anthony Tomasic , Hector Garcia-Molina, Performance of inverted indices in shared-nothing distributed text document informatioon retrieval systems, Proceedings of the second international conference on Parallel and distributed information systems, p.8-17, January 1993, San Diego, California, United States
• 31: Anthony Tomasic , Hector Garcia-Molina, Query processing and inverted indices in shared: nothing text document information retrieval systems, The VLDB Journal — The International Journal on Very Large Data Bases, v.2 n.3, July 1993
• 32: Anthony Tomasic , Héctor García-Molina , Kurt Shoens, Incremental updates of inverted lists for text document retrieval, Proceedings of the 1994 ACM SIGMOD international conference on Management of data, p.289-300, May 24-27, 1994, Minneapolis, Minnesota, United States
• 33: VILES, C. L. 1994. Maintaining state in a distributed information retrieval system. In 32nd Southeast Conference of the ACM, ACM Press, New York, NY, 157-161.
• 34: Charles L. Viles , James C. French, Dissemination of collection wide information in a distributed information retrieval system, Proceedings of the 18th annual international ACM SIGIR conference on Research and development in information retrieval, p.12-20, July 09-13, 1995, Seattle, Washington, United States [doi>10.1145/215206.215327]
• 35: Ian H. Witten , Alistair Moffat , Timothy C. Bell, Managing gigabytes (2nd ed.): compressing and indexing documents and images, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1999
• 36: Justin Zobel , Alistair Moffat , Ron Sacks-Davis, An Efficient Indexing Technique for Full Text Databases, Proceedings of the 18th International Conference on Very Large Data Bases, p.352-362, August 23-27, 1992

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.1 Content Analysis and Indexing
          Subjects: Indexing methods

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.4 Systems and Software
          Subjects: Distributed systems

General Terms:
Design, Performance

Keywords:
Distributed indexing, Embedded databases, Inverted files, Pipelining, Text retrieval