Reasoning and identifying relevant matches for XML keyword search

ABSTRACT

Keyword search is a user-friendly mechanism for retrieving XML data in web and scientific applications. An intuitively compelling but vaguely defined goal is to identify matches to query keywords that are relevant to the user. However, it is hard to directly evaluate the relevance of query results due to the inherent ambiguity of search semantics. In this work, we investigate an axiomatic framework that includes two intuitive and non-trivial properties that an XML keyword search technique should ideally satisfy: monotonicity and consistency, with respect to data and query. This is the first work that reasons about keyword search strategies from a formal perspective.

Then we propose a novel semantics for identifying relevant matches, which, to the best of our knowledge, is the only existing algorithm that satisfies both properties. An efficient algorithm is designed for realizing this semantics. Extensive experimental studies have verified the intuition of the properties and shown the effectiveness of the proposed algorithm.

REFERENCES

• 1: Oracle berkeley db. http://www.oracle.com/technology/products/berkeley-db/index.html.
• 2: Timber project. http://www.eecs.umich.edu/db/timber/.
• 3: K. Arrow. Social Choice and Individual Values. 1951.
• 4: Michael Barg , Raymond K. Wong, Structural proximity searching for large collections of semi-structured data, Proceedings of the tenth international conference on Information and knowledge management, October 05-10, 2001, Atlanta, Georgia, USA [doi>10.1145/502585.502615]
• 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: 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]
• 7: Pierre Hansen , Fred S. Roberts, An impossibility result in axiomatic location theory, Mathematics of Operations Research, v.21 n.1, p.195-208, Feb. 1996 [doi>10.1287/moor.21.1.195]
• 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: V. Hristidis, Y. Papakonstantinou, and A. Balmin. Keyword Proximity Search on XML Graphs. In ICDE, 2003.
• 10: 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]
• 11: J. Kleinberg. An Impossibility Theorem for Clustering. In NIPS, 2002.
• 12: Georgia Koutrika , Alkis Simitsis , Yannis Ioannidis, Précis: The Essence of a Query Answer, Proceedings of the 22nd International Conference on Data Engineering, p.69, April 03-07, 2006 [doi>10.1109/ICDE.2006.114]
• 13: 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]
• 14: 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
• 15: 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]
• 16: Z. Liu and Y. Chen. Answering Keyword Queries on XML Using Materialized Views. In ICDE, 2008.
• 17: M. J. Osborne and A. Rubinstein. A Course in Game Theory. In MIT Press, 1994.
• 18: D. M. Pennock, E. Horvitz, and C. L. Giles. An Impossibility Theorem for Clustering. In AAAI, 2000.
• 19: 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]
• 20: V. Vesper. Let's Do Dewey. http://www.mtsu.edu/vvesper/dewey.html.
• 21: 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]

INDEX TERMS

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

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

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.4 Knowledge Representation Formalisms and Methods
          Subjects: Semantic networks
  I.7 DOCUMENT AND TEXT PROCESSING
      I.7.2 Document Preparation

          Nouns: XML

General Terms:
Algorithms, Design, Management, Performance