Identifying meaningful return information for XML keyword search

ABSTRACT

Keyword search enables web users to easily access XML data without the need to learn a structured query language and to study possibly complex data schemas. Existing work has addressed the problem of selecting qualified data nodes that match keywords and connecting them in a meaningful way, in the spirit of inferring a where clause in XQuery. However, how to infer the return clause for keyword search is an open problem.

To address this challenge, we present an XML keyword search engine, XSeek, to infer the semantics of the search and identify return nodes effectively. XSeek recognizes possible entities and attributes inherently represented in the data. It also distinguishes between search predicates and return specifications in the keywords. Then based on the analysis of both XML data structures and keyword match patterns, XSeek generates return nodes. Extensive experimental studies show the effectiveness of XSeek.

REFERENCES

• 1: XQuery 1.0: An XML query language, June 2001. http://www.w3.org/XML/Query.
• 2: S. Agrawal, S. Chaudhuri, and G. Das. DBXplorer: A System for Keyword-Based Search over Relational Databases. In Proceedings of ICDE, pages 5--16, 2002.
• 3: S. Amer-Yahia , C. Botev , J. Dörre , J. Shanmugasundaram, XQuery full-text extensions explained, IBM Systems Journal, v.45 n.2, p.335-351, January 2006
• 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: G. Bhalotia, C. Nakhe, A. Hulgeri, S. Chakrabarti, and S. Sudarshan. Keyword Searching and Browsing in Databases using BANKS. In ICDE, 2002.
• 6: D. Carmel, Y. Maarek, Y. Mass, N. Efraty, and G. Landau. An extension of the vector space model for querying xml documents via xml fragments. In ACM SIGIR 2002: Workshop on XML and Information Retrieval, 2002.
• 7: J. Clark and S. DeRose. XML Path language (XPath) 1.0, November 1999. http://www.w3.org/TR/xpath.
• 8: S. Cohen, J. Mamou, Y. Kanza, and Y. Sagiv. XSEarch: A semantic Search Engine for XML, 2003.
• 9: Alin Deutsch , Mary Fernandez , Dan Suciu, Storing semistructured data with STORED, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.431-442, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
• 10: D. Florescu, D. Kossmann, and I. Manolescu. Integrating Keyword Search into XML Query Processing. Computer Networks( Amsterdam, Netherlands: 1999), 33(1--6):119--135, 2000.
• 11: 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]
• 12: 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]
• 13: 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]
• 14: V. Hristidis and Y. Papakonstantinou. Discover: Keyword search in relational databases. In Procs. VLDB, 2002.
• 15: V. Hristidis, Y. Papakonstantinou, and A. Balmin. Keyword Proximity Search on XML Graphs, 2003. In ICDE.
• 16: Georgia Koutrika , Alkis Simitsis , Yannis Ioannidis, Précis: The Essence of a Query Answer, Proceedings of the 22nd International Conference on Data Engineering (ICDE'06), p.69, April 03-07, 2006 [doi>10.1109/ICDE.2006.114]
• 17: Y. Li, C. Yu, and H. V. Jagadish. Schema-Free XQuery. In VLDB, 2004.
• 18: Fang Liu , Clement Yu , Weiyi Meng , Abdur Chowdhury, Effective keyword search in relational databases, Proceedings of the 2006 ACM SIGMOD international conference on Management of data, June 27-29, 2006, Chicago, IL, USA [doi>10.1145/1142473.1142536]
• 19: V. Vesper. Let's Do Dewey. http://www.mtsu.edu/vvesper/dewey.html.
• 20: Extensible markup language (xml) 1.0, 2004. http://www.w3.org/TR/REC-xml/.
• 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]
• 22: Cong Yu , H. V. Jagadish, Schema summarization, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea

INDEX TERMS

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

General Terms:
Algorithms, Design

Keywords:
XML, keyword search