Please wait a minute...
浙江大学学报(工学版)
J4  2009, Vol. 43 Issue (09): 1549-1556    DOI: 10.3785/j.issn.1008973X.2009.09.001
自动化技术、计算机技术     
XML结构化匹配中的位图过滤加速法
陈珂1，邵峰2，陈刚2，郑耀1
(1.浙江大学 航空航天学院，浙江 杭州 310027；2.浙江大学 计算机科学与技术学院，浙江 杭州 310027)
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)
 全文: PDF(1788 KB)   HTML
摘要：

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

国家自然科学基金资助项目（60603044)；浙江省科技计划重大科技攻关资助项目(2006c11108).
作者简介: 陈珂(1977-)，女，河南郑州人，助理研究员，从事数据库、嵌入式软件和数据安全等的研究。
服务　　
把本文推荐给朋友
加入引用管理器
E-mail Alert
RSS
作者相关文章　　

引用本文:

陈珂, 邵峰, 陈刚, 等. XML结构化匹配中的位图过滤加速法[J]. J4, 2009, 43(09): 1549-1556.

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

链接本文:

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

[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] 陈珂， 胡天磊， 陈刚. 基于角色的信任证覆盖网络中高效信任链搜索[J]. J4, 2010, 44(12): 2241-2250.
[2] 马晨华, 王进, 裘炅, 陆国栋. 基于情景约束的工作流柔性访问控制模型[J]. J4, 2010, 44(12): 2297-2308.
[3] 余利华, 陈刚, 王伟, 陈柯, 董金祥. 一种基于容器的自组织存储模型[J]. J4, 2010, 44(5): 915-922.
[4] 江颉, 张杰, 陈德人. 基于推理的上下文感知RBAC模型设计和实现[J]. J4, 2009, 43(09): 1609-1614.