Chinese Journal of Computers   Full Text
Title	Dynamic Region Matching Algorithm Based on Index-Order
Authors	YAO Yi-Ping1) ZHANG Ying-Xing1) CHEN Xin2) JI Li-Chun1)
Address	1)(College of Computer, National University of Defense Technology， Changsha 410073) 2)(School of Computer Science and Technology, Beijing University of Posts and Communications, Beijing 100876)
Year	2009
Issue	No.7(1375—1381)
Abstract &   Background	Abstract The HLA Data Distribution Management (DDM) service provides an abstract, application-driven data filtering capability. It can reduce the transmission and reception of irrelevant data. The key problem of its implementation is region matching algorithm. The current algorithms such as directly matching, grid-based, and sort-based approach are all not so perfect. They are either time consuming or inaccuracy in filtering, and are difficult to support large-scale simulation. Aiming at the characteristic of frequently region changing in large-scale simulation systems, a more effective matching algorithm based on intersecting information of region moving is proposed. It represents the upper bound and lower bound of a range with two nodes, and uses two indexed ordered tables to store the publication and subscription nodes of a dimension respectively. It uses range intersecting information during a range moving, and limits the matching computing only in the area of moving. Thereby it can greatly decrease the candidate ranges that need to do matching computing, thus can decrease the matching complexity greatly, and reach precise matching with high performance. This algorithm is extremely fit for the need of large-scale distributed simulation that has a large number of regions. Keywords high level architecture; runtime infrastructure; data distribution management; region matching; dynamic Background The High Level Architecture (HLA) is an architecture for reuse and interoperation of distributed simulations, which has been standardized as IEEE1516 in September 2000. It provides several Data Distribution Management (DDM) services to filter out irrelevant data. These services rely on the computation of intersection between update and subscription regions, which is called matching. Currently, there are several typical DDM matching algorithms, however, these algorithms are still time consuming and not good enough for scenarios when the regions have a large number of dimensions and need to be modified along with the simulation advancement dynamically. The paper introduces an algorithm using range intersecting information during a range moving, and limits the matching computing only in the moving area. This algorithm also use an index ordered table data structure in order to improve its query efficiency. This work is supported by the National Natural Science Foundation of China under grant No.60773019, the Ph.D. Programs Foundation of Ministry of Education of China under grant No.200899980004 and the National High Technology Research and Development Program of China under grant No.2006AA01Z330. The aim of the research is to achieve precise matching with high performance in dynamic scenarios. Until now, the research team has published more than 20 papers about the technology of parallel and distributed simulation.