一种基于跳表的DDM相交区域快速查询算法  

The Implementation of a Skip List Based Intersection Region Query Algorithm

作　　者：马越[1] 张大勇 金一丞[1] 

机构地区：[1]大连海事大学航海技术研究所,辽宁大连116026 [2]民航数据通信有限责任公司,北京100083

出　　处：《计算机仿真》2005年第7期46-50,共5页Computer Simulation

摘　　要：HLA是为提高仿真系统的互操作性和可重用性而提出的新型分布仿真标准。HLA中数据分发管理服务的目的是通过邦员对数据公布和订购区域的表达来过滤一个邦员所接收到的数据,同时减少对网络带宽的消耗。DDM的核心是多维矩形区域动态相交查找的问题,其算法性能的好坏对DDM的效率是至关重要的。现有的一些动态区域查找算法还不能同时满足高效、精确且易于实现等要求,为此设计出一种基于跳表数据结构的用于快速相交区域查找的区间跳表,同时分析了区间跳表的构造原则以及基本操作的流程,并在此基础上提出了基于区间跳表的相交区域查找算法。该算法的匹配精度高,时间复杂度低,且具有编程实现简单的特点。HLA is a serial of new distributed simulation standards released to improve the interoperability and reusability of simulation system. In HLA, Data Distributed Management （DDM） service aims to filter data received by a federate through the federate expressing of data publishing and subscribing region, and to reduce consumption of bandwidth. The kernel of DDM is query problem of dynamic multidimensional rectangle regions intersection. Whether its algorithm is good or not is very important to the efficiency of DDM. Presently, some dynamic region query algorithm can not meet the requirements of high efficiency, accuracy and easy implementation. Therefore, an interval skip table used in rapid intersection region query is designed with excellent advantages of skip table. Simultaneously, this paper analyses the structural principles of interval skip table and its basic process of operation, further points＇out intersection region query algorithm based on interval skip table. The advantages of this algorithm include high matching accuracy, low time complication, and easy programming implementation.

关 键 词：高层体系结构 数据分发管理 矩形相交 跳表 区间 

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