Estimating accesses in partitioned signature file organizations

ABSTRACT

We show that performance of some basic methods for the partitioning of signature files, namely Quick Filter and Fixed Prefix, can be easily evaluated by means of a closed formula. The approximation is based on well-known results from probability theory, and, as shown by simulations, introduces no appreciable errors when compared with the exact, cumbersome formulas used so far. Furthermore, we prove that the exact formulas for the two methods coincide. Although this does not imply that the two methods behave in the same way, it sheds light on the way they could be compared.

REFERENCES

• 1: 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]
• 2: FELLER, W An Introductwn to Probabd~ty Theory and Its Apphcations Vol. 1, 3rd edition, Wiley~ New York, 1968.
• 3: Fabio Grandi , Paolo Tiberio , Pavel Zezula, Frame-sliced partitioned parallel signature files, Proceedings of the 15th annual international ACM SIGIR conference on Research and development in information retrieval, p.286-287, June 21-24, 1992, Copenhagen, Denmark [doi>10.1145/133160.133211]
• 4: 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
• 5: 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]
• 6: LITWIN, W. Linear hashing: A new tool for files and table addressing In Proceedtngs of the 6th VLDB International Conference (Montreal, 1980), 212-223.
• 7: F. Rabitti , P. Zezula, A dynamic signature technique for multimedia databases, Proceedings of the 13th annual international ACM SIGIR conference on Research and development in information retrieval, p.193-210, September 05-07, 1990, Brussels, Belgium [doi>10.1145/96749.98223]
• 8: ZEZULA, P. Linear hashing for signature files. In Network Informatlon Processing Systems. Elsevier Science (North-Holland) 1989, 243 250.
• 9: P. Zezula , F. Rabitti , P. Tiberio, Dynamic partitioning of signature files, ACM Transactions on Information Systems (TOIS), v.9 n.4, p.336-367, Oct. 1991 [doi>10.1145/119311.119313]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.2 Physical Design
          Subjects: Access methods

Additional Classification:
  E. Data
  E.5 FILES
      Subjects: Organization/structure

  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.2 Information Storage
          Subjects: File organization

General Terms:
Design, Performance

Keywords:
access method, information retrieval, performance evaluation, superimposed coding