The first step in the FTSE algorithm is to find all intersecting
pairs between elements of R and elements of S. The technique
used to obtain these intersecting pairs is shown in Algorithm 1.
First, a grid of dimensionality d is constructed (line 4 of the algorithm).
The edge length of each element of the grid is .
In lines 6 to 8 of the algorithm, a Minimum Bounding Rectangle
(MBR) is constructed for each element ri of R. This MBR has
a side length of 2 in each dimension, and its center is the point
ri. This construction method ensures that ri overlaps with no more
than 3d elements in the grid.
The MBR construction is illustrated in Figure 4 for one and two
dimensions. In one dimension, the MBR of ri is flattened into a
line and intersects with 3 grid elements, as shown in Figure 4a. In
two dimensions, the MBR of ri intersects with 9 grid elements, as
shown in Figure 4b.
A FIFO queue is associated with each cell g of the grid. The
queue for each g is used to maintain a reference to all ri that are
within of g, in order of increasing i. This is done in line 9 of
Algorithm 1.
The intersections between R and S are found in lines 11-18 of
Algorithm 1. The grid cell g that contains each sj ∈ S is located.
The elements of R in the queue associated with g are compared
with sj to see if they are within of one another. For each element
rk of R that is within of sj , the index of rk, i.e. k, is inserted into
the intersection list Lj of sj . The entries of Lj are also maintained
in order of increasing k.
Note that the size of the grid is likely to be small for the following
reason: Since data is normalized with mean zero and standard
deviation σ = 1, most data will fall between -3 and 3. If the
value is not exceptionally small relative to σ (which is common
– for example, [29] uses 0.5σ), the size of the grid is reasonably
small. Outliers beyond -3 or 3 are rare and can be captured into an
additional grid cell.
http://www.liang-chen.com/images/200...rithm_2.pg.jpg
