Differences

This shows you the differences between two versions of the page.

--- pads:ddm [2013/06/26 08:28] – created gdangelo
+++ pads:ddm [2021/07/29 08:01] – [Parallel Sort-based Matching (pSBM)] gda
@@ Line 1: / Line 1: @@
 ====== DDM: Data Distribution Management ======
+The High Level Architecture (HLA) specification (IEEE 1516) defines several Data Distribution Management (DDM) services to forward events generated on //update// regions to a set of //subscription// regions. For example, consider a simulation of vehicles moving over a two-dimensional terrain. In this case, each vehicle may be interested in events happening inside its area of interest (e.g., its field of view), that might be approximated with a rectangular region centered at the vehicle position. This kind of problem also arises in the context of Massively Multiplayer Online
+Games, where the game engine must send game updates only to players that might be affected, in order to reduce computation cost and network traffic.
+Unfortunately, many solutions employed for the Data Distribution Management service of HLA are either inefficient, or can only partially be parallelized.
+=====  Parallel Sort-based Matching (pSBM)=====
+A novel [[:parallelsbm-paper|parallel extension of the Sort Based Matching algorithm]], whose sequential version is considered among the most efficient solutions to the DDM problem.
+=====  Interval Tree Matching (ITM) =====
+We propose the [[pads:Interval Tree Matching (ITM)]] algorithm for computing intersections among d-rectangles. ITM is based on a simple Interval Tree data structure, and exhibits an embarrassingly parallel structure.