Retrieving meaningful relaxed tightest fragments for XML keyword search

ABSTRACT

Adapting keyword search to XML data has been attractive recently, generalized as XML keyword search (XKS). One of its key tasks is to return the meaningful fragments as the result. [1] is the latest work following this trend, and it focuses on returning the fragments rooted at SLCA (Smallest LCA -- Lowest Common Ancestor) nodes. To guarantee that the fragments only contain interesting nodes, [1] proposes a contributor-based filtering mechanism in its MaxMatch algorithm. However, the filtering mechanism is not sufficient. It will commit the false positive problem (discarding interesting nodes) and the redundancy problem (keeping uninteresting nodes).

In this paper, our interest is to propose a framework of retrieving meaningful fragments rooted at not only the SLCA nodes, but all LCA nodes. We begin by introducing the concept of Relaxed Tightest Fragment (RTF) as the basic result type. Then we propose a new filtering mechanism to overcome those two problems in Max-Match. Its kernel is the concept of valid contributor, which helps to distinguish the interesting children of a node. The new filtering mechanism is then to prune the nodes in a RTF which are not valid contributors to their parents. Based on the valid contributor concept, our ValidRTF algorithm not only overcomes those two problems in MaxMatch, but also satisfies the axiomatic properties deduced in [1] that an XKS technique should satisfy. We compare ValidRTF with MaxMatch on real and synthetic XML data. The result verifies our claims, and shows the effectiveness of our valid-contributor-based filtering mechanism.

REFERENCES

• 1: Ziyang Liu , Yi Cher, Reasoning and identifying relevant matches for XML keyword search, Proceedings of the VLDB Endowment, v.1 n.1, August 2008 [doi>10.1145/1453856.1453956]
• 2: Igor Tatarinov , Stratis D. Viglas , Kevin Beyer , Jayavel Shanmugasundaram , Eugene Shekita , Chun Zhang, Storing and querying ordered XML using a relational database system, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin [doi>10.1145/564691.564715]
• 3: Daniela Florescu , Donald Kossmann , Ioana Manolescu, Integrating keyword search into XML query processing, Proceedings of the 9th international World Wide Web conference on Computer networks : the international journal of computer and telecommunications netowrking, p.119-135, June 2000, Amsterdam, The Netherlands
• 4: 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]
• 5: Sara Cohen , Jonathan Mamou , Yaron Kanza , Yehoshua Sagiv, XSEarch: a semantic search engine for XML, Proceedings of the 29th international conference on Very large data bases, p.45-56, September 09-12, 2003, Berlin, Germany
• 6: Yunyao Li , Cong Yu , H. V. Jagadish, Schema-free XQuery, Proceedings of the Thirtieth international conference on Very large data bases, p.72-83, August 31-September 03, 2004, Toronto, Canada
• 7: Yu Xu , Yannis Papakonstantinou, Efficient keyword search for smallest LCAs in XML databases, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland [doi>10.1145/1066157.1066217]
• 8: Vagelis Hristidis , Nick Koudas , Yannis Papakonstantinou , Divesh Srivastava, Keyword Proximity Search in XML Trees, IEEE Transactions on Knowledge and Data Engineering, v.18 n.4, p.525-539, April 2006 [doi>10.1109/TKDE.2006.61]
• 9: Chong Sun , Chee-Yong Chan , Amit K. Goenka, Multiway SLCA-based keyword search in XML data, Proceedings of the 16th international conference on World Wide Web, May 08-12, 2007, Banff, Alberta, Canada [doi>10.1145/1242572.1242713]
• 10: Ziyang Liu , Yi Chen, Identifying meaningful return information for XML keyword search, Proceedings of the 2007 ACM SIGMOD international conference on Management of data, June 11-14, 2007, Beijing, China [doi>10.1145/1247480.1247518]
• 11: Guoliang Li , Jianhua Feng , Jianyong Wang , Lizhu Zhou, Effective keyword search for valuable lcas over xml documents, Proceedings of the sixteenth ACM conference on Conference on information and knowledge management, November 06-10, 2007, Lisbon, Portugal [doi>10.1145/1321440.1321447]
• 12: Yu Xu , Yannis Papakonstantinou, Efficient LCA based keyword search in XML data, Proceedings of the 11th international conference on Extending database technology: Advances in database technology, March 25-29, 2008, Nantes, France [doi>10.1145/1353343.1353408]
• 13: Dov Harel , Robert Endre Tarjan, Fast algorithms for finding nearest common ancestors, SIAM Journal on Computing, v.13 n.2, p.338-355, May 1984 [doi>10.1137/0213024]
• 14: Baruch Schieber , Uzi Vishkin, On finding lowest common ancestors: simplification and parallelization, SIAM Journal on Computing, v.17 n.6, p.1253-1262, Dec. 1988 [doi>10.1137/0217079]
• 15: Richard Cole , Ramesh Hariharan, Dynamic LCA queries on trees, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.235-244, January 17-19, 1999, Baltimore, Maryland, United States
• 16: Michael A. Bender , Martín Farach-Colton , Giridhar Pemmasani , Steven Skiena , Pavel Sumazin, Lowest common ancestors in trees and directed acyclic graphs, Journal of Algorithms, v.57 n.2, p.75-94, November 2005 [doi>10.1016/j.jalgor.2005.08.001]
• 17: J. Xu, J. Lu, W. Wang, and B. Shi, "Effective keyword search in xml documents based on miu," in DASFAA, 2006.
• 18: Yu Xu , Yannis Papakonstantinou, Efficient LCA based keyword search in xml data, Proceedings of the sixteenth ACM conference on Conference on information and knowledge management, November 06-10, 2007, Lisbon, Portugal [doi>10.1145/1321440.1321597]
• 19: "http://www.cs.washington.edu/research/xmldatasets/."
• 20: "http://monetdb.cwi.nl/xml/."
• 21: "http://lucene.apache.org/."
• 22: "www.syger.com/jsc/docs/stopwords/english.htm."
• 23: Ricardo A. Baeza-Yates , Berthier Ribeiro-Neto, Modern Information Retrieval, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1999
• 24: Z. Liu and Y. Chen, "Answering keyword queries on xml using materialized views," in ICDE, 2008.
• 25: Yu Huang , Ziyang Liu , Yi Chen, Query biased snippet generation in XML search, Proceedings of the 2008 ACM SIGMOD international conference on Management of data, June 09-12, 2008, Vancouver, Canada [doi>10.1145/1376616.1376651]
• 26: Peter Buneman , Susan Davidson , Wenfei Fan , Carmem Hara , Wang-Chiew Tan, Keys for XML, Proceedings of the 10th international conference on World Wide Web, p.201-210, May 01-05, 2001, Hong Kong, Hong Kong [doi>10.1145/371920.371984]
• 27: Taurai Tapiwa Chinenyanga , Nicholas Kushmerick, Expressive retrieval from XML documents, Proceedings of the 24th annual international ACM SIGIR conference on Research and development in information retrieval, p.163-171, September 2001, New Orleans, Louisiana, United States [doi>10.1145/383952.383982]
• 28: D. Theodoratos and X. Wu, "An original semantics to keyword queries for xml using structural patterns," in DASFAA, 2007.
• 29: 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]
• 30: S. Amer-Yahia , C. Botev , J. Shanmugasundaram, Texquery: a full-text search extension to xquery, Proceedings of the 13th international conference on World Wide Web, May 17-20, 2004, New York, NY, USA [doi>10.1145/988672.988751]
• 31: E. Curtmola, S. Amer-Yahia, P. Brown, and M. Fernàndez, "Galatex: A conformant implementation of the xquery fulltext language," in XIME-P, 2005.
• 32: Martin Theobald , Ralf Schenkel , Gerhard Weikum, An efficient and versatile query engine for TopX search, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 33: Z. Bao, T. W. Ling, B. Chen, and J. Lu, "Effective xml keyword search with relevance oriented ranking," in ICDE, 2009.
• 34: Guoliang Li , Beng Chin Ooi , Jianhua Feng , Jianyong Wang , Lizhu Zhou, EASE: an effective 3-in-1 keyword search method for unstructured, semi-structured and structured data, Proceedings of the 2008 ACM SIGMOD international conference on Management of data, June 09-12, 2008, Vancouver, Canada [doi>10.1145/1376616.1376706]