Surrogate subsets: a free space management strategy for the index of a text retrieval system

ABSTRACT

This paper presents a new data structure and an associated strategy to be utilized by indexing facilities for text retrieval systems. The paper starts by reviewing some of the goals that may be considered when designing such an index and continues with a small survey of various current strategies. It then presents an indexing strategy referred to as surrogate subsets discussing its appropriateness in the light of the specified goals. Various design issues and implementation details are discussed. Our strategy requires that a surrogate file be divided into a large number of subsets separated by free space which will allow the index to expand when new material is appended to the database. Experimental results report on the utilization of free space when the database is enlarged.

REFERENCES

• BAY72: BAYER, R. AND MCCREIGHT, E., Organization and maintenance of large ordered indexes, Acta Informatica, vol. 1, no. 3, 1972, pp. 173-189. ~
• BER87: P. Bruce Berra , Soon Myoung Chung , Nabil I. Hachem, Computer architecture for a surrogate file to a very large data/knowledge base, Computer, v.20 n.3, p.25-32, March 1987 [doi>10.1109/MC.1987.1663506]
• CHR84: CHRISTODOULAKIS, S. AND FALOUTSOS, C., Design considerations for a message file server, IEEE Trans. Sofn#,are Engineering, Vol. SE-10, No. 2, Mar. 1984, pp. 201-210.
• CHR86: Stavros Christodoulakis , Christos Faloutsos, Design and performance considerations for an optical disk-based, multimedia object server, Computer, v.19 n.12, p.45-56, Dec. 1986 [doi>10.1109/MC.1986.1663127]
• DEF88: DEFAZIO, S. AND GREENWALD, C., The Mead information retrieval system, IEEE Compcon 88, Feb. 1988, pp. 431.
• DEF89: DEFAZIO, S., Private communication.
• FAL84: 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]
• FAL85: Chris Faloutsos, Access methods for text, ACM Computing Surveys (CSUR), v.17 n.1, p.49-74, March 1985 [doi>10.1145/4078.4080]
• FAL87D: FALOUTSOS, C. AND CHAN, R., Fast text access methods for optical disks- designs and performance comparison, UMIACS-TR-87-66, CS-TR- 1958, Dept. of Comp. Sci. and Inst. for Adv. Comp. Studies, Univ. of Maryland, Dec. 1987, 29 pages.
• FAL87S: Christos Faloutsos , Stavros Christodoulakis, Optimal signature extraction and information loss, ACM Transactions on Database Systems (TODS), v.12 n.3, p.395-428, Sept. 1987 [doi>10.1145/27629.214285]
• HAS81: HASKIN, R. L., Special purpose processors for text retrieval, Database Engineering, Vol. 4, No. 1, Sept. 1981, pp. 16-29.
• LAR83: Per-Åke Larson, A Method for Speeding Up Text Retrieval, Databases for Business and Office Applications, Database Week, p.117-123, May 23-26, 1983 [doi>10.1145/647004.711872]
• ROB79: ROBERTS, C. S., Partial-match retrieval via the method of superimposed codes, Proc. IEEE, 67,12, Dec. 1979, 1624-1642.
• SAL86: Gerard Salton, Another look at automatic text-retrieval systems, Communications of the ACM, v.29 n.7, p.648-656, July 1986 [doi>10.1145/6138.6149]
• STA86: Craig Stanfill , Brewster Kahle, Parallel free-text search on the connection machine system, Communications of the ACM, v.29 n.12, p.1229-1239, Dec. 1986 [doi>10.1145/7902.7907]
• TEO82: Toby J. Teorey , James P. Fry, Design of Database Structures, Prentice Hall Professional Technical Reference, 1982
• TSI83: Dennis Tsichritzis , Stavros Christodoulakis, Message files, ACM Transactions on Information Systems (TOIS), v.1 n.1, p.88-98, Jan. 1983 [doi>10.1145/357423.357429]

INDEX TERMS

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

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.1 Content Analysis and Indexing
          Subjects: Indexing methods

General Terms:
Algorithms, Design