[1] Xiao Kun, Chen Shihong, Matching algorithm for label-based integrable-ware query [J]. Journal of Southeast University (English Edition), 2007, 23 (3): 431-434. [doi:10.3969/j.issn.1003-7985.2007.03.026]

Copy

Matching algorithm for label-based integrable-ware query()

基于标注的一种积件查询匹配算法

Share：

Journal of Southeast University (English Edition)[ISSN:1003-7985/CN:32-1325/N]

Volumn:

23

Issue:

2007 3

Page:

431-434

Research Field:

Computer Science and Engineering

Publishing date:

2007-09-30

Info

Title:

Matching algorithm for label-based integrable-ware query

基于标注的一种积件查询匹配算法

Author(s):

Xiao Kun¹;  Chen Shihong¹;  2

¹School of Computer, Wuhan University, Wuhan 430072, China
²National Multimedia Software Engineering Technology Research Center, Wuhan University, Wuhan 430072, China

肖锟¹;  陈世鸿¹;  2

¹武汉大学计算机学院, 武汉 430072; ²武汉大学国家多媒体软件工程技术研究中心, 武汉 430072

Keywords:

integrable-ware;  retrieval;  label;  tree-inclusion matching

积件;  查询;  标注;  树包容匹配

PACS:

TP311

DOI:

10.3969/j.issn.1003-7985.2007.03.026

Abstract:

Based on tree-inclusion matching, retrieval may be transformed into matching between the query tree and the integrable-ware label tree.Considering the retrieval specialities of integrable-ware, three theorems of matching are given.On this basis, the inverted-path string algorithm for the integrable-ware label tree query is proposed.This algorithm searches from leaf nodes rather than from root nodes, and considers about the path length and the total number of leaf nodes.It can terminate the failed matching as early as possible and avoid spending too much time on loop comparisons in character string matching.It utilizes the dictionary suffix order to skip much of the impossibility matching path.The experimental results show that this algorithm enhances the recall and the precision of integrable-ware query efficiency while maintaining the searching speed of the integrable-ware.

基于树的包容匹配思想, 把积件的查询转化为查询树与积件标注树之间的匹配.通过研究积件查询的特点, 提出积件标注树匹配的3个定理.在此基础上, 提出积件查询的逆路径字符串匹配算法.该算法从叶节点开始进行匹配查找, 同时考虑从叶节点到根节点的路径长度关系, 能尽早终止不能匹配成功的路径, 避免了字符串的循环反复查找, 同时利用同一路径长度下字符串按字典排序, 跳过大量不可能匹配的路径.实验结果表明, 此方法在保持积件查找速度的前提下, 能有效提高积件的查全率和查准率.

References:

[1] Jia Xiaohui, Chen Dehua, Yan Mei, et al.Research on matching model and algorithm for faceted-based software component query[J].Journal of Computer Research and Development, 2004, 41(10):1634-1638.(in Chinese)
[2] Dennis Shasha, Jason T L.ATreeGrep:approximate searching in unordered trees[C]//Proc of the 14th International Conference on Scientific and Statistical Database Management (SSDBM’02). Edinburgh, Scotland, 2002:89-98.
[3] Xu Ruzhi, Qian Leqiu, Chen Jianping, et al.Research on matching algorithm for XML-based software component query[J].Journal of Software, 2003, 14(7):1195-1202.(in Chinese)
[4] Wang Yuanfeng, Xue Yunjiao, Zhang Yong, et al.A matching model for software component classified in faceted scheme[J].Journal of Software, 2003, 14(3):401-408.(in Chinese)
[5] Cooper B, Sample N, Franklin M, et al.A fast index for semi-structured data[C]//Proc of the 27th International Conference on VLDB.Roma, Italy, 2001:341-350.
[6] Kilpelainen Pekka.Tree matching problems with applications to structured text databases[D].Helsinki, Finland:Department of Computer Science of University of Helsinki, 1992.
[7] Chen M S, Yu P S, Wu K L.Optimization of parallel execution for multi-join queries[J].Knowledge and Data Engineering, 1996, 8(3):416-428.
[8] Shasha Dennis, Wang Jason T L, Giugno Rosalba.Algorithmics and applications of tree and graph searching[C]//Proc of the 21st ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems. Madison, WI, USA, 2002:39-52.

Memo

Memo:

Biographies: Xiao Kun(1976—), male, graduate;Chen Shihong(corresponding author), male, professor, chen_-lei0605@sina.com.

Common functions