Implementing ranking strategies using text signatures

ABSTRACT

Signature files provide an efficient access method for text in documents, but retrieval is usually limited to finding documents that contain a specified Boolean pattern of words. Effective retrieval requires that documents with similar meanings be found through a process of plausible inference. The simplest way of implementing this retrieval process is to rank documents in order of their probability of relevance. In this paper techniques are described for implementing probabilistic ranking strategies with sequential and bit-sliced signature tiles and the limitations of these implementations with regard to their effectiveness are pointed out. A detailed comparison is made between signature-based ranking techniques and ranking using term-based document representatives and inverted files. The comparison shows that term-based representations are at least competitive (in terms of efficiency) with signature files and, in some situations, superior.

REFERENCES

• 1: Nicholas J. Belkin , W. Bruce Croft, Retrieval techniques, Annual review of information science and technology, vol. 22, Elsevier Science Inc., New York, NY, 1987
• 2: BERTINO, E., GIBBS, S., RABITTI, F., THANOS, C., AND TSICHRITZIS, D. A multimedia document server. In Proceedings of the Advanced Database Symposium (Japan, Aug. 29-30), 1986.
• 3: Chris Buckley , Alan F. Lewit, Optimization of inverted vector searches, Proceedings of the 8th annual international ACM SIGIR conference on Research and development in information retrieval, p.97-110, June 05-07, 1985, Montreal, Quebec, Canada [doi>10.1145/253495.253515]
• 4: CHRISTODOULAKIS, S. AND FALOUTSOS, C. Design considerations for a message file server. IEEE Trans. Softw. Eng. SE-IO (1984), 201-210.
• 5: CROFT, W.B. Document representation in probabilistic models of information retrieval. J. Am. Soc. Inf. Sci. 32 (1981), 451-457.
• 6: W. Bruce Croft, Experiments with automatic text filing and retrieval in the office environment, ACM SIGIR Forum, v.16 n.4, p.2-9, Spring 1982 [doi>10.1145/1095450.1095451]
• 7: CROFT, W.B. Experiments with representation in a document retrieval system. Inf. Tech. 2 (1983), 1-21.
• 8: CROFT, W.B. A comparison of the cosine correlation and the modified probabilistic model. Inf. Tech. 2 (1984), 113-114.
• 9: CROFT, W.B. Boolean queries and term dependencies in probabilistic retrieval models. J. Am. Soc. Inf. Sci. 37 (1986), 71-77.
• 10: W. B. Croft , Thomas J. Parenty, A comparison of a network structure and a database system used for document retrieval, Information Systems, v.10 n.4, p.377-390, 1985 [doi>10.1016/0306-4379(85)90042-0]
• 11: W. B. Croft , R. Krovetz, Interactive retrieval office documents, Proceedings of the ACM SIGOIS and IEEECS TC-OA 1988 conference on Office information systems, p.228-235, March 23-25, 1988, Palo Alto, California, United States
• 12: J. Fagan, Automatic phrase indexing for document retrieval, Proceedings of the 10th annual international ACM SIGIR conference on Research and development in information retrieval, p.91-101, June 03-05, 1987, New Orleans, Louisiana, United States [doi>10.1145/42005.42016]
• 13: 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]
• 14: 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]
• 15: HARDING, A. F., LYNCH, M. F., AND WILLETT, P. Document retrieval using a serial bit string search. Inf. Process. Manage. 19 (1983), 1-8.
• 16: HARPER, D.J. Relevance feedback in document retrieval systems: An evaluation of probabilistic strategies. Ph.D. dissertation, Computer Laboratory, Cambridge Univ., Cambridge, England, 1980.
• 17: H. S. Heaps, Information Retrieval: Computational and Theoretical Aspects, Academic Press, Inc., Orlando, FL, 1978
• 18: PORTER, M.F. An algorithm for suffix stripping. In New models in probabilistic information retrieval. British Library Research and Development Report 5587, Cambridge Univ., Cambridge, England, 1980.
• 19: F. Rabitti , J. Zizka, Evaluation of access methods to text documents in office systems, Proc. of the third joint BCS and ACM symposium on Research and development in information retrieval, p.21-40, November 1984, King's College, Cambridge
• 20: ROBERTS, C.S. Partial match retrieval via the method of superimposed codes. In Proceedings IEEE 67 (1979), 1624-1642.
• 21: ROBERTSON, S.E. The probability ranking principle in IR. J. Doc. 33 (1977), 294-304.
• 22: SACKS-DAVIS, R., AND RAMAMOHANARAO, K. A two level superimposed coding scheme for partial match retrieval. Inf. Syst. 8 (1983), 273-280.
• 23: Gerard. Salton, Automatic Information Organization and Retrieval., McGraw Hill Text, 1968
• 24: Gerard Salton , Edward A. Fox , Harry Wu, Extended Boolean information retrieval, Communications of the ACM, v.26 n.11, p.1022-1036, Nov. 1983 [doi>10.1145/182.358466]
• 25: Alan F. Smeaton, Incorporating syntactic information into a document retrieval strategy: an investigation, Proceedings of the 9th annual international ACM SIGIR conference on Research and development in information retrieval, p.103-113, September 1986, Palazzo dei Congressi, Pisa, Italy [doi>10.1145/253168.253193]
• 26: A. F. Smeaton , C. J. van Rijsbergen, The nearest neighbour problem in information retrieval: an algorithm using upperbounds, Proceedings of the 4th annual international ACM SIGIR conference on Information storage and retrieval: theoretical issues in information retrieval, p.83-87, May 31-June 02, 1981, Oakland, California
• 27: SPARCK JONES, K. Automatic indexing. J. Doc. 30 {1974), 393-432.
• 28: SPARCK JONES, K. AND BATES, R. C,. Research on automatic indexing. British Library Research and Development Rep. 5464, Computer Laboratory, Cambridge Univ., Cambridge, England, 1977.
• 29: 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]
• 30: Harold S. Stone, Parallel querying of large databases: a case study, Computer, v.20 n.10, p.11-21, Oct. 1987 [doi>10.1109/MC.1987.1663384]
• 31: 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]
• 32: C. J. Van Rijsbergen, Information Retrieval, Butterworth-Heinemann, Newton, MA, 1979
• 33: VAN RIJSBERGEN, C.J. A non-classical logic for information retrieval. Comput. J. 29 (1986), 481-485.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.2 Information Storage
          Subjects: File organization

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.2 Physical Design
          Subjects: Access methods
  H.3 INFORMATION STORAGE AND RETRIEVAL
  H.4 INFORMATION SYSTEMS APPLICATIONS

General Terms:
Design, Performance