A Taxonomy for Distance-Based Spatial Join Queries

A Taxonomy for Distance-Based Spatial Join Queries

Lingxiao Li, David Taniar
Copyright: © 2017 |Pages: 24
DOI: 10.4018/IJDWM.2017070101
(Individual Articles)
No Current Special Offers


Join operation is one of the most used operations in database management systems, including spatial databases. Hence, spatial join queries are very important in spatial database processing. There are many different kinds of spatial join queries, due to the richness in spatial data types and spatial operations. Therefore, it is important to understand the full spectrum of spatial join queries. The aim of this paper is to give a classification to one family type of spatial join, called the Distance-based Spatial Join. In the taxonomy, the authors divide this spatial join into three categories: (i) AllRange, (ii) All-kNN, and (iii) All-RNN. Each of these categories has its own variants. In this taxonomy, the authors confine the discussions to join queries on fixed points.
Article Preview


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 (M1), Western Link (M2) and East Link Highway (M3) 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 (Mi, Sj) based on the join predicate by using the topological operator cross. The result is {(M1, S4), (M2, S5), (M2, S6), (M3, S7)}.

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 {H1, H2, H3} and a list of restaurants {R1, R2, R3, R4, R5}. The join output is three pairs {(H2, R3), (H2, R4), (H3, R1)}; 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.

Complete Article List

Search this Journal:
Volume 20: 1 Issue (2024): Forthcoming, Available for Pre-Order
Volume 19: 6 Issues (2023)
Volume 18: 4 Issues (2022): 2 Released, 2 Forthcoming
Volume 17: 4 Issues (2021)
Volume 16: 4 Issues (2020)
Volume 15: 4 Issues (2019)
Volume 14: 4 Issues (2018)
Volume 13: 4 Issues (2017)
Volume 12: 4 Issues (2016)
Volume 11: 4 Issues (2015)
Volume 10: 4 Issues (2014)
Volume 9: 4 Issues (2013)
Volume 8: 4 Issues (2012)
Volume 7: 4 Issues (2011)
Volume 6: 4 Issues (2010)
Volume 5: 4 Issues (2009)
Volume 4: 4 Issues (2008)
Volume 3: 4 Issues (2007)
Volume 2: 4 Issues (2006)
Volume 1: 4 Issues (2005)
View Complete Journal Contents Listing