A Taxonomy for Distance-Based Spatial Join Queries

Introduction

Online maps are now widely available; everywhere, in smart phones, tablet computers, desktops, car navigation systems, etc. (Waluyo, Srinivasan, & Taniar, 2005; Waluyo, Srinivasan, & Taniar, 2005). Hence, spatial database management is used as the backend to store spatial objects, such as roads, parks, restaurants, petrol stations, schools, and other objects of interest (Güting, 1994).

One of the most common operations in databases is the join operation; and in spatial databases, it is Spatial Join Query (Šidlauskas & Jensen, 2014). A typical spatial join query involves two or more data sets on a spatial predicate. From the theoretical point of view, the spatial join is similar as join that in the traditional database system domain. The main difference is join predicate, which can be intersection, topological, directional or distance, rather than simply equijoin (Manolopoulos, Papadopoulos, & Vassilakopoulos, 2005).

A typical example of an intersection join is “to find all suburbs that are crossed by Southern Link Highway (M₁), Western Link (M₂) and East Link Highway (M₃) in the city of Melbourne”, as illustrated in Figure 1a. The entries of the two data sets M and S (i.e. highways and suburbs, respectively) are combined as pairs (M_i, S_j) based on the join predicate by using the topological operator cross. The result is {(M₁, S₄), (M₂, S₅), (M₂, S₆), (M₃, S₇)}.

Besides an intersection join, there is another spatial join, which is a distance-based join. An example for a distance-based join is “to find all pairs of hotels and restaurants within 1 kilometer apart”, as illustrated in Figure 1b, which has a list of hotels {H₁, H₂, H₃} and a list of restaurants {R₁, R₂, R₃, R₄, R₅}. The join output is three pairs {(H₂, R₃), (H₂, R₄), (H₃, R₁)}; each pair having less than 1 kilometer apart.

Figure 1.

Spatial Intersection join and distance-based join

Most of existing work on spatial join focused on intersection join (such as the first example in Figure 1a) (Šidlauskas & Jensen, 2014). A much less work has been focusing on distance-based join (such as the second example shown in Figure 1b). In this paper, we would like to focus on distance-based spatial join. The aim of this paper is to present a comprehensive study on various possibilities that distance-based spatial join can offer; hence, this paper presents a taxonomy on distance-based spatial join queries. Distance-based spatial join has a lot of applications, including those in data mining (Bohm & Krebs, 2002), online maps and mobile devices (Waluyo, Srinivasan, & Taniar, 2005; Waluyo, Srinivasan, & Taniar, 2005). Therefore, it is crucial to understand the capabilities of distance-based spatial join queries.