›› 2013, Vol. 28 ›› Issue (2): 366-381.doi: 10.1007/s11390-013-1337-1

Special Issue: Data Management and Data Mining

• Database and Data Management • Previous Articles     Next Articles

Fast Smallest Lowest Common Ancestor Computation Based on Stable Match

Jun-Feng Zhou1,3 (周军锋), Member, CCF, Guo-Xiang Lan1 (蓝国翔), Zi-Yang Chen1 (陈子阳), Member, CCF and Xian Tang2 (汤显)   

  1. 1 School of Information Science and Engineering, Yanshan University, Qinhuangdao 066004, China;
    2 School of Economics and Management, Yanshan University, Qinhuangdao 066004, China;
    3 Key Laboratory for Computer Virtual Technology and System Integration of Hebei Province, Yanshan UniversityQinhuangdao 066004, China
  • Received:2011-11-11 Revised:2012-05-30 Online:2013-03-05 Published:2013-03-05
  • Supported by:

    This research was partially supported by the National Natural Science Foundation of China under Grant Nos. 61073060, 61040023, 61272124, and the Science and Technology Research and Development Program of Hebei Province of China under Grant No. 11213578.

In this paper, we focus on efficient processing of XML keyword queries based on smallest lowest common ancestor (SLCA) semantics. For a given query Q with m keywords, we propose to use stable matches as the basis for SLCA computation, where each stable match M consists of m nodes that belong to the m distinct keyword inverted lists of Q. M satisfies that no other lowest common ancestor (LCA) node of Q can be found to be located after the first node of M and be a descendant of the LCA of M, based on which the operation of locating a stable match can skip more useless nodes. We propose two stable match based algorithms for SLCA computation, i.e., BSLCA and HSLCA. BSLCA processes two keyword inverted lists each time from the shortest to the longest, while HSLCA processes all keyword inverted lists in a holistic way to avoid the problem of redundant computation invoked by BSLCA. Our extensive experimental results verify the performance advantages of our methods according to various evaluation metrics.

[1] Cohen S, Mamou J, Kanza Y, Sagiv Y. XSEarch: A semanticsearch engine for XML. In Proc. the 29th International Con-ference on Very Large Data Bases (VLDB2003), September2003, pp.45-56.

[2] Guo L, Shao F, Botev C, Shanmugasundavam J. XRANK:Ranked keyword search over XML documents. In Proc. the2003 ACM SIGMOD International Conference on Manage-ment of Data (SIGMOD2003), June 2003, pp.16-27.

[3] Zhou R, Liu C, Li J. Fast ELCA computation for keywordqueries on XML data. In Proc. the 13th InternationalConference on Extending Database Technology (EDBT2010),March 2010, pp.549-560.

[4] Xu Y, Papakonstantinou Y. Efficient keyword search forsmallest LCAs in XML databases. In Proc. the ACMSIGMOD International Conference on Management of Data(SIGMOD2005), June 2005, pp.527-538.

[5] Li Y, Yu C, Jagadish H V. Schema-free xQuery. In Proc.the 30th International Conference on Very Large Data Bases(VLDB2004), Aug. 31-Sept. 3, 2004, pp.72-83.

[6] Chen L J, Papakonstantinou P. Supporting top-K keywordsearch in XML databases. In Proc. the 26th InternationalConference on Data Engineering (ICDE 2010), March 2010,pp.689-700.

[7] Sun C, Chan C Y, Goenka A K. Multiway SLCA-based key-word search in XML data. In Proc. the 16th InternationalConference on World Wide Web (WWW2007), May 2007,pp.1043-1052.

[8] Liu Z, Chen Y. Identifying meaningful return informationfor XML keyword search. In Proc. the 2007 ACM SIG-MOD International Conference on Management of Data(SIGMOD2007), June 2007, pp.329-340.

[9] Bao Z, Ling T W, Chen B, Lu J. Effective XML keywordsearch with relevance oriented ranking. In Proc. the 25thInternational Conference on Data Engineering (ICDE 2009),March 2009, pp.517-528.

[10] Li G, Feng J, Wang J, Zhou L. Effective keyword searchfor valuable LCAs over XML documents. In Proc. the 6thACM Conference on Information and Knowledge Manage-ment (CIKM2007), November 2007, pp.31-40.

[11] Li G, Ji S, Li C, Feng J. Efficient type-ahead search on rela-tional data: A TASTIER approach. In Proc. the 2009 ACMSIGMOD International Conference on Management of Data(SIGMOD2009), June 29-July 2, 2009, pp.695-706.

[12] Tatarinov I, Viglas S, Beyer K S, Shanmugasundaram J,Shekita E J, Zhang C. Storing and querying ordered XMLusing a relational database system. In Proc. the 2002 ACMSIGMOD International Conference on Management of Data(SIGMOD2002), June 2002, pp.204-215.

[13] Xu Y, Papakonstantinou Y. Efficient LCA based keywordsearch in XML data. In Proc. the 11th International Confer-ence on Extending Database Technology (EDBT2008), March2008, pp.535-546.

[14] Chen Y, Wang W, Liu Z, Lin X. Keyword search on struc-tured and semi-structured data. In Proc. the 2009 ACMSIGMOD International Conference on Management of Data(SIGMOD2009), June 29-July 2, 2009, pp.1005-1010.

[15] Chen Y, Wang W, Liu Z. Keyword-based search and explo-ration on databases. In Proc. the 27th International Confer-ence on Data Engineering (ICDE 2011), April 2011, pp.1380-1383.
No related articles found!
Full text



[1] Liu Mingye; Hong Enyu;. Some Covering Problems and Their Solutions in Automatic Logic Synthesis Systems[J]. , 1986, 1(2): 83 -92 .
[2] Chen Shihua;. On the Structure of (Weak) Inverses of an (Weakly) Invertible Finite Automaton[J]. , 1986, 1(3): 92 -100 .
[3] Gao Qingshi; Zhang Xiang; Yang Shufan; Chen Shuqing;. Vector Computer 757[J]. , 1986, 1(3): 1 -14 .
[4] Chen Zhaoxiong; Gao Qingshi;. A Substitution Based Model for the Implementation of PROLOG——The Design and Implementation of LPROLOG[J]. , 1986, 1(4): 17 -26 .
[5] Huang Heyan;. A Parallel Implementation Model of HPARLOG[J]. , 1986, 1(4): 27 -38 .
[6] Min Yinghua; Han Zhide;. A Built-in Test Pattern Generator[J]. , 1986, 1(4): 62 -74 .
[7] Tang Tonggao; Zhao Zhaokeng;. Stack Method in Program Semantics[J]. , 1987, 2(1): 51 -63 .
[8] Min Yinghua;. Easy Test Generation PLAs[J]. , 1987, 2(1): 72 -80 .
[9] Zhang Bo; Zhang Ling;. Statistical Heuristic Search[J]. , 1987, 2(1): 1 -11 .
[10] Zhu Hong;. Some Mathematical Properties of the Functional Programming Language FP[J]. , 1987, 2(3): 202 -216 .

ISSN 1000-9000(Print)

CN 11-2296/TP

Editorial Board
Author Guidelines
Journal of Computer Science and Technology
Institute of Computing Technology, Chinese Academy of Sciences
P.O. Box 2704, Beijing 100190 P.R. China
E-mail: jcst@ict.ac.cn
  Copyright ©2015 JCST, All Rights Reserved