基于多槽分桶的快速规则冲突检测算法

留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

基于多槽分桶的快速规则冲突检测算法

罗谦, 唐常杰, 郑皎凌, 胡建

文章导航 > 电子科技大学学报 > 2012 > 41(3): 447-452

罗谦, 唐常杰, 郑皎凌, 胡建. 基于多槽分桶的快速规则冲突检测算法[J]. 电子科技大学学报, 2012, 41(3): 447-452. doi: 10.3969/j.issn.1001-0548.2012.03.024

引用本文:

罗谦, 唐常杰, 郑皎凌, 胡建. 基于多槽分桶的快速规则冲突检测算法[J]. 电子科技大学学报, 2012, 41(3): 447-452. doi: 10.3969/j.issn.1001-0548.2012.03.024

LUO Qian, TANG Chang-jie, ZHENG Jiao-ling, HU Jian. Fast Algorithm to Detect Conflict Rule Based on the Multi_Slot Sub_Bucket[J]. Journal of University of Electronic Science and Technology of China, 2012, 41(3): 447-452. doi: 10.3969/j.issn.1001-0548.2012.03.024

Citation:

LUO Qian, TANG Chang-jie, ZHENG Jiao-ling, HU Jian. Fast Algorithm to Detect Conflict Rule Based on the Multi_Slot Sub_Bucket[J]. Journal of University of Electronic Science and Technology of China, 2012, 41(3): 447-452. doi: 10.3969/j.issn.1001-0548.2012.03.024

基于多槽分桶的快速规则冲突检测算法

doi: 10.3969/j.issn.1001-0548.2012.03.024

罗谦^1,2,
唐常杰¹,
郑皎凌³,
胡建⁴

1.
四川大学计算机学院成都 610065;
2.
中国民用航空总局第二研究所信息公司成都 610041;
3.
成都信息工程学院软件工程系成都 610225;
4.
中国西南电子设备研究所成都 610036

基金项目:

国家自然科学基金(60773169);中国民用航空局科研项目(MHRD200924)

作者简介:
罗谦(1975-),男,博士生,高级工程师,主要从事数据挖掘、进化计算、企业智能计算等方面的研究.

中图分类号: TP301

Fast Algorithm to Detect Conflict Rule Based on the Multi_Slot Sub_Bucket

1.
Department of Computer Science,Sichuan University Chengdu 610065;
2.
Information Filiale,The Second Research Institute of CAAC Chengdu 610041;
3.
Department of Software Engineering,Chengdu University of Infomation Technology Chengdu 610225;
4.
Southwest China Research Institute of Electronic Equipment Chengdu 610036

摘要: 为解决企业海量规则集合中产生的规则自我冲突问题,提出了基于多槽分桶的快速规则冲突检测算法MSSB。该算法利用同槽实桶之间规则两两必不冲突特性,将复杂的冲突规则求解转换为线性时间内的不冲突规则求解,从而在稳定的空间和时间复杂度下有效解决规则冲突发现问题。先形式化描述了通用规则冲突和不冲突,并在合理的假设条件下证明了3个规则间关系的命题和同槽不冲突定理;然后提出了基于哈夫曼树和三角矩阵结构的MSSB算法;最终在国内民航典型机场的规则集合上完成了对比实验,结果表明新算法的冲突检测性能比Policytree算法相提高了36.2%。
- 冲突检测 /
- 多槽 /
- 规则引擎 /
- 分桶
Abstract: To resolve the conflict within the massive rules in enterprise, this paper proposes a fast rule conflict-detection algorithm named multi_slot sub_bucket conflict cetection (MSSB) based on multi_slot and sub_bucket. It turns rule's complexity conflict detection into result of non-conflict rules in lineartime by the theorem of non-conflict. First, this research proposed the concepts of general rule's conflict and non-conflict, and proves three propositions and the theorem of non-conflict. Then it proposes the MSSB algorithm by the structure of Huffman tree and Triangular matrix. Extensive experiments over real data of Hub Airport show the effectiveness of new proposed MSSB algorithm. The average space complexity is decreased 33.6% and matching time is decreased 36.2% compared with traditional linear detection and policytree.
- conflict detection /
- multi_slot /
- rule engines /
- sub_bucket

[1]	王军. 基于多尺度特征预测的异常事件检测 . 电子科技大学学报, 2022, 51(4): 586-591. doi: 10.12178/1001-0548.2021333
[2]	艾斯卡尔·艾木都拉, 武文成. 基于多尺度局部梯度的点目标检测技术 . 电子科技大学学报, 2019, 48(6): 893-903. doi: 10.3969/j.issn.1001-0548.2019.06.014
[3]	孙萍, 晏明国, 张鸿泽, 黄琦, 周林, 赵苡, 彭富刚, 刘培良. 差分脉冲阳极溶出伏安法检测重金属离子 . 电子科技大学学报, 2017, 46(5): 784-789. doi: 10.3969/j.issn.1001-0548.2017.05.022
[4]	张涛, 谢红, 黄少滨. 多Agent交互策略模型检测方法 . 电子科技大学学报, 2016, 45(5): 802-807. doi: 10.3969/j.issn.1001-0548.2016.05.016
[5]	杨勇, 郭玲, 叶阳东, 周小佳. 多类变分优化的自然图像分割方法 . 电子科技大学学报, 2016, 45(5): 824-831. doi: 10.3969/j.issn.1001-0548.2016.05.020
[6]	杨勇, 郭玲, 叶阳东, 周小佳. 多类变分优化的自然图像分割方法 . 电子科技大学学报, 2016, 45(5): -. doi: 第45卷第5期 pp:824-831
[7]	俞东进, 吴为, 殷昱煜, 闫大强, 刘志清. 基于模型检测的服务规则路由正确性验证方法 . 电子科技大学学报, 2014, 43(1): 107-112. doi: 10.3969/j.issn.1001-0548.2014.01.018
[8]	吴丹, 危胜军. 基于模型检测的策略冲突检测方法 . 电子科技大学学报, 2013, 42(5): 745-748,768. doi: 10.3969/j.issn.1001-0548.2013.05.019
[9]	江虹, 伍春, 马景辉. 最小二乘SVM的CR认知引擎设计 . 电子科技大学学报, 2011, 40(1): 41-46. doi: 10.3969/j.issn.1001-0548.2011.01.008
[10]	韩杰思, 沈建京. 采用图像滤波的多特征JPEG盲检测 . 电子科技大学学报, 2011, 40(2): 255-260. doi: 10.3969/j.issn.1001-0548.2011.02.020
[11]	邹见效, 张正迁, 徐红兵. 三重化冗余多机系统心跳检测机制研究 . 电子科技大学学报, 2010, 39(3): 379-383. doi: 10.3969/j.issn.1001-0548.2010.03.012
[12]	周秀云, 何晓渝, 冯中正. 左中右差分绝对值最大法的边缘检测方法研究 . 电子科技大学学报, 2010, 39(3): 388-391. doi: 10.3969/j.issn.1001-0548.2010.03.014
[13]	徐图, 罗瑜, 何大可. 多类支持向量机的DDoS攻击检测的方法 . 电子科技大学学报, 2008, 37(2): 274-277.
[14]	杨丹, 胡光岷, 李宗林, 姚兴苗. 全局的多流量相关异常检测算法 . 电子科技大学学报, 2008, 37(6): 823-827.
[15]	胡东伟, 陈杰. TD-SCDMA中一种新的空分多址实现算法 . 电子科技大学学报, 2008, 37(5): 668-672.
[16]	吴知, 许家珆. 免疫原理在多Agent入侵检测系统中的应用 . 电子科技大学学报, 2005, 34(3): 381-384.
[17]	张宇. 基于差分和肤色图像的人脸检测算法 . 电子科技大学学报, 2005, 34(4): 497-500.
[18]	杨清夙, 游志胜, 张先玉. 基于豪斯多夫距离的快速多人脸检测算法 . 电子科技大学学报, 2004, 33(4): 407-409.
[19]	高飞, 郭彦平, 赵东风. 随机多址信道冲突分解算法及吞吐量分析 . 电子科技大学学报, 2001, 30(2): 124-128,133.
[20]	王玉林. 利用Bernstein多项式设计FIR槽状滤波器 . 电子科技大学学报, 2000, 29(3): 252-255.

WeChat

点击查看大图

计量

文章访问数: 3277
HTML全文浏览量: 113
PDF下载量: 52
被引次数: 0

基于多槽分桶的快速规则冲突检测算法

doi: 10.3969/j.issn.1001-0548.2012.03.024

1. 四川大学计算机学院成都 610065;

2. 中国民用航空总局第二研究所信息公司成都 610041;

3. 成都信息工程学院软件工程系成都 610225;

4. 中国西南电子设备研究所成都 610036

基金项目:

国家自然科学基金(60773169);中国民用航空局科研项目(MHRD200924)

作者简介:
罗谦(1975-),男,博士生,高级工程师,主要从事数据挖掘、进化计算、企业智能计算等方面的研究.

收稿日期: 2011-07-15
修回日期: 2012-03-20
刊出日期: 2012-06-15

中图分类号: TP301

关键词:

冲突检测 /
多槽 /
规则引擎 /
分桶

摘要: 为解决企业海量规则集合中产生的规则自我冲突问题,提出了基于多槽分桶的快速规则冲突检测算法MSSB。该算法利用同槽实桶之间规则两两必不冲突特性,将复杂的冲突规则求解转换为线性时间内的不冲突规则求解,从而在稳定的空间和时间复杂度下有效解决规则冲突发现问题。先形式化描述了通用规则冲突和不冲突,并在合理的假设条件下证明了3个规则间关系的命题和同槽不冲突定理;然后提出了基于哈夫曼树和三角矩阵结构的MSSB算法;最终在国内民航典型机场的规则集合上完成了对比实验,结果表明新算法的冲突检测性能比Policytree算法相提高了36.2%。

English Abstract

罗谦, 唐常杰, 郑皎凌, 胡建. 基于多槽分桶的快速规则冲突检测算法[J]. 电子科技大学学报, 2012, 41(3): 447-452. doi: 10.3969/j.issn.1001-0548.2012.03.024

引用本文:

罗谦, 唐常杰, 郑皎凌, 胡建. 基于多槽分桶的快速规则冲突检测算法[J]. 电子科技大学学报, 2012, 41(3): 447-452. doi: 10.3969/j.issn.1001-0548.2012.03.024

LUO Qian, TANG Chang-jie, ZHENG Jiao-ling, HU Jian. Fast Algorithm to Detect Conflict Rule Based on the Multi_Slot Sub_Bucket[J]. Journal of University of Electronic Science and Technology of China, 2012, 41(3): 447-452. doi: 10.3969/j.issn.1001-0548.2012.03.024

Citation:

LUO Qian, TANG Chang-jie, ZHENG Jiao-ling, HU Jian. Fast Algorithm to Detect Conflict Rule Based on the Multi_Slot Sub_Bucket[J]. Journal of University of Electronic Science and Technology of China, 2012, 41(3): 447-452. doi: 10.3969/j.issn.1001-0548.2012.03.024

全文HTML

/

下载: 全尺寸图片幻灯片

分享

用微信扫码二维码

分享至好友和朋友圈

返回

期刊在线

编辑办公

友情链接

电子科技大学

版权所有 © 《电子科技大学学报》编辑部

地址: 成都市建设北路二段四号电子科技大学主楼中350室电话: 028-83202308,83207559 Email: xuebao@uestc.edu.cn

本系统由北京仁和汇智信息技术有限公司开发