Versioning a full-text information retrieval system

ABSTRACT

In this paper, we present an approach to the incorporation of object versioning into a distributed full-text information retrieval system. We propose an implementation based on “partially versioned” index sets, arguing that its space overhead and query-time performance make it suitable for full-text IR, with its heavy dependence on inverted indexing. We develop algorithms for computing both historical queries and time range queries and show how these algorithms can be applied to a number of problems in distributed information management, such as data replication, caching, transactional consistency, and hybrid media repositories.

REFERENCES

• AHLSEN84: Matts Ahlsen , Anders Bjornerstedt , Stefan Britts , Christer Hulten , Lars Soderlund, An architecture for object management in OIS, ACM Transactions on Information Systems (TOIS), v.2 n.3, p.173-196, July 1984 [doi>10.1145/1206.1207]
• ANICK90: P. G. Anick , J. D. Brennan , R. A. Flynn , D. R. Hanssen , B. Alvey , J. M. Robbins, A direct manipulation interface for boolean information retrieval via natural language query, Proceedings of the 13th annual international ACM SIGIR conference on Research and development in information retrieval, p.135-150, September 05-07, 1990, Brussels, Belgium [doi>10.1145/96749.98015]
• ANICK91: Peter G. Anick , Rex A. Flynn , David R. Hanssen, Addressing the requirements of a dynamic corporate textual information base, Proceedings of the 14th annual international ACM SIGIR conference on Research and development in information retrieval, p.163-172, October 13-16, 1991, Chicago, Illinois, United States [doi>10.1145/122860.122876]
• BOOKSTEIN90: A. Bookstein , S. T. Klein, Construction of optimal graphs for bit-vector compression, Proceedings of the 13th annual international ACM SIGIR conference on Research and development in information retrieval, p.327-342, September 05-07, 1990, Brussels, Belgium [doi>10.1145/96749.98236]
• BURKOWSKI92: Forbes J. Burkowski, An algebra for hierarchically organized text-dominated databases, Information Processing and Management: an International Journal, v.28 n.3, p.333-348, 1992 [doi>10.1016/0306-4573(92)90079-F]
• COOMBS90: J. H. Coombs, Hypertext, full text, and automatic linking, Proceedings of the 13th annual international ACM SIGIR conference on Research and development in information retrieval, p.83-98, September 05-07, 1990, Brussels, Belgium [doi>10.1145/96749.98010]
• CROFT87: W. B. Croft , R. H. Thompson, I3R: a new approach to the design of document retrieval systems, Journal of the American Society for Information Science, v.38 n.6, p.389-404, Nov. 1987 [doi>10.1002/(SICI)1097-4571(198711)38:6<389::AID-ASI1>3.0.CO;2-4]
• DITTRICH88: Klaus R. Dittrich , Raymond A. Lorie, Version Support for Engineering Database Systems, IEEE Transactions on Software Engineering, v.14 n.4, p.429-437, April 1988 [doi>10.1109/32.4664]
• GADIA88: Shashi K. Gadia, A homogeneous relational model and query languages for temporal databases, ACM Transactions on Database Systems (TODS), v.13 n.4, p.418-448, Dec. 1988 [doi>10.1145/49346.50065]
• GOLDBERG83: Adele Goldberg , David Robson, Smalltalk-80: the language and its implementation, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1983
• GUTTMAN84: Antonin Guttman, R-trees: a dynamic index structure for spatial searching, Proceedings of the 1984 ACM SIGMOD international conference on Management of data, June 18-21, 1984, Boston, Massachusetts
• KAHLE91: Kahle, B. and A. Medlar. An Information System for Corporate Users: Wide Area Information Servers, WAIS Corporate Paper version 3, April 1991.
• KATZ84: Katz, Randy H. and Lehman, Tobin J. Database Support for Versions and Alternatives of Large Design Files, IEEE Transactions on Software Engineering, Vol. SF,-10, no. 2, March 1984, pp. 191-200.
• KENT89: Kent, William, An Overview of the Versioning Problem. in Proceedings of 1989 ACM SIGMOD Conference on the Management of Data, 1989, pp. 5-7.
• KOLOVSON89: Kolovson, Curtis and Stonbraker, Michael. Indexing Techniques for Historical Databases. Memorandum No. UCB/ERL M89/34, Electronics Research Laboratory, College of Engineering, University of California, Berkeley, Apr. 1989.
• KOLOVSON90: Kolovson, Curtis and Stonbraker, Michael. S- Trees: Database Indexing Techniques for Multi-dimensional Interval Data. Memorandum No. UCB/ERL M90/35, Electronics Research Laboratory, College of Engineering, University of California, Berkeley, Apr. 1990.
• KHOSHAFIAN86: Setrag N. Khoshafian , George P. Copeland, Object identity, Conference proceedings on Object-oriented programming systems, languages and applications, p.406-416, September 29-October 02, 1986, Portland, Oregon, United States
• ROWE87: Lawrence A. Rowe , Michael Stonebraker, The POSTGRES Data Model, Proceedings of the 13th International Conference on Very Large Data Bases, p.83-96, September 01-04, 1987
• SALTON89: Gerard Salton, Automatic text processing: the transformation, analysis, and retrieval of information by computer, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1989
• SNODGRASS90: Richard Snodgrass, Temporal databases status and research directions, ACM SIGMOD Record, v.19 n.4, p.83-89, Dec. 1990 [doi>10.1145/122058.122068]
• STONEBRAKER87: Michael Stonebraker, The Design of the POSTGRES Storage System, Proceedings of the 13th International Conference on Very Large Data Bases, p.289-300, September 01-04, 1987

INDEX TERMS

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

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.1 Content Analysis and Indexing
          Subjects: Indexing methods
      H.3.3 Information Search and Retrieval
          Subjects: Retrieval models

General Terms:
Algorithms