Dynamic maintenance of web indexes using landmarks

ABSTRACT

Recent work on incremental crawling has enabled the indexed document collection of a search engine to be more synchronized with the changing World Wide Web. However, this synchronized collection is not immediately searchable, because the keyword index is rebuilt from scratch less frequently than the collection can be refreshed. An inverted index is usually used to index documents crawled from the web. Complete index rebuild at high frequency is expensive. Previous work on incremental inverted index updates have been restricted to adding and removing documents. Updating the inverted index for previously indexed documents that have changed has not been addressed.In this paper, we propose an efficient method to update the inverted index for previously indexed documents whose contents have changed. Our method uses the idea of landmarks together with the diff algorithm to significantly reduce the number of postings in the inverted index that need to be updated. Our experiments verify that our landmark-diff method results in significant savings in the number of update operations on the inverted index.

REFERENCES

• 1: Lars Arge , Octavian Procopiuc , Sridhar Ramaswamy , Torsten Suel , Jan Vahrenhold , Jeffrey Scott Vitter, A Unified Approach for Indexed and Non-Indexed Spatial Joins, Proceedings of the 7th International Conference on Extending Database Technology: Advances in Database Technology, p.413-429, March 27-31, 2000
• 2: Ricardo A. Baeza-Yates , Berthier Ribeiro-Neto, Modern Information Retrieval, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1999
• 3: Robert S. Boyer , J. Strother Moore, A fast string searching algorithm, Communications of the ACM, v.20 n.10, p.762-772, Oct. 1977 [doi>10.1145/359842.359859]
• 4: Brian E. Brewington , George Cybenko, Keeping Up with the Changing Web, Computer, v.33 n.5, p.52-58, May 2000 [doi>10.1109/2.841784]
• 5: 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
• 6: J. Cho and H. Garcia-Molina. Estimating frequency of change. Submitted for publication, 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: C. Clarke and G. Cormack. Dynamic inverted indexes for a distributed full-text retrieval system. Tech. Report CS-95-01, Univ. of Waterloo CS Dept., 1995.
• 9: C. Clarke, G. Cormack, and F. Burkowski. Fast inverted indexes with on-line update. Tech. Report CS-94-40, Univ. of Waterloo CS Dept., 1994.
• 10: D. Cutting , J. Pedersen, Optimization for dynamic inverted index maintenance, Proceedings of the 13th annual international ACM SIGIR conference on Research and development in information retrieval, p.405-411, September 05-07, 1990, Brussels, Belgium [doi>10.1145/96749.98245]
• 11: William B. Frakes , Ricardo Baeza-Yates, Information retrieval: data structures and algorithms, Prentice-Hall, Inc., Upper Saddle River, NJ, 1992
• 12: D. E. Knuth, J. H. Morris, and V. B. Pratt. Fast pattern matching in strings. SIAM Journal of Computing, 6, 323--350, 1977.
• 13: S. Lawrence and C. L. Giles. Accessibility of information on the web. Nature, 400, 107--109, 1999.
• 14: Quanzhong Li , Bongki Moon, Indexing and Querying XML Data for Regular Path Expressions, Proceedings of the 27th International Conference on Very Large Data Bases, p.361-370, September 11-14, 2001
• 15: Lipyeow Lim , Min Wang , Sriram Padmanabhan , Jeffrey Scott Vitter , Ramesh C. Agarwal, Characterizing Web Document Change, Proceedings of the Second International Conference on Advances in Web-Age Information Management, p.133-144, July 09-11, 2001
• 16: U. Manber and S. Wu. GLIMPSE: A tool to search through entire file systems. In Proceedings of the Winter 1994 USENIX Conf., 23--32. USENIX, 1994.
• 17: Sergey Melnik , Sriram Raghavan , Beverly Yang , Hector Garcia-Molina, Building a distributed full-text index for the Web, Proceedings of the 10th international conference on World Wide Web, p.396-406, May 01-05, 2001, Hong Kong, Hong Kong [doi>10.1145/371920.372095]
• 18: Sergey Brin , Lawrence Page, The anatomy of a large-scale hypertextual Web search engine, Proceedings of the seventh international conference on World Wide Web 7, p.107-117, April 1998, Brisbane, Australia
• 19: 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
• 20: Esko Ukkonen, Algorithms for approximate string matching, Information and Control, v.64 n.1-3, p.100-118, Jan./Feb./March 1985 [doi>10.1016/S0019-9958(85)80046-2]
• 21: Jeffrey Scott Vitter, Faster methods for random sampling, Communications of the ACM, v.27 n.7, p.703-718, July 1984 [doi>10.1145/358105.893]
• 22: Jeffrey S. Vitter, An efficient I/O interface for optical disks, ACM Transactions on Database Systems (TODS), v.10 n.2, p.129-162, June 1985 [doi>10.1145/3857.3862]
• 23: 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
• 24: Chun Zhang , Jeffrey Naughton , David DeWitt , Qiong Luo , Guy Lohman, On supporting containment queries in relational database management systems, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.425-436, May 21-24, 2001, Santa Barbara, California, United States

INDEX TERMS

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

Additional Classification:
  I. Computing Methodologies
  I.7 DOCUMENT AND TEXT PROCESSING
      I.7.m Miscellaneous

General Terms:
Performance

Keywords:
inverted files, update processing