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

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

罗谦, 唐常杰, 郑皎凌, 胡建. 基于多槽分桶的快速规则冲突检测算法[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

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

基金项目: 

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

详细信息
    作者简介:

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

  • 中图分类号: TP301

Fast Algorithm to Detect Conflict Rule Based on the Multi_Slot Sub_Bucket

  • 摘要: 为解决企业海量规则集合中产生的规则自我冲突问题,提出了基于多槽分桶的快速规则冲突检测算法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.
计量
  • 文章访问数:  4427
  • HTML全文浏览量:  135
  • PDF下载量:  56
  • 被引次数: 0
出版历程
  • 收稿日期:  2011-07-14
  • 修回日期:  2012-03-19
  • 刊出日期:  2012-06-14

目录

    /

    返回文章
    返回