Similarity Join for Big Geographic Data - Geographical Information Systems: Trends and Technologies - page 44

than the maximum value of ε used in our tests. Half of the records of each
dataset belong to R and the remaining ones to S . We use the geographical
distance geoDist with both datasets. The available memory to perform the
in-memory SJ algorithm was 32 MB.
We compare the performance of MRSimJoin with MRThetaJoin, an
adaptation of the memory-aware 1-Bucket-Theta algorithm (Okcan and
Riedewald 2011) that uses the single-node QuickJoin algorithm (Jacox and
Samet 2008) in the reduce function.

Performance Evaluation with Synthetic Data

Increasing Scale Factor . Figure 9 compares the way MRSimJoin and
MRThetaJoin scale when the data size increases (SF1-SF10). This experiment
uses a value of epsilon of 2 miles. The core result in this fi gure is that
MRSimJoin performs and scales signifi cantly better than MRThetaJoin.
The execution time of MRThetaJoin grows from being 1.7 times the one
of MRSimJoin for SF=1 to 8.4 times for SF=10. The execution time of
MRThetaJoin is signifi cantly higher than that of MRSimJoin because the
total size of all the partitions of MRThetaJoin is signifi cantly larger than
that of MRSimJoin.

Increasing Epsilon . Figure 10 shows how the execution time of MRSimJoin
and MRThetaJoin increase when epsilon increases (1-5 miles). These tests use
SF1. The performance of MRSimJoin is better than the one of MRThetaJoin
for all the values of epsilon. Specifi cally, the execution time of MRSimJoin is
59.6% of the one of MRThetaJoin for epsilon = 1 mile, and 64.2% for epsilon
= 5 miles. We can also observe that, in general, the execution time of both
algorithms grows slowly when epsilon grows. The increase in execution time
is due to a higher number of distance computations in both algorithms and
slightly larger sizes of window-pair partitions in the case of MRSimJoin.

SynthData, Eps:2

Output Size
MRSimJoin
MRThetaJoin

4000 25000000

20000000

3000

15000000

2000

10000000

1000

5000000

0 0

123456789 0

Scale Factor (SF)

Fig. 9. Increasing SF-SynthData.