XKMis: effective and efficient keyword search in XML databases

ABSTRACT

We present XKMis, a system for keyword search in XML documents. Unlike previous work, our method is not based on the lowest common ancestor (LCA) or its variant, rather we divide the nodes into meaningful and self-containing information segments, called minimal information segments (MISs), and return MIS-subtrees which consist of MISs that are logically connected by the keywords. The MIS-subtrees are closer to what the user wants. The MIS-subtrees enable us to use the region code of XML trees to develop an algorithm for the search which is more efficient especially for large XML trees. We report our experiment results, which verify the better effectiveness and efficiency of our system.

REFERENCES

• 1: http://www.cs.washington.edu/research/xmldatasets.
• 2: http://www.oracle.com/database/berkeley-db/.
• 3: http://xmlsoft.org/.
• 4: N. Bruno, N. Koudas, and D. Srivastava. Holistic twig joins: optimal XML pattern matching. In SIGMOD Conference, pages 310--321, 2002.
• 5: L. Guo, F. Shao, C. Botev, and J. Shanmugasundaram. Xrank: Ranked keyword search over XML documents. In SIGMOD Conference, pages 16--27, 2003.
• 6: V. Hristidis, L. Gravano, and Y. Papakonstantinou. Efficient ir-style keyword search over relational databases. In VLDB, pages 850--861, 2003.
• 7: V. Hristidis, N. Koudas, Y. Papakonstantinou, and D. Srivastava. Keyword proximity search in XML trees. IEEE Trans. Knowl. Data Eng., 18(4):525--539, 2006.
• 8: G. Li, J. Feng, J. Wang, and L. Zhou. Effective keyword search for valuable lcas over XML documents. In CIKM, pages 31--40, 2007.
• 9: Y. Li, C. Yu, and H. V. Jagadish. Schema-free XQuery. In VLDB, pages 72--83, 2004.
• 10: Z. Liu and Y. Chen. Identifying meaningful return information for XML keyword search. In SIGMOD Conference, pages 329--340, 2007.
• 11: Z. Liu and Y. Chen. Reasoning and identifying relevant matches for xml keyword search. PVLDB, 1(1):921--932, 2008.
• 12: J. Xu, J. Lu, W. Wang, and B. Shi. Effective keyword search in XML documents based on MIU. In DASFAA, pages 702--716, 2006.
• 13: Y. Xu and Y. Papakonstantinou. Efficient keyword search for smallest lcas in XML databases. In SIGMOD Conference, pages 527--538, 2005.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT

General Terms:
Algorithms

Keywords:
XML, keyword search