An Efficient XML Pattern Matching Algorithm for Supporting Wildcard Query

doi:10.3969/j.issn.1006-2475.2016.04.014

Abstract

Abstract:

In XML query language, the wildcard query which includes “*” can effectively meet some special query requirements. But in the big data era, with the increasing of the XML file size and structural complexity, the existing algorithms which support wildcard query need huge amounts of memory to parse XML file and also need many single path matching operations and local result caching. Aiming at this situation, we propose a new XML pattern matching algorithm named WTwigList to solve the twig pattern containing the wildcard effectively. First, the hierarchical relationship of wildcard in the query pattern is processed to reduce unnecessary wildcard matching. Then the XML file is parsed as data stream pattern and the local Extended Dewey encoding is executed. After filtering operation, the ordered list of leaf node encoding is gotten, and the matching results can get from the list matching operations. A set of experimental result on both reallife and synthetic dataset demonstrates that WTwigList improves query efficiency andis of advantages in space efficiency, and it can deal with the P-C relationship quickly and accurately.

Key words: wildcard query, stream data processing, Extended Dewey Encoding, XML pattern matching

CLC Number:

TP311

CHEN Chong, JIANG Xia-jun.

An Efficient XML Pattern Matching Algorithm for Supporting Wildcard Query[J]. Computer and Modernization, doi: 10.3969/j.issn.1006-2475.2016.04.014.

References

［1］ Al-Khalifa S, Jagadish H V, Koudas Nick, et al. Structural joins: A primitive for efficient XML query pattern matching［C］// Proceedings of the 18th International Conference on Data Engineering. 2002:141-152.

［2］ Bruno N, Koudas N, Srivastava D.Holistic twig joins: Optimal XML pattern matching［C］// Proceedings of 2002 ACM SIGMOD International Conference on Management of Data. 2002:310-321.

［3］ Jiang Haifeng, Wang Wei, Lu Hongjun, et al. Holistictwig joins on indexed XML documents［C］// Proceedings of the 29th International Conference on Very Large Databases(VLDB). 2003:273-284.

［4］ Lu Jiaheng, Chen Ting, Ling Tokwang.Efficient processing of XML twig patterns with parent child edges: A look-ahead approach［C］// Proceedings of the 13th ACM International Conference on Information and Knowledge Management(CIKM). 2004:533-542.

［5］ Che Dunren, Ling T W, Hou Wenchi. Holistic Booleantwig pattern matching for efficient XML query processing［J］. IEEE Transaction on Knowledge and Data Engineering, 2012,24(11):2008-2024.

［6］李国良，冯建华，塔娜，等. TwigStar——快速处理XML twig查询中含通配符*的算法［J］. 计算机研究与发展， 2006,43(z3):430-437.

［7］ Lu Jiaheng, Ling Tokwang, Chan Chee-Yong, et al. From region encoding to extended dewey: On efficient processing of XML twig pattern matching［C］// Proceedings of the 31st VLDB Conference. 2005.

［8］ Lu Jiaheng, Ling Tokwang, Bao Zhifeng, et al. Extended XML treepattern matching: Theories and algorithms［J］. IEEE Transactions on Knowledge and Data Engineering, 2011,23(3):402-416.

［9］孟小峰. XML数据管理: 概念与技术［M］. 北京:清华大学出版社, 2009:126140.

［10］毕鑫,王国仁,赵相国,等. XML数据中Twig查询处理与优化技术研究综述［J］. 计算机科学与探索, 2013,7(9):769-782.

［11］Knorad C, Magnize F, Validating XML document in the streaming model with external memory［J］. ACM Transactions on Database Systems(TODS), 2013,38(4):84-87.

［12］张红. 基于ASP.NET与XML的异构数据库数据交互解析与实现［J］. 计算机与现代化, 2011(1):18-19.

［13］Hachicha M, Darmont J. A survey of XML tree pattern［J］. IEEE Transactions on Knowledge and Data Engineering, 2013,25(1):29-46.

［14］David Hunter, Jeff Rafter, Joe Fawcett,等. XML入门经典［M］. 吴文国译. 4版. 北京:清华大学出版社, 2009.

［15］University of Washington.XMLDataRepository［EB/OL］. http://www.cs.washington.edu/research/xmldatasets/, 2015-11-15.

［16］Xu Xiaoshuang,FengYucai,Wang Feng. Efficient processing of XML twig queries with all predicates［C］//Proceedings of the 8th International Conference on Computer and Information Science Conference. 2009:457-462.

[1]	LIN Wei. Incremental News Recommendation Method Based on Self-supervised Learning and Data Replay [J]. Computer and Modernization, 2023, 0(12): 1-6.
[2]	CHAI Li, WANG Xiao, GONG Jia-hao, WANG Yang, JI Shun-hui, ZHANG Peng-cheng. Survey of Supply Chain Oriented Consensus Algorithms [J]. Computer and Modernization, 2023, 0(11): 22-27.
[3]	WANG Chong-yang, ZHUANG Yi. Load Balancing Algorithm of Multi-job Cluster Based on SDN and Improved CSA Algorithm [J]. Computer and Modernization, 2023, 0(11): 28-35.
[4]	WANG Guang-hui, CHENG Gong-xu, LI Qing. Design of Power Material Sharing Cloud Warehouse Based on Blockchain Technology [J]. Computer and Modernization, 2023, 0(10): 99-106.
[5]	SHEN Jia-wei, LU Yi-ming, CHEN Xiao-yi, QIAN Mei-ling, LU Wei-zhong, . Review of Research on Human Behavior Detection Methods Based on Deep Learning [J]. Computer and Modernization, 2023, 0(09): 1-9.
[6]	GU Cheng-wei, DING Yong, LI Deng-hua. Personnel Safety Warning System in Industrial Plant Based on Computer Vision [J]. Computer and Modernization, 2023, 0(09): 20-26.
[7]	LIU Rui-xue, LI Wen, LIU Fang, DU Shou-guo. Prediction of Time Series with Missing Value Based on Tensor Autoregressive Completion [J]. Computer and Modernization, 2023, 0(09): 51-58.
[8]	MAO Ming-yang, XU Sheng-chao. Continuous Attribute Discretization Algorithm of Rough Sets for BP Neural Networks Based on Particle Swarm Optimization#br# [J]. Computer and Modernization, 2023, 0(09): 115-119.
[9]	CHEN Jia-min, ZHANG Bo-quan, MAI Hai-peng. Hippocampus Segmentation Based on Feature Fusion [J]. Computer and Modernization, 2023, 0(08): 1-6.
[10]	SHEN Shi-fan, WANG Li-song, WANG Xin-meng, QIN Xiao-lin. Tuple Space Coordination Model for Multi-robot Systems [J]. Computer and Modernization, 2023, 0(08): 98-106.
[11]	ZHONG Song-ying. Textile Raw Material Cost Warning Based on Apriori Algorithm of Association Rules [J]. Computer and Modernization, 2023, 0(07): 43-43.
[12]	ZHONG Lin-feng, LI Yan-feng, ZHANG Gui-peng, LIU Wen-yin. Decentralized Online Shopping Data Sharing Scheme Based on Blockchain [J]. Computer and Modernization, 2023, 0(07): 61-68.
[13]	LU Wei-qiang. Microservices-based Architecture Design for Civil Aircraft Industrial Software [J]. Computer and Modernization, 2023, 0(07): 73-78.
[14]	ZHANG Jun, SU Wen-hao. Optimization Method of Hadoop File Archiving Based on LZO [J]. Computer and Modernization, 0, (): 1-6.
[15]	LIU Pei. Medical Insurance Fee Control System Based on Data Mining [J]. Computer and Modernization, 2023, 0(06): 89-94.