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