Content and structure in indexing and ranking XML

ABSTRACT

Rooted in electronic publishing, XML is now widely used for modelling and storing structured text documents. Especially in the WWW, retrieval of XML documents is most useful in combination with a relevance-based ranking of the query result. Index structures with ranking support are therefore needed for fast access to relevant parts of large document collections. This paper proposes a classification scheme for both XML ranking models and index structures, allowing to determine which index suits which ranking model. An analysis reveals that ranking parameters related to both the content and structure of the data are poorly supported by most known XML indices. The IR-CADG index, owing to its tight integration of content and structure, supports various XML ranking models in a very efficient retrieval process. Experiments show that it outperforms separate content/structure indexing by more than two orders of magnitude for large corpora of several hundred MB.

REFERENCES

• 1: Yangjun Chen , Karl Aberer, Combining Pat-Trees and Signature Files for Query Evaluation in Document Databases, Proceedings of the 10th International Conference on Database and Expert Systems Applications, p.473-484, August 30-September 03, 1999
• 2: Brian Cooper , Neal Sample , Michael J. Franklin , Gisli R. Hjaltason , Moshe Shadmon, A Fast Index for Semistructured Data, Proceedings of the 27th International Conference on Very Large Data Bases, p.341-350, September 11-14, 2001
• 3: 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]
• 4: Roy Goldman , Jennifer Widom, DataGuides: Enabling Query Formulation and Optimization in Semistructured Databases, Proceedings of the 23rd International Conference on Very Large Data Bases, p.436-445, August 25-29, 1997
• 5: Raghav Kaushik , Rajasekar Krishnamurthy , Jeffrey F. Naughton , Raghu Ramakrishnan, On the integration of structure indexes and inverted lists, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007656]
• 6: H. Meuss, K. Schulz, and F. Bry. Visual Querying and Exploration of Large Answers in XML DBs with X2. In Proc. 19th Int. Conf. on Data Engineering, 2003.
• 7: Tova Milo , Dan Suciu, Index Structures for Path Expressions, Proceeding of the 7th International Conference on Database Theory, p.277-295, January 10-12, 1999
• 8: Gerard Salton , Michael J. McGill, Introduction to Modern Information Retrieval, McGraw-Hill, Inc., New York, NY, 1986
• 9: K. Sauvagnat and M. Boughanem. XFIRM: A Flexible IR Model for Indexing and Searching XML Documents. Poster at 26th Europ. Conf. on IR, 2004.
• 10: T. Schlieder. Similarity Search in XML Data using Cost-Based Query Transformations. In Proc. 4th Int. Workshop on the Web and Databases, 2001.
• 11: Torsten Schlieder , Holger Meuss, Querying and ranking XML documents, Journal of the American Society for Information Science and Technology, v.53 n.6, p.489-503, May, 2002 [doi>10.1002/asi.10060]
• 12: Dongwook Shin , Hyuncheol Jang , Honglan Jin, BUS: an effective indexing and retrieval scheme in structured documents, Proceedings of the third ACM conference on Digital libraries, p.235-243, June 23-26, 1998, Pittsburgh, Pennsylvania, United States [doi>10.1145/276675.276702]
• 13: Anja Theobald , Gerhard Weikum, The Index-Based XXL Search Engine for Querying XML Data with Relevance Ranking, Proceedings of the 8th International Conference on Extending Database Technology: Advances in Database Technology, p.477-495, March 25-27, 2002
• 14: F. Weigel, H. Meuss, F. Bry, and K. U. Schulz. Content-Aware DataGuides: Interleaving IR and DB Indexing Techniques for Efficient Retrieval of Textual XML Data. In Proc. 26th Europ. Conf. on IR, 2004.
• 15: Jens E. Wolff , Holger Flörke , Armin B. Cremers, Searching and Browsing Collections of Structural Information, Proceedings of the IEEE Advances in Digital Libraries 2000, p.141, May 22-24, 2000
• 16: H. Zargayouna and S. Salotti. SemIndex: A Model of Semantic Indexing on XML Documents. Poster at 26th Europ. Conf. on IR, 2004.