Partitioned signature files: design issues and performance evaluation

ABSTRACT

A signature file acts as a filtering mechanism to reduce the amount of text that needs to be searched for a query. Unfortunately, the signature file itself must be exhaustively searched, resulting in degraded performance for a large file size. We propose to use a deterministic algorithm to divide a signature file into partitions, each of which contains signatures with the same “key.” The signature keys in a partition can be extracted and represented as the partition's key. The search can then be confined to the subset of partitions whose keys match the query key. Our main concern here is to study methods for obtaining the keys and their performance in terms of their ability to reduce the search space. Owing to the reduction of search space, partitioning a signature file has a direct benefit in a sequential search (single-processor) environment. In a parallel environment, search can be conducted in parallel effectively by allocating one or more partitions to a processor. Partitioning the signature tile with a deterministic method (as opposed to a random partitioning scheme) provides intraquery parallelism as well as interquery parallelism. In this paper, we outline the criteria for evaluating partitioning schemes. Three algorithms are described and studied. An analytical study of the performance of the algorithms is provided and the results are verified with simulation.

REFERENCES

• 1: Sudhir R. Ahuja , Charles S. Roberts, An associative/parallel processor for partial match retrieval using superimposed codes, Proceedings of the 7th annual symposium on Computer Architecture, p.218-227, May 06-08, 1980, La Baule, United States [doi>10.1145/800053.801929]
• 2: 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]
• 3: CHRISTODOULAKIS, S., AND FALOUTSOS, C. Design considerations for a message file server. IEEE Trans. Soft. Eng. SE-IO, 2 (Mar. 1984), 201-210.
• 4: Uwe Deppisch, S-tree: a dynamic balanced signature index for office retrieval, Proceedings of the 9th annual international ACM SIGIR conference on Research and development in information retrieval, p.77-87, September 1986, Palazzo dei Congressi, Pisa, Italy [doi>10.1145/253168.253189]
• 5: Chris Faloutsos, Access methods for text, ACM Computing Surveys (CSUR), v.17 n.1, p.49-74, March 1985 [doi>10.1145/4078.4080]
• 6: Christos Faloutsos , Stavros Christodoulakis, Description and performance analysis of signature file methods for office filing, ACM Transactions on Information Systems (TOIS), v.5 n.3, p.237-257, July 1987 [doi>10.1145/27641.28057]
• 7: 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]
• 8: Richard A. Gustafson, Elements of the randomized combinatorial file structure, Proceedings of the 1971 international ACM SIGIR conference on Information storage and retrieval, April 01-02, 1971, College Park, Maryland [doi>10.1145/511285.511304]
• 9: Dik Lun Lee, A Word-Parallel, Bit-Serial Signature Processor for Superimposed Coding, Proceedings of the Second International Conference on Data Engineering, p.352-359, February 05-07, 1986
• 10: LEE, D. L., AND LENG, C.-W. A fast access method based on partitioned signature files. Submitted for publication, 1988.
• 11: LEE, D. L., AND LOCHOVSKY, F. H. Text retrieval machines. In Office Automation, D. C. Tsichritzis, Ed. Springer-Verlag, New York, 1985, pp. 339-375.
• 12: OROSZ, G., AND TACKACS, L. Some probability problems concerning the marking of codes in the superimposition field. J. Doc. 12, 4 (Dec. 1956), 231-234.
• 13: John L. Pfaltz , William J. Berman , Edgar M. Cagley, Partial-match retrieval using indexed descriptor files, Communications of the ACM, v.23 n.9, p.522-528, Sept. 1980 [doi>10.1145/359007.359013]
• 14: RIVEST, R.L. Partial-match retrieval algorithms. SIAM J. Comput. 5, 1 (1976), 19-50.
• 15: ROBERTS, C.S. Partial-match retrieval via a method of superimposed codes. In Proceedings of the IEEE 67, 12 (Dec. 1979), 1624-1642.
• 16: SACKS-DAVIS, R., AND RAMAMOHANARAO, K. A two level superimposed coding scheme for partial match retrieval. Inf. Syst. 8, 4 (1983), 273-280.
• 17: R. Sacks-Davis , A. Kent , K. Ramamohanarao, Multikey access methods based on superimposed coding techniques, ACM Transactions on Database Systems (TODS), v.12 n.4, p.655-696, Dec. 1987 [doi>10.1145/32204.32222]
• 18: 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]
• 19: 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.2 DATABASE MANAGEMENT
      H.2.2 Physical Design
          Subjects: Access methods

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL

General Terms:
Design, Performance