Calculating Similarity of XML Documents by Weighted Pq-gram Algorithm

doi:10.3969/j.issn.1006-2475.2015.03.005

Abstract

Abstract: Clustering for XML documents is an important method for efficiently managing XML documents, and calculating similarity of XML documents is the pivotal step. Pq-gram algorithm is an efficient method to solve the problem of calculating similarity of XML documents. However, it ignores that the nodes of XML documents are ordered. Based on the pq-gram algorithm, weighted pq-gram algorithm, in accordance with the structural characteristics of XML documents, sets weight for nodes, and sets weight for pq-grams based on the weight of nodes, then applies the weight to the method of calculating similarity of XML documents. Experimental results show that the weighted pq-gram algorithm describes the contribution of nodes better in the process of calculating similarity of XML documents, and improves the precision of calculating of XML documents.

Key words: XML documents, calculate similarity, pq-gram, weight

CLC Number:

TP391

WANG Cheng-yong, DU Qing-wei, SUN Jing, SUN Zhen. Calculating Similarity of XML Documents by Weighted Pq-gram Algorithm[J]. Computer and Modernization, 2015, 0(3): 20-25.

References

［1]Algergawy A, Mesiti M, Nayak R, et al. XML data clustering: An overview［J]. ACM Computing Surveys, 2011,43(4):Article No. 25.
［2]Tai K C. The tree-to-tree correction problem［J]. Journal of the ACM, 1979,6(3):422-433.
［3]Zhang Kaizhong, Statman R, Shasha D. On the editing distance between unordered labeled trees［J]. Information Processing Letters, 1992,42(3):133-139.
［4]Zhang Kaizhong, Shasha D. Simple fast algorithms for the editing distance between trees and related problems［J]. SIAM Journal on Computing, 1989,18(6):1245-1262.
［5]Jiang Tao, Wang Lusheng, Zhang Kaizhong. Alignment of trees—an alternative to tree edit［J]. Theoretical Computer Science, 1995,143(1):137-148.
［6]Zhang Kaizhong. Algorithms for the constrained editing distance between ordered labeled trees and related problems［J]. Pattern Recognition, 1995,28(3):463-474.
［7]Guha S, Jagadish H V, Koudas N, et al. Approximate XML joins［C]// Proceedings of the 2002 ACM SIGMOD International Conference on Management of Data. 2002:287-298.
［8]Augsten N, Bhlen M, Gamper J. Approximate matching of hierarchical data using pq-grams［C]// Proceedings of the 31st International Conference on Very Large Data Bases. 2005:301-312.
［9]Augsten N, Bhlen M, Gamper J. The pq-gram distance between ordered labeled trees［J]. ACM Transactions on Database Systems, 2010,35(1):1-16.
［10]〖JP2〗Chawathe S S. Comparing hierarchical data in external memory［C]// Proceedings of the 25th International Conference on Very Large Data Bases. 1999:90-101.
［11]Tekli J, Chbeir R, Yetongnon K. An overview on XML similarity: Background, current trends and future directions［J]. Computer Science Review, 2009,3(3):151-173.
［12]Nierman A, Jagadish H V. Evaluating structural similarity in XML documents［C]// Proceedings of the 5th International Workshop on the Web and Database. 2002:61-66.
［13]Dalamagas T, Cheng T, Winkel K J, et al. A methodology for clustering XML documents by structure［J]. Information Systems, 2006,31(3):187-228.
［14]The DBLP Team. DBLP DataSet［DB/OL]. http://dblp.uni-trier.de/xml/, 2014-11-01.
［15]Association for Computing Machinery. Sidmod DataSet［DB/OL]. http://www.sigmod.org/publications/sigmod-record/1312, 2014-11-01.
［16]Expasy Website. UniProtKB/Swiss-Prot ［DB/OL]. http://us.expasy.org/sprot/, 2014-11-01.
［17]刘晨. XML文档聚类的研究［D]. 大连:大连理工大学, 2010.
［18]Posonia A M, Jyothi V L. Structural-based clustering technique of XML documents［C]// Proceedongs of the 2013 International Conference on Circuits, Power and Computing Technologies. 2013:1239-1242.

[1]	ZHANG Yu1, 2, LI Jing1, 2, MA Ming1, 2, WANG Zhongxiang1, 2, SUN Yan1, 2. YOLOLW: A Novel Lightweight Object Detection Model [J]. Computer and Modernization, 2024, 0(11): 91-98.
[2]	JIAO Jian, JI Yuanfa, SUN Xiyan, WU Jianhui, LIANG Weibin. Multiple Unmanned Aerial Vehicles Three-dimensional Cooperative Route Planning Based on Improved GWO Algorithm [J]. Computer and Modernization, 2024, 0(10): 1-6.
[3]	ZHOU Anda, TANG Chaoying. Semantic Segmentation Algorithm for Rainy Road Scene and Its Mobile Deployment [J]. Computer and Modernization, 2024, 0(10): 7-13.
[4]	YUE Youjun1, 2, ZHANG Yuankun1, ZHAO Hui1, 2, WANG Hongjun1, 2. Indoor Scene Recognition Method Based on Multi-scale Feature and Attention Module [J]. Computer and Modernization, 2024, 0(08): 37-42.
[5]	SHI Xianwei1, FAN Xin2. Semantic Segmentation of Video Frame Scene Based on Lightweight [J]. Computer and Modernization, 2024, 0(08): 49-53.
[6]	LIU Yuxuan1, 2, LIAO Yuchen1, LIU Zhonghui1. Construction of Single-condition Triadic Concept and Its Fusion Recommendation Application [J]. Computer and Modernization, 2024, 0(07): 1-6.
[7]	ZHU Lingheng1, 2, GU Danpeng1, 2, TANG Songqiang1, 2, CHEN Xiaoyong1, 2. Algorithm for Layered Bipartite Graph Maximum Matching Problem [J]. Computer and Modernization, 2024, 0(06): 59-63.
[8]	XIA Huang-zhi1, 2, CHEN Li-min3, MAO Xue-di1, 2, QI Fu1, 2. Adaptive Bald Eagle Search Algorithm Embedded with Somersault Foraging and Application [J]. Computer and Modernization, 2024, 0(02): 7-14.
[9]	ZHOU Yong-qin, WANG Yong, WANG Ying. Lightweight PCB Defect Detection Method Based on Multi-scale Features and Attention Mechanism [J]. Computer and Modernization, 2024, 0(02): 88-92.
[10]	XIA Huang-zhi, CHEN Li-min, MAO Xue-di, . Adaptive Bald Eagle Search Algorithm with Dynamic Learning and Gaussian Mutation [J]. Computer and Modernization, 2024, 0(01): 117-126.
[11]	LUO Ming-jie, FENG Kai-ping. Lightweight Facial Expression Recognition Method Based on Sandglass Structure and Attention Mechanism [J]. Computer and Modernization, 2023, 0(11): 89-94.
[12]	OU Jia-cheng, ZENG An, JIN Liang. CP-YOLOX-based Algorithm for Protein Target Detection in Cryo-electron Micrographs [J]. Computer and Modernization, 2023, 0(11): 113-119.
[13]	LU Lei, HE Zhi-ming, HUANG Zhi-cheng. An Improved Sparrow Search Algorithm Based on Multi-strategy [J]. Computer and Modernization, 2023, 0(10): 23-31.
[14]	LI Yan-man, WANG Bi-heng, ZHAO Ling-yan. Safety Helmet Detection Based on Lightweight YOLOv5 [J]. Computer and Modernization, 2023, 0(10): 59-64.
[15]	LEI Yi-han, CAO Li-feng, HAN Meng-da, HAN Xue. Security Handover Architecture and Method for Software Defined Space-ground#br# Integration Network [J]. Computer and Modernization, 2023, 0(08): 119-126.