A novel method for the evaluation of Boolean query effectiveness across a wide operational range

ABSTRACT

Traditional methods for the system-oriented evaluation of Boolean IR system suffer from validity and reliability problems. Laboratory-based research neglects the searcher and studies suboptimal queries. Research on operational systems fails to make a distinction between searcher performance and system performance. This approach is neither capable of measuring performance at standard points of operation (e.g. across R0.0-R1.0).

A new laboratory-based evaluation method for Boolean IR systems is proposed. It is based on a controlled formulation of inclusive query plans, on an automatic conversion of query plans into elementary queries, and on combining elementary queries into optimal queries at standard points of operation. Major results of a large case experiment are reported. The validity, reliability, and efficiency of the method are considered in the light of empirical and analytical test data.

REFERENCES

• 1: Arnold, B.H. (1962). Logic and Boolean algebra. Eaglewood Cliffs: Prentice-Hall.
• 2: Nicholas J. Belkin , W. Bruce Croft, Retrieval techniques, Annual review of information science and technology, vol. 22, Elsevier Science Inc., New York, NY, 1987
• 3: David C. Blair , M. E. Maron, An evaluation of retrieval effectiveness for a full-text document-retrieval system, Communications of the ACM, v.28 n.3, p.289-299, March 1985 [doi>10.1145/3166.3197]
• 4: Chvtal, V. (1983). Linear Programming. New York: W.H. Freeman.
• 5: Cleverdon, C.W. (1967). The Cranfield tests on index language devices. Aslib Proceedings 19(6), 173-193.
• 6: Fidel, R. (1991). Searcher's Selection of Search Keys. Journal of the American Society for Information Science 42(7), 490-500, 501-514, 515-527.
• 7: Valery I. Frants , Jacob Shapiro , Vladimir G. Voiskunskii , Isak Taksa, Boolean search: current state and perspectives, Journal of the American Society for Information Science, v.50 n.1, p.86-95, Jan. 1999 [doi>10.1002/(SICI)1097-4571(1999)50:1<86::AID-ASI10>3.3.CO;2-Z]
• 8: Harman, D. (1993). The First Text Retrieval Conference (TREC-1). Gaithersburg: National Institute of Standards and Technology. (NIST Spec. Publ. 500-207).
• 9: Stephen P. Harter, Online Information Retrieval: Concepts, Principles, and Techniques, Academic Press, Inc., Orlando, FL, 1986
• 10: Harter, S.P. (1990). Search Term Combinations and Retrieval Overlap: A Proposed Methodology and Case Study. Journal of the American Society for Information Science 41(2), 132-146.
• 11: William R. Hersh , David H. Hickam, An evaluation of interactive Boolean and natural language searching with an online medical textbook, Journal of the American Society for Information Science, v.46 n.7, p.478-489, Aug. 1995 [doi>10.1002/(SICI)1097-4571(199508)46:7<478::AID-ASI2>3.0.CO;2-#]
• 12: Mirja Iivonen, Consistency in the selection of search concepts and search terms, Information Processing and Management: an International Journal, v.31 n.2, p.173-190, March/April 1995 [doi>10.1016/0306-4573(94)00062-8]
• 13: Ingwersen, P. & Willett, P. (1995). An Introduction to Algorithmic and Cognitive Approaches for Information Retrieval. Libri 450, 160-177.
• 14: Kalervo Järvelin , Jaana Kristensen , Timo Niemi , Eero Sormunen , Hiekki Keskustalo, A deductive data model for query expansion, Proceedings of the 19th annual international ACM SIGIR conference on Research and development in information retrieval, p.235-243, August 18-22, 1996, Zurich, Switzerland [doi>10.1145/243199.248146]
• 15: Lancaster, F.W. (1968). Information Retrieval Systems: Characteristics, Testing, and Evaluation. New York: John Wiley.
• 16: F. Wilfrid Lancaster , Amy J. Warner, Information Retrieval Today, Information Resources Press, Arlington, VA, 1993
• 17: Silvano Martello , Paolo Toth, Knapsack problems: algorithms and computer implementations, John Wiley & Sons, Inc., New York, NY, 1990
• 18: McKinin, E.J., Sievert, M.E., et al. (1991). The Medline Full-Text Project. Journal of the American Society for Information Science 42(4), 297-307.
• 19: Newell, A. (1968). Heuristic programming: Ill-structured problems. In: Arofonsky, J. (Ed.). Progress in Operations Research, Vol III, 360-414. New York.
• 20: Lee Anne H. Paris , Helen R. Tibbo, Freestyle vs. Boolean: a comparison of partial and exact match retrieval systems, Information Processing and Management: an International Journal, v.34 n.2-3, p.175-190, 1998 [doi>10.1016/S0306-4573(97)00065-4]
• 21: Salton, G. (1972). A new comparison between conventional indexing (MEDLARS) and automatic text processing (SMART). Journal of the American Society for Information Science 23(March-April), 75-84.
• 22: Gerard Salton, Another look at automatic text-retrieval systems, Communications of the ACM, v.29 n.7, p.648-656, July 1986 [doi>10.1145/6138.6149]
• 23: Gerard Salton , Michael J. McGill, Introduction to Modern Information Retrieval, McGraw-Hill, Inc., New York, NY, 1986
• 24: Tefko Saracevic, Evaluation of evaluation in information retrieval, Proceedings of the 18th annual international ACM SIGIR conference on Research and development in information retrieval, p.138-146, July 09-13, 1995, Seattle, Washington, United States [doi>10.1145/215206.215351]
• 25: Saracevic, T., Kantor. P. et al. (1988). A Study of Information Seeking and Retrieving. Journal of the American Society for Information Science 39(3), pp. 161- 176, 177-196, and 197-216.
• 26: Sormunen, E. (2000). A Method for measuring Wide Range Performance of Boolean Queries in Full-Text Databases. Doctoral Thesis. Tampere: University of Tampere. Acta Electronica Universitatis Tamperensis, ISBN: 951-44-4732-8, 231 p. URL: http://granum.uta.fi/pdf/951-44-4732-8.pdf.
• 27: Sormunen, E., Laaksonen, J., et al. (1998). The IR Game - A Tool for Rapid Query Analysis in Cross-Language IR Experiments. PRICAI '98 Workshop on Cross Language Issues in Artificial Intelligence. Singapore, Nov 22-24, 1998, p. 22-32.
• 28: Karen Sparck Jones, Information Retrieval Experiment, Butterworth-Heinemann, Newton, MA, 1981
• 29: Jean Tague-Sutcliffe, The pragmatics of information retrieval experimentation, revisited, Information Processing and Management: an International Journal, v.28 n.4, p.467-490, July-Aug. 1992 [doi>10.1016/0306-4573(92)90005-K]
• 30: 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

INDEX TERMS

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

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Query formulation; Retrieval models

General Terms:
Algorithms, Design, Experimentation, Human Factors, Performance, Reliability

Keywords:
evaluation (general), structured queries, test collections, testing methodology