吉林大学学报(工学版) ›› 2012, Vol. 42 ›› Issue (01): 134-139.

• 论文 • 上一篇    下一篇

P2P网络中基于非确定有限自动机的XML数据流过滤

沈洁1,2, 印桂生1, 王向辉1   

  1. 1. 哈尔滨工程大学 计算机科学与技术学院, 哈尔滨 150001;
    2. 哈尔滨商业大学 计算机与信息工程学院, 哈尔滨 150001
  • 收稿日期:2010-01-14 出版日期:2012-01-01 发布日期:2012-01-01
  • 通讯作者: 印桂生(1964-),男,教授, 博士生导师.研究方向:数据库与知识库,虚拟现实. E-mail:yinguisheng@hrbeu.edu.cn E-mail:yinguisheng@hrbeu.edu.cn
  • 作者简介:沈洁(1981-),女,博士研究生.研究方向:数据库系统,XML数据库.E-mail:shenjie@hrbeu.edu.cn
  • 基金资助:

    国家自然科学基金项目(61073042);黑龙江省自然科学基金项目(F201121);中央高校基本科研业务费专项项目(HEUCF 100606).

XML data filtering in P2P network based on non-determinate finite automata

SHEN Jie1,2, YIN Gui-sheng1, WANG Xiang-hui1   

  1. 1. College of Computer Science and Engineering, Harbin Engineering University, Harbin 150001,China;
    2. School of Computer and Information Engineering, Harbin University of Commerce, Harbin 150001,China
  • Received:2010-01-14 Online:2012-01-01 Published:2012-01-01

摘要:

将自动机方法对XML数据的过滤延伸到P2P网络中,依据在本地XML系统YFilter中构造非确定有限自动机(NFA)的思想,采用Chord环建立起分布式的NFA对于peer节点中的XML数据的查询过滤系统,并基于递归法执行查询过滤,在不同的peer节点上得到满足查询条件的数据集合。通过实验验证了当查询的数量和网络大小发生变化时分布式NFA的方法的执行性能。结果表明:本文方法可在不同的过滤场景中处理百万数量级的XPath查询,具有良好的网络流量和过滤延迟。

关键词: 计算机应用, XML, 对等网, 非确定有限自动机, 过滤

Abstract:

Automata was employed to filter XML data in P2P network,based on the concept to construct non-determinate finite automata in YFilter system locally,chord ring is used in XML filtering to build distributed non-determinate finite automata to filter the XML queries in peers. The main idea of the filtering system was based on the recursive method to obtain satisfied data set meeting the query condition in different peers. To examine the performance of the distributed non-determinate finite automata, more experiments are conducted with the changes in volume of inquiries and the network size. Results show that, at different filtering scenarios, the proposed method can deal with millions of XPath queries with good performances of network traffic and filtering delay.

Key words: computer application, XML, P2P network, non-determinate finite automata(NFA), filtering

中图分类号: 

  • TP393


[1] Stoica I, Morris R, Karger D, et al. Chord: a scalable peer-to-peerlookup service for internet applications//SIGCOMM,2001.

[2] Felber P, Chan C Y, Garofalakis M, et al. Scalable filtering of XML data for web services
[J]. IEEE Internet Computing, 2003, 7(1):49-57.

[3] Gong X, Qian W, Yan Y, et al. Bloom filter-based xml packets filtering for millions of path queries//Proc ICDE,2005.

[4] Uchiyama H, Onizuka M, Honishi T. Distributed XML stream filtering system with high scalability//Proc ICDE,2005.

[5] Chan C Y, Ni Y. Efficient XML data dissemination with piggybacking//Proc of SIGMOD Conference, 2007.

[6] Clark J. XML Path Language(XPath).. http://www.w3.org/TR/xpath.html.

[7] Martens Wim, Niehren Joachim. Minimizing tree automata for unranked trees//DBPL, 2005:232-246.

[8] IBM Faculty Partnership Award Program. YFilter 1.0 release... http://yfilter.cs.umass.edu/code release.htm.

[9] Bardosa D, Mignet L, Veltri P. Studying the XML Web: gathering statistics from an XML sample
[J]. World Wide Web, 2006,9(2):187-212.

[10] Tryfonopoulos C, Idreos S, Koubarakis M. Publish/subscribe functionality in IR environments using structured overlay networks//Proceedings of the 28th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval,2005:322-329.

[1] 刘富,宗宇轩,康冰,张益萌,林彩霞,赵宏伟. 基于优化纹理特征的手背静脉识别系统[J]. 吉林大学学报(工学版), 2018, 48(6): 1844-1850.
[2] 王利民,刘洋,孙铭会,李美慧. 基于Markov blanket的无约束型K阶贝叶斯集成分类模型[J]. 吉林大学学报(工学版), 2018, 48(6): 1851-1858.
[3] 金顺福,王宝帅,郝闪闪,贾晓光,霍占强. 基于备用虚拟机同步休眠的云数据中心节能策略及性能[J]. 吉林大学学报(工学版), 2018, 48(6): 1859-1866.
[4] 赵东,孙明玉,朱金龙,于繁华,刘光洁,陈慧灵. 结合粒子群和单纯形的改进飞蛾优化算法[J]. 吉林大学学报(工学版), 2018, 48(6): 1867-1872.
[5] 刘恩泽,吴文福. 基于机器视觉的农作物表面多特征决策融合病变判断算法[J]. 吉林大学学报(工学版), 2018, 48(6): 1873-1878.
[6] 欧阳丹彤, 范琪. 子句级别语境感知的开放信息抽取方法[J]. 吉林大学学报(工学版), 2018, 48(5): 1563-1570.
[7] 刘富, 兰旭腾, 侯涛, 康冰, 刘云, 林彩霞. 基于优化k-mer频率的宏基因组聚类方法[J]. 吉林大学学报(工学版), 2018, 48(5): 1593-1599.
[8] 桂春, 黄旺星. 基于改进的标签传播算法的网络聚类方法[J]. 吉林大学学报(工学版), 2018, 48(5): 1600-1605.
[9] 刘元宁, 刘帅, 朱晓冬, 陈一浩, 郑少阁, 沈椿壮. 基于高斯拉普拉斯算子与自适应优化伽柏滤波的虹膜识别[J]. 吉林大学学报(工学版), 2018, 48(5): 1606-1613.
[10] 车翔玖, 王利, 郭晓新. 基于多尺度特征融合的边界检测算法[J]. 吉林大学学报(工学版), 2018, 48(5): 1621-1628.
[11] 赵宏伟, 刘宇琦, 董立岩, 王玉, 刘陪. 智能交通混合动态路径优化算法[J]. 吉林大学学报(工学版), 2018, 48(4): 1214-1223.
[12] 黄辉, 冯西安, 魏燕, 许驰, 陈慧灵. 基于增强核极限学习机的专业选择智能系统[J]. 吉林大学学报(工学版), 2018, 48(4): 1224-1230.
[13] 傅文博, 张杰, 陈永乐. 物联网环境下抵抗路由欺骗攻击的网络拓扑发现算法[J]. 吉林大学学报(工学版), 2018, 48(4): 1231-1236.
[14] 曹洁, 苏哲, 李晓旭. 基于Corr-LDA模型的图像标注方法[J]. 吉林大学学报(工学版), 2018, 48(4): 1237-1243.
[15] 侯永宏, 王利伟, 邢家明. 基于HTTP的动态自适应流媒体传输算法[J]. 吉林大学学报(工学版), 2018, 48(4): 1244-1253.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!