基于最小圆覆盖区域划分的索引过滤算法  

Index Filtering Algorithm Based on Minimum Enclosing Circle Partition

作　　者：陈洁[1,2] 方滨兴[1,2] 谭建龙[2] 金世超[2,3] 

机构地区：[1]北京邮电大学计算机学院,北京100876 [2]中国科学院信息工程研究所信息智能处理实验室,北京100093 [3]北京大学软件与微电子学院,北京100084

出　　处：《计算机学报》2012年第10期2139-2146,共8页Chinese Journal of Computers

基　　金：国家"八六三"高技术研究发展计划项目基金(2011AA010705;2012AA012502)资助~~

摘　　要：过滤算法设计是信息内容安全处理系统中的一个重要环节,过滤速度成为衡量过滤系统性能的首要因素.索引结构是处理大规模数据的一种有效方式,但目前索引方法都是针对特定检索领域而设计,在实际过滤应用中,并不能满足过滤实时性需求.为了加快信息过滤中数据查询的判定速度,文中提出一种基于最小圆覆盖的区域划分方法,构建了适合过滤的索引结构:F-tree.该算法充分考虑实际过滤环境中正例(正常信息)多、反例(敏感信息)少的非平衡数据分布特性,利用最小圆覆盖划分方法得到最大否定判断区域.在查询阶段,正例以最大概率落入否定区域,根据否定性判定原理可以对正例快速否定判定,从而加快整体查询的判定速度.实验表明,与现有算法相比,所提出的算法减少了查询中的距离计算次数,有效提高了过滤查询性能.Filte process system, ring algorithm design play a very important role in information content security filtering speed become the first consideration factor for improving the system performance. Index is an effective method to cope with massive data and can get a good performance. Unfortunately, most of existing index methods especially designed for information retrieval application and these indexes cannot achieve a good performance for filtering application. In order to improve the filtering performance, this paper proposes an index filtering method based on min- imum enclosing circle data partition, and built a particular filtering index called F-tree. This method considers the imbalance data distribution with more positive and less negative in real filte- ring situation, the minimum enclosing circle partition method is used to obtain maximum negative area. In query step, the positive data falls into negative area with maximum probability in order to get up to the all data judgment speed. Experimental results show that the proposed method can improve the filtering performance by reducing the times of computation.

关 键 词：过滤算法 最小圆覆盖 否定性判定 索引结构 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]