Partitioning strategies for spatio-textual similarity join
Jinfeng Rao, Jimmy Lin, Hanan Samet · 2014
Given a collection of geo-tagged objects with associated textual descriptors, the spatio-textual similarity join (STJoin) problem is to identify all pairs of similar objects that are close in distance. This task, which is useful in localized recommendations and other applications, is challenging since computing the join is super-linear with respect to the size of the collection. In this paper, we explore partitioning strategies for tackling STJoin. One approach is to start with a spatial data structure, traverse regions and apply a previous algorithm for identifying similar pairs of textual documents called All-Pairs. An alternative approach is to construct a global index but partition postings spatially and modify the All-Pairs algorithm to prune candidates based on distance. We evaluate these approaches on two real-world datasets and find that when running in a single thread, both approaches are comparable in terms of performance. However, a multi-threaded implementation of the global index approach is able to achieve far better speedup given its ability to parallelize at a finer granularity to avoid skewed distributions in task sizes. In addition to using All-Pairs as the underlying textual similarity join algorithm, we also explored an alternate algorithm known as PPJ: our findings are consistent, which suggests that load balancing is a fundamental issue affecting parallel implementations of STJoin algorithms.