[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

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.

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