In this paper we consider the problem of identifying intersections between two sets of d-dimensional axis-parallel rectangles. This is a common operation that arises in many agent-based simulation studies, and is of central importance in the context of High Level Architecture (HLA), where it is at the core of the Data Distribution Management (DDM) service. Several realizations of the DDM service have been proposed; however, many of them are either inefficient or inherently sequential. We propose a parallel version of the Sort-Based Matching algorithm for shared-memory multiprocessors. Sort-Based Matching is one of the most efficient serial algorithms for the DDM problem, but is quite difficult to parallelize because of data dependencies. We describe the algorithm and compute its asymptotic running time; we complete the analysis by assessing its performance and scalability through extensive experiments on two commodity multicore systems based on a dual socket Intel Xeon processor, and a single socket Intel Core i7 processor.
It is demonstrated that power-efficient software also requires simplicity and the use of elementary data structures in addition to asymptotically optimal CPU and memory requirements. Though in the past few decades much effort has been devoted to reporting all k intersecting pairs in a planar set of n iso-oriented rectangles, all the known algorithms using elementary data structures, such as linked lists, are either not optimal, report some intersections repeatedly or fail to report some altogether. A simpler algorithm is proposed that uses only linear arrays and that takes O(n log n + k) time and O(n) space, which are the best possible under the algebraic RAM model of computation. The algorithm is designed for systems with limited resources, such as mobile 3D graphics, and can be implemented in less than 100 lines of Java code. The High Level Architecture (HLA) is a standard for constructing distributed simulations. The Data Distribution Management services of HLA reduce the amount of data delivered to an HLA federate by allowing communications connections to be based on federates’ expressed data production and requirements. At the core of determining which connections to make is a geometric problem: finding the dynamic intersection of d-dimensional rectilinear hyperrectangles in d-space. Four different algorithms for solving that problem are described, including a new one developed through application of a data structure from computational geometry. Those algorithms are then compared in an experiment designed to reveal how well they perform in the specific context of the data distribution application. Both intersection performance and connectivity efficiency results are reported. This paper compares three data structures that support area operations on 2-space: linked lists, quad trees, and multidimensional binary trees (k-d trees). Region searching is the most important operation these data structures must support in many applications. Insertion and deletion must also be reasonably fast. The three data structures are described and implementation considerations are discussed. Extensive experimentation was done using an experimental program that executed algorithms for all three data structures on the same problem. Results of this experimentation is presented to show the superior performance of k-d trees. The conclusion of this paper is that in applications where region search (or point search) on large problems is crucial (as in computer-aided design), k-d trees provide superior performance. Quad trees have become quite popular recently to solve the same problem--this may be due to unfamiliarity with k-d trees or a feeling that they are hard to implement. Actual working code for k-d trees (and quad trees) is included in this paper in an attempt to address both these problems. In order to handle spatial data efficiently, as required in computer aided design and geo-data applications, a database system needs an index mechanism that will help it retrieve data items quickly according to their spatial locations However, traditional indexing methods are not well suited to data objects of non-zero size located m multi-dimensional spaces In this paper we describe a dynamic index structure called an R-tree which meets this need, and give algorithms for searching and updating it. We present the results of a series of tests which indicate that the structure performs well, and conclude that it is useful for current database systems in spatial applications