Structural relevance: a common basis for the evaluation of structured document retrieval

ABSTRACT

This paper presents a unified framework for the evaluation of a range of structured document retrieval (SDR) approaches and tasks. The framework is based on a model of tree retrieval, evaluated using a novel extension of the Structural elevance (SR) measure. The measure replaces the assumption of independence in traditional information retrieval (IR) with a notion of redundancy that takes into account the user navigation inside documents while seeking relevant information. Unlike existing metrics for SDR, our proposed framework does not require the computation of an ideal ranking which has, thus far, prevented the practical application of such measures. Instead, SR builds on a Markovian model of user navigation that can be estimated through the use of structural summaries. The results of this paper (supported by experimental validation using INEX data) show that SR defined over a tree retrieval model can provide a common basis for the evaluation of SDR approaches across various structured search tasks.

REFERENCES

• 1: M. S. Ali, M. P. Consens, and M. Lalmas. Structural Relevance in XML Retrieval Evaluation. In SIGIR 2007 Workshop on Focused Retrieval, pages 1--8, 2007.
• 2: S. Amer-Yahia et al. XQuery 1.0 and XPath 2.0 Full-Text,W3C Working Draft 18 May 2007, 2007.
• 3: Ricardo Baeza-Yates , Gonzalo Navarro, Integrating contents and structure in text retrieval, ACM SIGMOD Record, v.25 n.1, p.67-79, March 1996 [doi>10.1145/381854.381890]
• 4: David Carmel , Yoelle S. Maarek , Matan Mandelbrod , Yosi Mass , Aya Soffer, Searching XML documents via XML fragments, Proceedings of the 26th annual international ACM SIGIR conference on Research and development in informaion retrieval, July 28-August 01, 2003, Toronto, Canada [doi>10.1145/860435.860464]
• 5: Charles L. A. Clarke, Controlling overlap in content-oriented XML retrieval, Proceedings of the 28th annual international ACM SIGIR conference on Research and development in information retrieval, August 15-19, 2005, Salvador, Brazil [doi>10.1145/1076034.1076089]
• 6: C. Clarke. Range results in XML retrieval. In INEX 2005, volume LNCS(3493), pages 4--5, 2006.
• 7: M. P. Consens, F. Rizzolo, and A. A. Vaisman. AxPRE Summaries: Exploring the (Semi-)Structure of XML Web Collections. In ICDE 2008, pages 1519--1521. IEEE, 2008.
• 8: A. Doucet, L. Aunimo, M. Lehtonen, and R. Petit. Accurate retrieval of XML document fragments using EXTIRP. In INEX 2003, 2004.
• 9: Cynthia Dwork , Ravi Kumar , Moni Naor , D. Sivakumar, Rank aggregation methods for the Web, Proceedings of the 10th international conference on World Wide Web, p.613-622, May 01-05, 2001, Hong Kong, Hong Kong [doi>10.1145/371920.372165]
• 10: Norbert Fuhr , Kai Großjohann, XIRQL: a query language for information retrieval in XML documents, Proceedings of the 24th annual international ACM SIGIR conference on Research and development in information retrieval, p.172-180, September 2001, New Orleans, Louisiana, United States [doi>10.1145/383952.383985]
• 11: Lin Guo , Feng Shao , Chavdar Botev , Jayavel Shanmugasundaram, XRANK: ranked keyword search over XML documents, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872762]
• 12: V. Hristidis, Y. Papakonstantinou, and A. Balmin. Keyword proximity search on XML graphs. ICDE 2003, pages 367--395, 2003.
• 13: D. Jenkinson and A. Trotman. Focused access to XML documents. In INEX 2007, 2008.
• 14: G. Kazai. Choosing an Ideal Recall-Base for the Evaluation of the Focused Task: Sensitivity Analysis of the XCG Evaluation Measures. In INEX 2006, pages 35--44, 2007.
• 15: Gabriella Kazai , Mounia Lalmas, eXtended cumulated gain measures for the evaluation of content-oriented XML retrieval, ACM Transactions on Information Systems (TOIS), v.24 n.4, p.503-542, October 2006 [doi>10.1145/1185877.1185883]
• 16: Gabriella Kazai , Mounia Lalmas , Thomas Rölleke, Focussed Structured Document Retrieval, Proceedings of the 9th International Symposium on String Processing and Information Retrieval, p.241-247, September 11-13, 2002
• 17: G. Kazai, B. Piwowarski, and S. Robertson. Effort-precision and gain-recall based on a probabilistic navigation model. In ICTIR 2007, 2007.
• 18: Benjamin Piwowarski , Georges Dupret, Evaluation in (XML) information retrieval: expected precision-recall with user modelling (EPRUM), Proceedings of the 29th annual international ACM SIGIR conference on Research and development in information retrieval, August 06-11, 2006, Seattle, Washington, USA [doi>10.1145/1148170.1148218]
• 19: B. Piwowarski and P. Gallinari. Expected ratio of relevant units: A measure for structured document information retrieval. In INEX 2003, pages 158--166, April 2004.
• 20: B. Piwowarski , P. Gallinari , G. Dupret, Precision recall with user modeling (PRUM): Application to structured information retrieval, ACM Transactions on Information Systems (TOIS), v.25 n.1, p.1-es, February 2007 [doi>10.1145/1198296.1198297]
• 21: B. Piwowarski, A. Trotman, and M. Lalmas. Sound and Complete Relevance Assessment for XML Retrieval. ACM Trans. Inf. Syst., 2008 (To Appear).
• 22: Vijay Raghavan , Peter Bollmann , Gwang S. Jung, A critical investigation of recall and precision as measures of retrieval system performance, ACM Transactions on Information Systems (TOIS), v.7 n.3, p.205-229, July 1989 [doi>10.1145/65943.65945]
• 23: Sheldon M. Ross, Introduction to Probability Models, Ninth Edition, Academic Press, Inc., Orlando, FL, 2006
• 24: Anja Theobald , Gerhard Weikum, The XXL search engine: ranked retrieval of XML data using indexes and ontologies, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin [doi>10.1145/564691.564768]
• 25: A. Trotman. Wanted: Element retrieval users. In INEX 2005, volume LNCS(3493), pages 58--64, 2006.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval

General Terms:
Measurement

Keywords:
structural relevance, xml