Spatial Joins in Main Memory: Implementation Matters!

A recent PVLDB paper reports on experimental analyses of ten spatial join techniques in main memory. We build on this compre-hensive study to raise awareness of the fact that empirical running time performance findings in main-memory settings are results of not only the algorithms and data structures employed, but also their implementation, which complicates the interpretation of the results. In particular, we re-implement the worst performing technique without changing the underlying high-level algorithm, and we then offer evidence that the resulting re-implementation is capable of outperforming all the other techniques. This study demonstrates that in main memory, where no time-consuming I/O can mask vari-ations in implementation, implementation details are very impor-tant; and it offers a concrete illustration of how it is difficult to make conclusions from empirical running time performance find-ings in main-memory settings about data structures and algorithms studied. 1