Please wait a minute...
浙江大学学报(工学版)
J4  2009, Vol. 43 Issue (09): 1549-1556    DOI: 10.3785/j.issn.1008973X.2009.09.001
    
Accelerating XML structural matching using bitmap filtration
CHEN Ke1, SHAO Feng2, CHEN Gang2, ZHENG Yao1
(1.School of Aeronautics and Astronautics, Zhejiang University, Hangzhou 310027, China;
2.College of Computer Science and Technology, Zhejiang University, Hangzhou 310027, China)
Download:   PDF(1788KB) HTML
Export: BibTeX | EndNote (RIS)      

Abstract  

A novel bitmap filtering method was proposed to accelerate structural matching in extensible markup language (XML) data query processing. Prefix/suffix tag bitmap on each XML node was constructed during document preprocessing. Then most of unmatched candidate nodes can be filtered by bitmap comparisons during XML structural matching. The bitmap filtering was integrated into some classical XML structural matching algorithms by some lowcost means. Experimental results show that the bitmap filtration can significantly improve the performance of XML structural matching.

CLC:  TP 309.2  
Service
E-mail this article
Add to my bookshelf
Add to citation manager
E-mail Alert
RSS
Articles by authors
Cite this article:

CHEN Ke, SHAO Feng, CHEN Gang, et al. Accelerating XML structural matching using bitmap filtration. J4, 2009, 43(09): 1549-1556.

URL:

http://www.zjujournals.com/eng/10.3785/j.issn.1008973X.2009.09.001     OR     http://www.zjujournals.com/eng/Y2009/V43/I09/1549


XML结构化匹配中的位图过滤加速法

针对可扩展标记语言(XML)数据查询中的结构化匹配问题，提出一种位图过滤加速法，该算法能有效地提高XML结构化匹配效率。通过预先为每个XML节点建立标签位图，该加速法在XML结构化匹配中，能以位图比较形式过滤大部分未匹配节点，从而达到加速效果。研究位图过滤加速法与几类XML结构化匹配算法的集成问题，提出了低代价的融合方法。实验证明，集成位图过滤加速法的XML结构化匹配算法在查询效率方面明显优于原有算法。

[1] AL-KHALIFA S, JAGADISH H V, KOUDAS N, et al. Structural joins: a primitive for efficient XML query pattern matching
[C] ∥ Proceedings of the 18th International Conference on Data Engineering. San Jose: IEEE, 2002: 141-152.
[2] JIANG H F, LU H J, WANG W, et al. XR-tree: indexing XML data for efficient structural joins
[C] ∥ Proceedings of the 19th International Conference on Data Engineering. India: IEEE, 2003: 253-264.
[3] CHEN Q, LIM A, ONG K W. D (k)-index: an adaptive structural summary for graph-structured data
[C] ∥ Proceedings of the 2003 ACM SIGMOD International Conference on Management of Data. San Diego, California: ACM, 2003: 134-144.
[4] GOLDMAN R, WIDOM J. Data guides: enabling query formulation and optimization in semi structured databases
[C] ∥ Proceedings of the 23rd International Conference on Very Large Data Bases. San Francisco, CA: ACM, 1997: 436-445.
[5] KAUSHIK R, SHENOY P, BOHANNON P, et al. Exploiting local similarity for indexing paths in graph-structured data
[C]∥ Proceedings of the 18th International Conference on Data Engineering. Washington, DC: IEEE, 2002: 129-140.
[6] MILO T, SUCIU D. Index structures for path expressions
[C] ∥ Proceedings of the 7th International Conference on Database Theory. London, UK: Springer, 1999: 277-295.
[7] WANG W, WANG H, LU H, et al. Efficient processing of XML path queries using the disk-based F&B index
[C] ∥ Proceedings of the 31st International Conference on Very large Data Bases. Trondheim, Norway: ACM, 2005: 145-156.
[8] BRUNO N, KOUDAS N, SRIVASTAVA D. Holistic twig joins: optimal XML pattern matching
[C] ∥ Proceedings ACM SIGMOD International Conference on Management of Data. Madison, Wisconsin: ACM, 2002: 310-321.
[9] LU Q, JEFFREY X Y, BOLIN D. TwigList: make twig pattern matching fast
[C] ∥ 12th International Conference on Database Systems for Advanced Applications. Bangkok, Thailand: LNCS, 2007: 850-862.
[10] JOSIFOVSKI V, FONTOURA M, BARTA A. Querying XML streams
[J]. The International Journal on Very Large Data Bases, 2005, 14(2): 197-210.
[11] LU J H, CHEN T, LING T W. TJFast: efficient processing of XML twig pattern matching
[C] ∥ Special Interest Tracks and Posters of the 14th International Conference on World Wide Web. Chiba, Japan: ACM, 2005: 1118-1119.
[12] CHEN S T, LI H G, TATEMURA J, et al. Twig2Stack: bottom-up processing of generalized-tree-pattern queries over XML documents
[C] ∥ Proceedings of the 32nd International Conference on Very Large Data Bases. Seoul, Korea: ACM, 2006: 283-294.
[13] KAUSHIK R, BOHANNON P, NAUGHTON J, et al. Covering indexes for branching path queries
[C]∥ Proceedings ACM SIGMOD International Conference on Management of Data. Wisconsin: ACM, 2002: 133-144.
[14] MORO M M, VAGENA Z, TSOTRAS V J. Tree-pattern queries on a lightweight XML processor
[C]∥ Proceedings of the 31st International Conference on Very Large Data Bases. Trondheim, Norway: ACM, 2005: 205-216.
[15] CHEN Z Y, GEHRKE J, KORN F, et al. Index structures for matching XML twigs using relational query processors
[J].Data and Knowledge Engineering, 2007, 60(2): 283-302.
[16] BOULOS J, KARAKASHIAN S. A new design for a native XML storage and indexing manager
[C]∥ 10th International Conference on Extending Database Technology. Munich, Germany: Springer, 2006: 755-772.
[17] SHAO F, CHEN G, YU L H, et al. Accelerating XML structural matching using suffix bitmaps
[C]∥ 7th International Conference on Computational Science. Beijing, China: LNCS, 2007: 253-260.
[18] SHAO F, CHEN G, DONG J X. Bitmap filtering: an efficient speedup method for XML structural matching
[C]∥ 8th ACIS International Conference on Software Engineering, Artificial Intelligence, Networking, and Parallel/Distributed Computing. Qingdao, China: IEEE, 2007: 756-761.
[1] CHEN Ke, HU Tian-lei, CHEN Gang. Fast trust chain search in role-based credential overlay network[J]. J4, 2010, 44(12): 2241-2250.
[2] MA Chen-hua, WANG Jing, QIU Jiong, LU Guo-dong. Flexible context-constraint-based access control model
for workflows[J]. J4, 2010, 44(12): 2297-2308.
[3] TU Li-Hua, CHEN Gang, WANG Wei, CHEN Ke, DONG Jin-Xiang. Containerbased self-organizing storage model[J]. J4, 2010, 44(5): 915-922.
[4] JIANG Jia, ZHANG Jie, CHEN De-Ren. Design and implementation of context-aware RBAC model based on reasoning[J]. J4, 2009, 43(09): 1609-1614.