Shortest-substring retrieval and ranking

ABSTRACT

We present a model for arbitrary passage retrieval using Boolean queries. The model is applied to the task of ranking documents, or other structural elements, in the order of their expected relevance. Features such as phrase matching, truncation, and stemming integrate naturally into the model. Properties of Boolean algebra are obeyed, and the exact-match semantics of Boolean retrieval are preserved. Simple inverted-list file structures provide an efficient implementation. Retrieval effectiveness is comparable to that of standard ranking techniques. Since global statistics are not used, the method is of particular value in distributed environments. Since ranking is based on arbitrary passages, the structural elements to be ranked may be specified at query time and do not need to be restricted to predefined elements.

REFERENCES

• 1: James Allan, Relevance feedback with too much data, Proceedings of the 18th annual international ACM SIGIR conference on Research and development in information retrieval, p.337-343, July 09-13, 1995, Seattle, Washington, United States [doi>10.1145/215206.215380]
• 2: R. Attar , A. S. Fraenkel, Local Feedback in Full-Text Retrieval Systems, Journal of the ACM (JACM), v.24 n.3, p.397-417, July 1977 [doi>10.1145/322017.322021]
• 3: BOOKSTEIN, A. 1978. On the perils of merging Boolean and weighted retrieval systems. J. Am. Soc. Inf. Sci. 29, 3, 156-158.
• 4: BOOKSTEIN, n. 1980. Fuzzy requests: An approach to weighted Boolean searches. J. Am. Soc. Inf. Sci. 31, 4 (July), 240-247.
• 5: Everett H. Brenner, Beyond Boolean: New Approaches to Information Retrieval, NFAIS, 1996
• 6: BUELL, D. A. AND KRAFT, D. H. 1981. Threshold values and Boolean retrieval systems. Inf. Process. Manage. 17, 3, 127-136.
• 7: Forbes J. Burkowski, An algebra for hierarchically organized text-dominated databases, Information Processing and Management: an International Journal, v.28 n.3, p.333-348, 1992 [doi>10.1016/0306-4573(92)90079-F]
• 8: James P. Callan, Passage-level evidence in document retrieval, Proceedings of the 17th annual international ACM SIGIR conference on Research and development in information retrieval, p.302-310, July 03-06, 1994, Dublin, Ireland
• 9: James P. Callan , Zhihong Lu , W. Bruce Croft, Searching distributed collections with inference networks, Proceedings of the 18th annual international ACM SIGIR conference on Research and development in information retrieval, p.21-28, July 09-13, 1995, Seattle, Washington, United States [doi>10.1145/215206.215328]
• 10: CLARKE, C. L. A. AND CORMACK, G.V. 1996. Interactive substring retrieval. In Proceedings of the 5th Text Retrieval Conference (TREC-5, Gaithersburg, MD, Nov.), E. M. Voorhees and D. K. Harman, Eds. National Institute of Standards and Technology, Gaithersburg, MD, 267-277.
• 11: CLARKE, C. L. A., CORMACK, G. V., AND BURKOWSKI, F. J. 1994. Fast inverted indexes with on-line update. Tech. Rep. CS-94-40. Computer Science Dept., University of Waterloo, Waterloo, Canada.
• 12: CLARKE, C. L. A., CORMACK, G. V., AND BURKOWSKI, F. J. 1995a. An algebra for structured text search and a framework for its implementation. Comput. J. 38, 1, 43-56.
• 13: CLARKE, C. L. A., CORMACK, G. V., AND BURKOWSKI, F.J. 1995b. Schema-independent retrieval from heterogeneous structured text. In Proceedings of the 4th Annual Symposium on Document Analysis and Information Retrieval (Las Vegas, NV), 279-289.
• 14: CLARKE, C. L. A., CORMACK, G. V., AND BURKOWSKI, F.J. 1995c. Shortest substring ranking MultiText experiments for TREC-4. In Proceedings of the 4th Text Retrieval Conference (TREC-4, Washington, D.C., Nov.), D. K. Harman, Ed. National Institute of Standards and Technology, Gaithersburg, MD, 295-304.
• 15: William S. Cooper, Getting beyond Boole, Information Processing and Management: an International Journal, v.24 n.3, p.243-248, May 1988 [doi>10.1016/0306-4573(88)90091-X]
• 16: CORMACK, G. V., CLARKE, C. L. A., PALMER, C. R., AND TO, S. S.-L. 1997. Passage based refinement. In Proceedings of the 6th Text Retreival Conference (TREC-6, Nov.), E. Voorhees and D. Harman, Eds. 303-319.
• 17: CORMACK, G., PALMER, C., VAN BIESBROUCK, M., AND CLARKE, C. 1998. Deriving very short queries for high precision and recall. In Proceedings of the 7th Text Retreival Conference (TREC-7),
• 18: Warren R. Greiff , W. Bruce Croft , Howard Turtle, Computationally tractable probabilistic modeling of Boolean operators, Proceedings of the 20th annual international ACM SIGIR conference on Research and development in information retrieval, p.119-128, July 27-31, 1997, Philadelphia, Pennsylvania, United States
• 19: HARMAN, D. K., Ed. 1995. Proceedings of the 4th Text Retrieval Conference. (TREC-4, Washington, D.C., Nov.). National Institute of Standards and Technology, Gaithersburg, MD.
• 20: HAWKING, D. AND THISTLEWAITE, P. 1995. Proximity operators--So near and yet so far. In Proceedings of the 4th Text Retrieval Conference (TREC-4, Washington, D.C., Nov.), D. K. Harman, Ed. National Institute of Standards and Technology, Gaithersburg, MD, 131-143.
• 21: HAWKING, D. AND THISTLEWAITE, P. 1996. Relevance weighting using distance between term occurrences. Tech. Rep. TR-CS-96-08. Department of Computer Science, Australian National Univ., Canberra, Australia. Available via http://cs.anu.edu.au/techreports/1996/ index.html.
• 22: HAWKING, D. AND THISTLEWAITE, P. 1997. Overview of the TREC-6 very large collection track. In Proceedings of the 6th Text Retreival Conference (TREC-6, Nov.), E. Voorhees and D. Harman, Eds.
• 23: HAWKING, D., CRASWELL, N., AND THISTLEWAITE, P. 1998. Overview of TREC-7 very large collection track. In Proceedings of the 7th Text Retrieval Conference (TREC-7),
• 24: HEARST, M.A. 1996. Improving full-text precision on short queries using simple constraints. In Proceedings of the 5th Annual Symposium on Document Analysis and Information Retrieval (Las Vegas, NV, Apr.),
• 25: Marti A. Hearst , Christian Plaunt, Subtopic structuring for full-length document access, Proceedings of the 16th annual international ACM SIGIR conference on Research and development in information retrieval, p.59-68, June 27-July 01, 1993, Pittsburgh, Pennsylvania, United States [doi>10.1145/160688.160695]
• 26: JING, Y. AND CROFT, W. B. 1994. An association thesaurus for information retrieval. In Proceedings of the Intelligent Multimedia Information Retrieval Systems (RIAO '94, New York, NY), 146-160.
• 27: Marcin Kaszkiel , Justin Zobel, Passage retrieval revisited, Proceedings of the 20th annual international ACM SIGIR conference on Research and development in information retrieval, p.178-185, July 27-31, 1997, Philadelphia, Pennsylvania, United States
• 28: E. Michael Keen, The use of term position devices in ranked output experiments, Journal of Documentation, v.47 n.1, p.1-22, March 1991 [doi>10.1108/eb026869]
• 29: E. Michael Keen, Some aspects of proximity searching in text retrieval systems, Journal of Information Science, v.18 n.2, p.89-98, 1992 [doi>10.1177/016555159201800202]
• 30: E. Michael Keen, Term position ranking: some new test results, Proceedings of the 15th annual international ACM SIGIR conference on Research and development in information retrieval, p.66-76, June 21-24, 1992, Copenhagen, Denmark [doi>10.1145/133160.133179]
• 31: KERRE, E. E., ZENNER, R. B. R. C., AND DE CALUWE, R. M. M. 1986. The use of fuzzy set theory in information retrieval and databases: A survey. J. Am. Soc. Inf. Sci. 37, 5 (Sept.), 341-345.
• 32: Myoung Ho Kim , Joon Ho Lee , Yoon Joon Lee, Analysis of fuzzy operators for high quality information retrieval, Information Processing Letters, v.46 n.5, p.251-256, July 9, 1993 [doi>10.1016/0020-0190(93)90104-H]
• 33: KNAUS, D., MITTENDORF, E., SCH UBLE, P., AND SHERIDAN, P. 1995. Highlighting relevant passages for users of the interactive SPIDER retrieval system. In Proceedings of the 4th Text Retrieval Conference (TREC-4, Washington, D.C., Nov.), D. K. Harman, Ed. National Institute of Standards and Technology, Gaithersburg, MD.
• 34: Joon Ho Lee, Properties of extended Boolean models in information retrieval, Proceedings of the 17th annual international ACM SIGIR conference on Research and development in information retrieval, p.182-190, July 03-06, 1994, Dublin, Ireland
• 35: Joon Ho Lee , Won Yong Kin , Myoung Ho Kim , Yoon Joon Lee, On the evaluation of Boolean operators in the extended Boolean retrieval framework, Proceedings of the 16th annual international ACM SIGIR conference on Research and development in information retrieval, p.291-297, June 27-July 01, 1993, Pittsburgh, Pennsylvania, United States [doi>10.1145/160688.160741]
• 36: Michael Lesk, Practical digital libraries: books, bytes, and bucks, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1997
• 37: Shih-Hao Li , Peter B. Danzig, Boolean Similarity Measures for Resource Discovery, IEEE Transactions on Knowledge and Data Engineering, v.9 n.6, p.863-876, November 1997 [doi>10.1109/69.649313]
• 38: MACLANE, S. AND BIRKOFF, G. 1967. Algebra. Macmillan, New York, NY.
• 39: MITRA, M., BUCKLEY, C., SINGHAL, A., AND CARDIE, C. 1997. An analysis of statistical and syntactic phrases. In Proceedings of the 1997 Intelligent Multimedia Information Retrieval Systems Conference (RIAO '97, Montreal, Canada, June), 200-214.
• 40: Alistair Moffat , Justin Zobel, Self-indexing inverted files for fast text retrieval, ACM Transactions on Information Systems (TOIS), v.14 n.4, p.349-379, Oct. 1996 [doi>10.1145/237496.237497]
• 41: NOREAULT, T., KOLL, M., AND MCGILL, M. g. 1977. Automatic ranked output from Boolean searches in SIRE. J. Am. Soc. Inf. Sci. 28, 6, 333-339.
• 42: RADECKI, T. 1982. Reducing the perils of merging Boolean and weighted retrieval systems. J. Doc. 38, 1 (Sept.), 207-211.
• 43: ROBERTSON, S. E. 1978. On the nature of fuzz: A diatribe. J. Am. Soc. Inf. Sci. 29, 6, 304-307.
• 44: S. E. Robertson , S. Walker, Some simple effective approximations to the 2-Poisson model for probabilistic weighted retrieval, Proceedings of the 17th annual international ACM SIGIR conference on Research and development in information retrieval, p.232-241, July 03-06, 1994, Dublin, Ireland
• 45: ROBERTSON, S. E., WALKER, S., JONES, S., HANCOCK-BEAULIEU, M. M., AND GATFORD, M. 1994. Okapi at TREC-3. In Proceedings of the 3rd Text Retrieval Conference (TREC-3, Nov.), 109-126.
• 46: R. Rousseau, Extended boolean retrieval: a heuristic approach?, Proceedings of the 13th annual international ACM SIGIR conference on Research and development in information retrieval, p.495-508, September 05-07, 1990, Brussels, Belgium [doi>10.1145/96749.98255]
• 47: Gerard Salton , Michael J. McGill, Introduction to Modern Information Retrieval, McGraw-Hill, Inc., New York, NY, 1986
• 48: Gerard Salton , J. Allan , Chris Buckley, Approaches to passage retrieval in full text information systems, Proceedings of the 16th annual international ACM SIGIR conference on Research and development in information retrieval, p.49-58, June 27-July 01, 1993, Pittsburgh, Pennsylvania, United States [doi>10.1145/160688.160693]
• 49: 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]
• 50: SCHIETTECATTE, F. AND FLORANCE, V. 1995. Document retrieval using the MPS information server. In Proceedings of the 4th Text Retrieval Conference (TREC-4, Washington, D.C., Nov.), D. K. Harman, Ed. National Institute of Standards and Technology, Gaithersburg, MD, 401-419.
• 51: TAHANI, V. 1978. A fuzzy model of document retrieval systems. Inf. Process. Manage. 12, 3, 177-187.
• 52: TEASDALE, S. 1920. Flame and Shadow. Macmillan, New York, NY.
• 53: Spencer W. Thomas , Ken Alexander , Kevin Guthrie, Technology Choices for the JSTOR Online Archive, Computer, v.32 n.2, p.60-65, February 1999 [doi>10.1109/2.745721]
• 54: Howard Turtle, Natural language vs. Boolean query evaluation: a comparison of retrieval performance, Proceedings of the 17th annual international ACM SIGIR conference on Research and development in information retrieval, p.212-220, July 03-06, 1994, Dublin, Ireland
• 55: Howard Turtle , James Flood, Query evaluation: strategies and optimizations, Information Processing and Management: an International Journal, v.31 n.6, p.831-850, Nov. 1995 [doi>10.1016/0306-4573(95)00020-H]
• 56: Howard R. Turtle , W. Bruce Croft, A comparison of text retrieval models, The Computer Journal, v.35 n.3, p.279-290, June 1992 [doi>10.1093/comjnl/35.3.279]
• 57: WALLER, W. G. AND KRAFT, D. H. 1979. A mathematical model for a weighted Boolean retrieval system. Inf. Process. Manage. 15, 5, 235-245.
• 58: Ross Wilkinson, Effective retrieval of structured documents, Proceedings of the 17th annual international ACM SIGIR conference on Research and development in information retrieval, p.311-317, July 03-06, 1994, Dublin, Ireland
• 59: WILKINSON, R. AND ZOBEL, g. 1994. Comparison of fragmentation schemes for document retrieval. In Proceedings of the 3rd Text Retrieval Conference (TREC-3, Nov.), 81-84.
• 60: Jinxi Xu , W. Bruce Croft, Query expansion using local and global document analysis, Proceedings of the 19th annual international ACM SIGIR conference on Research and development in information retrieval, p.4-11, August 18-22, 1996, Zurich, Switzerland [doi>10.1145/243199.243202]

INDEX TERMS

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

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.4 Systems and Software
          Subjects: Performance evaluation (efficiency and effectiveness)

General Terms:
Algorithms, Performance

Keywords:
Boolean retrieval model, passage retrieval, relevance ranking