Initial Comparison of Monotonic Logical Grid and Alternative Data Base Structures

摘要

We compare the Monotonic Logical Grid (MLG) data base structure to alternative data base structures for tasks relevant to computing the dynamics of N moving objects. The tasks include identifying near neighbors of designated nodes, retrieving information on the near neighbors, and ordering this information according to distances of the associated near neighbors from the designated nodes. We use a collection of N = 64K (65,536) noninteracting objects with randomly initialized velocities. We have performed the calculations on the Naval Research Laboratory (NRL) Cray X-MP computer, which has a hardware gather-scatter capability. We consider two types of alternative data structures for which the indexing is static (the data corresponding to each node always have the same index and memory locations). These two types encompass most of the data structures currently in use in manybody simulations. Data structure Type 1 carries no additional information or pointers which could identify the near neighbors of each node. Data structure Type 2 does carry coarse information on near neighbors by maintaining linked lists or a related system of pointers that change with the motion of nodes in time. Our numerical test show that the MLG data structures are vastly superior to the Type 1 data structure when we require near-neighbor information on a large number M of designated or focal nodes.