Optimal weight assignment for signature generation

ABSTRACT

Previous work on superimposed coding has been characterized by two aspects. First, it is generally assumed that signatures are generated from logical text blocks of the same size; that is, each block contains the same number of unique terms after stopword and duplicate removal. We call this approach the fixed-size block (FSB) method, since each text block has the same size, as measured by the number of unique terms contained in it. Second, with only a few exceptions [6,7,8,9,17], most previous work has assumed that each term in the text contributes the same number of ones to the signature (i.e., the weight of the term signatures is fixed). The main objective of this paper is to derive an optimal weight assignment that assigns weights to document terms according to their occurrence and query frequencies in order to minimize the false-drop probability. The optimal scheme can account for both uniform and nonuniform occurence and query frequencies, and the signature generation method is still based on hashing rather than on table lookup. Furthermore, a new way of generating signatures, the fixed-weight block (FWB) method, is introduced. FWB controls the weight of every signature to a constant, whereas in FSB, only the expected signature weight is constant. We have shown that FWB has a lower false-drop probability than that of the FSB method, but its storage overhead is slightly higher. Other advantages of FWB are that the optimal weight assignment can be obtained analytically without making unrealistic assumptions and that the formula for computing the term signature weights is simple and efficient.

REFERENCES

• 1: APOSTOL, T M. Mathematical AnalysLs. 2nd ed Addison-Wesley, Reading, Mass., 1974.
• 2: W. W. Chang , H. J. Schek, A signature access method for the Starburst database system, Proceedings of the 15th international conference on Very large data bases, p.145-153, July 1989, Amsterdam, The Netherlands
• 3: 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]
• 4: C. Faloutsos, Signature-based text retrieval methods: a survey, Data Engineering, v.13 n.1, p.25-32, Mar. 1990
• 5: 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]
• 6: FALOUTSOS, C., AND CHRISTODOULAKIS, S. Design of a signature file method that accounts for non-uniform occurrence and query frequencies. In Proceedings of the 11th International Conference on Very Large Data Bases (Stockholm, Aug. 1985). VLDB Endowment, 1985, pp. 165-170.
• 7: 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]
• 8: 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]
• 9: KENT, A., RAMAMOHANARAO, K., AND SACKS-DAviS, R. A signature file scheme based on multiple organizations for indexing very large databases. J. Am. Soc. Inf. Sci. 41, 7 (1990), 508-534.
• 10: KIM, Y. M., LEE, D. L., AND GAURAV, P. Efficient search methods for signature files. Submitted for publication.
• 11: 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
• 12: Dik Lun Lee , Chun-Wu Leng, Partitioned signature files: design issues and performance evaluation, ACM Transactions on Information Systems (TOIS), v.7 n.2, p.158-180, April 1989 [doi>10.1145/65935.65937]
• 13: Dik Lun Lee , Chun-Wu Leng, A Partitioned Signature File Structure for Multiattribute and Text Retrieval, Proceedings of the Sixth International Conference on Data Engineering, p.389-397, February 05-09, 1990
• 14: 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]
• 15: ROBERTS, C.S. Partial-match retrieval via method of superimposed codes. Proc. 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: Gerard Salton , Michael J. McGill, Introduction to Modern Information Retrieval, McGraw-Hill, Inc., New York, NY, 1986
• 19: 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]
• 20: STIASSNY, S. Mathematical analysis of various superimposed coding methods. Am. Doc. 11, 2 (Feb. 1960), 155-169.
• 21: 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.2 Physical Design
          Subjects: Access methods
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.6 Library Automation

  I. Computing Methodologies
  I.7 DOCUMENT AND TEXT PROCESSING
      I.7.1 Document and Text Editing

General Terms:
Design, Performance

Keywords:
access method, coding methods, document retrieval, information retrieval, optimization, signature file, superimposed coding, text retrieval