# APRIL: Approximating Polygons as Raster Interval Lists

Thanasis Georgiadis  University of Ioannina, GreeceGreece
<EMAIL_ADDRESS>,  Eleni Tzirita Zacharatou  IT University of
CopenhagenDenmark<EMAIL_ADDRESS>and  Nikos Mamoulis  University of Ioannina,
GreeceGreece<EMAIL_ADDRESS>
###### Abstract.

The spatial intersection join an important spatial query operation, due to its
popularity and high complexity. The spatial join pipeline takes as input two
collections of spatial objects (e.g., polygons). In the filter step, pairs of
object MBRs that intersect are identified and passed to the refinement step
for verification of the join predicate on the exact object geometries. The
bottleneck of spatial join evaluation is in the refinement step. We introduce
APRIL, a powerful intermediate step in the pipeline, which is based on raster
interval approximations of object geometries. Our technique applies a sequence
of interval joins on “intervalized” object approximations to determine whether
the objects intersect or not. Compared to previous work, APRIL approximations
are simpler, occupy much less space, and achieve similar pruning effectiveness
at a much higher speed. Besides intersection joins between polygons, APRIL can
directly be applied and has high effectiveness for polygonal range queries,
within joins, and polygon-linestring joins. By applying a lightweight
compression technique, APRIL approximations may occupy even less space than
object MBRs. Furthermore, APRIL can be customized to apply on partitioned data
and on polygons of varying sizes, rasterized at different granularities. Our
last contribution is a novel algorithm that computes the APRIL approximation
of a polygon without having to rasterize it in full, which is orders of
magnitude faster than the computation of other raster approximations.
Experiments on real data demonstrate the effectiveness and efficiency of
APRIL; compared to the state-of-the-art intermediate filter, APRIL occupies
2x-8x less space, is 3.5x-8.5x more time-efficient, and reduces the end-to-end
join cost up to 3 times.

PVLDB Reference Format:
PVLDB, 14(1): XXX-XXX, 2020.
doi:XX.XX/XXX.XX ††This work is licensed under the Creative Commons BY-NC-ND
4.0 International License. Visit https://creativecommons.org/licenses/by-nc-
nd/4.0/ to view a copy of this license. For any use beyond those covered by
this license, obtain permission by emailing<EMAIL_ADDRESS>Copyright is held
by the owner/author(s). Publication rights licensed to the VLDB Endowment.
Proceedings of the VLDB Endowment, Vol. 14, No. 1 ISSN 2150-8097.
doi:XX.XX/XXX.XX

PVLDB Artifact Availability:
The source code, data, and/or other artifacts have been made available at
%leave␣empty␣if␣no␣availability␣url␣should␣be␣sethttps://github.com/ThanGeo/APRIL.

##  1\. Introduction

We study the problem of computing the spatial intersection join between two
spatial object collections $R$ and $S$, which identifies all pairs of objects
$(r,s),r\in R,s\in S$ such that $r$ shares at least one common point with $s$.
Besides being a common operation in geographic information systems (GIS), the
spatial intersection join finds a wide range of applications in geo-spatial
interlinking (Papadakis et al., 2021), GeoSPARQL queries on RDF data stores
(Theocharidis et al., 2019), interference detection between objects in
computer graphics (Shinya and Forgue, 1991), suggestion of synapses between
neurons in neuroscience models (Nobari et al., 2013). Recently, there is a
growing interest in spatial query evaluation over complex object geometries
(i.e., polygons) (Doraiswamy and Freire, 2020, 2022; Georgiadis and Mamoulis,
2023; Kipf et al., 2020; Winter et al., 2021; Nobari et al., 2017; Pandey et
al., 2018a; Sidlauskas et al., 2018; Teng et al., 2021; Zacharatou et al.,
2017, 2021).

A naive way to evaluate the join is to run an intersection test algorithm from
computational geometry for each pair $(r,s)$ in $R\times S$. However, this
method is extremely expensive, since (i) the number $|R\times S|$ of pairs to
be tested can be huge and (ii) for each pair the test takes $O(n\log n)$ time
(Brinkhoff et al., 1994). To mitigate (i), the join is evaluated in two steps.
Provided that the minimum bounding rectangles (MBRs) of the objects are
available (and possibly indexed), in the filter step, an efficient MBR-join
algorithm (Brinkhoff et al., 1993b; Tsitsigkos et al., 2019) is used to find
the pairs of objects $(r,s)\in R\times S$ such that $MBR(r)$ intersects with
$MBR(s)$. In the refinement step, for each pair that passes the filter step,
the expensive intersection test on the exact object geometries is applied. To
further reduce the number of pairs to be refined, intermediate filters can be
added to the pipeline (Brinkhoff et al., 1994; Zimbrao and de Souza, 1998;
Georgiadis and Mamoulis, 2023). The main idea is to use, in addition to the
MBR, object approximations that can help to identify fast whether a candidate
pair $(r,s)$ that passes the MBR filter is (i) a sure result, (ii) a sure non-
result, or (iii) an indecisive pair, for which we still have to apply the
geometry intersection test.

Previously proposed approximations in intermediate filters include simple
convex polygons (5C or convex hull (Brinkhoff et al., 1994)), raster
approximations (Zimbrao and de Souza, 1998), and “intervalized” raster
approximations paired with binary codes (Georgiadis and Mamoulis, 2023). Each
of these approaches has its drawbacks. The convex polygons proposed in
(Brinkhoff et al., 1994), although cheap to store and relatively fast to
compute, can only be used to identify sure non-results and fail to reduce
significantly the number of indecisive pairs that are sent to the expensive
refinement step. The raster approximation technique of (Zimbrao and de Souza,
1998) occupies too much space and is not always effective in pruning object
pairs. Finally, the state-of-the-art raster-intervals approach (Georgiadis and
Mamoulis, 2023), which improves over (Zimbrao and de Souza, 1998) in terms of
space complexity and pruning effectiveness, has a high preprocessing cost and
occupies significant space.

In this paper, we propose APRIL (Approximating Polygons as Raster Interval
Lists), a technique which significantly improves upon the Raster Intervals
(RI) approach of (Georgiadis and Mamoulis, 2023), having the following key
differences. First, previous rasterization techniques for spatial joins
(Zimbrao and de Souza, 1998; Georgiadis and Mamoulis, 2023) divide the raster
cells that intersect a polygon in three classes: Full cells that are fully
covered by the polygon, Strong cells that are covered by the polygon more than
50% but less than 100%, and Weak cells that are covered by the polygon by at
most 50%. APRIL, unites Strong and Weak cell classes to a single Partial
class, which simplifies storage and accelerates the intermediate filter.
Second, previous work (Zimbrao and de Souza, 1998; Georgiadis and Mamoulis,
2023) explicitly stores or encodes cell-class information. The main novelty of
APRIL is the representation of each object by two lists of intervals; one list
that includes All cells (independently of their class) and one that includes
only Full cells. The intermediate filter is then applied as a sequence of
interval joins; All-All join (AA-join) filters out all non-results and then
Full-All (FA-join), All-Full (AF-join) joins filter (i.e., identify) sure
results, leaving indecisive pairs to the refinement step. Since there are no
cell-specific comparisons, the intermediate filter using APRIL is much faster
compared to RI (Georgiadis and Mamoulis, 2023) which performs comparisons at
the cell level for each pair of intersecting intervals. Finally, APRIL applies
a compression technique, based on delta encoding, to greatly reduce the space
required to store the interval lists. This way, the APRIL approximations may
require even less storage compared to object MBRs, making it possible to store
and process them in the main memory. Moreover, APRIL’s compression scheme
allows partial, on-demand decompression of interval lists, which is conducted
during interval join evaluation.

In addition to APRIL, the contributions of this paper include:

  * •

We show the generality of APRIL in supporting spatial selection queries,
spatial within joins, and joins between polygons and linestrings.

  * •

We present a space partitioning approach, which increases the resolution of
the raster grid and achieves more refined object approximations compared to
(Georgiadis and Mamoulis, 2023) leading to fewer inconclusive cases and,
therefore, faster query evaluation.

  * •

We investigate options for defining and joining APRIL approximations of
different polygons at different granularities based on their geometries.

  * •

We propose a novel, one-step “intervalization” algorithm that computes the
APRIL approximation of a polygon without having to rasterize it in full.

Our experimental evaluation on real data shows that, compared to the state-of-
the-art intermediate filter (RI), APRIL is 3.5x-8.5x faster, (ii) occupies
2x-8x less space, and (iii) has orders of magnitude lower preprocessing cost.
Using APRIL, the cost of end-to-end spatial join drops up to 71%, compared to
using RI.

The rest of the paper is structured as follows: Section 2 provides the
necessary background. Section 3 details APRIL’s features, construction and
usage. Section 4 offers customization options that help to further tune APRIL
to fit the system’s or dataset’s needs. In Section 5 we study the efficient
construction of APRIL approximations. Section 6 includes our experiments that
verify APRIL’s performance. Section 7 reviews related work and, finally,
Section 8 concludes the paper with suggestions for future work.

##  2\. Background

The intersection join pipeline applies an MBR-join algorithm (Brinkhoff et
al., 1993a; Jacox and Samet, 2007; Tsitsigkos et al., 2019) on (indexed) MBR
approximations of the objects, to identify pairs of object MBRs that
intersect; these form candidate join results. The direct refinement of each
candidate pair using computational geometry algorithms is very expensive and
can easily take up to $99\%$ of the end-to-end join cost (Ray et al., 2014).
In view of this, several studies (Brinkhoff et al., 1994; Zimbrao and de
Souza, 1998; Georgiadis and Mamoulis, 2023) suggest the use of an intermediate
filter based on more accurate object approximations than the MBR, to further
reduce the number of object pairs that need to be refined. Figure 1
illustrates a general spatial intersection join pipeline that includes an
intermediate filter. For each candidate join pair $(r.id,s.id)$ produced by
the MBR-join, we perform a look-up of the geometric approximations (GAs) of
objects $r$ and $s$ using their IDs, assuming a fast access method (e.g.,
$r.id$ is row-number in a table or vector storing $R$’s GAs). The GAs are used
by the intermediate filter to identify the pair $(r.id,s.id)$ as a true
negative or a true hit, or forward it to the refinement step in order for it
to access the exact geometries and make the ultimate decision (at a high
computational cost).

Figure 1. Spatial intersection join pipeline that includes an intermediate
filter.

Raster Intervals (RI) (Georgiadis and Mamoulis, 2023) is the state-of-the-art
intermediate filter. Assuming a global $2^{N}\times 2^{N}$ grid superimposed
over the data space, RI approximates each object $p$ by the set of cells in
the grid that overlap $p$. Further, these cells are classified to Full,
Strong, and Weak, based on their coverage percentage with the object’s
geometry ($100\%$, $>50\%$ and $\leq 50\%$, respectively). Consider a
candidate join pair of two objects $r$ and $s$ whose MBRs overlap. If there
are no common cells in the approximations of $r$ and $s$, then the pair is a
true negative and is eliminated. If the objects have common cells, then it is
possible to detect true hits by examining the types of common cells. All
possible cases are shown in Table 1; if for at least one common cell its types
in the two objects lead to a ‘yes’ case, then the object pair is a definite
join result and the refinement step can be avoided. Figure 2 illustrates three
cases of two polygonal objects, whose MBRs intersect. In Fig. 2(a), the two
object approximations do not share any common cells, so the pair is pruned as
a true negative. In Fig. 2(b), the two objects are reported as a join result
(true hit); they definitely intersect because there exists a cell (the one
with the bold-line border) which is fully covered by one of them and strongly
covered by the other (see full-strong case in Table 1). In Fig. 2(c) all
common cells in the two object approximations are either weak-weak or weak-
strong, so the pair is determined as inconclusive and passed to the refinement
step.

Table 1. Do two objects intersect, based on a common cell? | weak | strong | full
---|---|---|---
weak | inconclusive | inconclusive | yes
strong | inconclusive | yes | yes
full | yes | yes | yes
---
|  |
(a) true negative | (b) true hit | (c) inconclusive
Figure 2. Raster approximations as intermediate filters (Zimbrao and de Souza,
1998).

To expedite the comparison of raster approximations of objects, RI maps each
cell in the $2^{N}\times 2^{N}$ space to an integer in $[0,2^{2N}-1]$, which
is the cell’s order in the Hilbert space-filling curve (Hilbert, 1891). Then,
the cells in an object approximation with continuous IDs are merged into
intervals $[start,end)$, which are sorted to form an intervals list. To
capture the types of cells in each interval, the method uses 3-bit codes
(Table 2), which are concatenated to form an interval’s coding. The creation
of Raster Intervals is illustrated in Figure 3.

The intermediate filter for a pair of objects is then implemented as follows.
The sorted interval lists of the two objects are merged (as in merge-join) to
identify pairs of intervals that overlap. For each such interval pair, the
corresponding bit-codes are aligned and bitwise $AND$ed; if the result of an
$AND$ is non-zero then the object pair is immediately reported as a true hit;
if there are no overlapping intervals, then the pair is reported as a true
negative. If there is at least one pair of non-overlapping intervals and for
all such pairs the bitwise $AND$ of their codings is 0, then the pair is
passed to the refinement step as indecisive.

Table 2. 3-bit type codes for each input dataset (Georgiadis and Mamoulis, 2023) | input $R$ | input $S$
---|---|---
full | 011 | 101
strong | 101 | 011
weak | 100 | 010
Figure 3. Hilbert curve cell enumeration and interval generation and encoding
for a polygon in a $8\times 8$ space (Georgiadis and Mamoulis, 2023).

In summary, the RI intermediate filter checks all common cells of two object
approximations en masse. Even though RI offers high refinement candidate
reduction compared to other polygon approximations, it comes with a number of
drawbacks. First, the construction of RI approximations (i.e., pre-processing)
is costly, because for each cell that overlaps with the object, we need to
identify the cell type. Second, the intermediate filter involves a complex and
relatively expensive bitstring alignment process. Third, RI approximations may
occupy too much space, especially for large polygons that include long
intervals with spacious encodings.

##  3\. Methodology

We propose APRIL (Approximating Polygons as Raster Interval Lists), an
enhanced intermediate filtering method for spatial intersection joins, which
is more efficient and less space consuming compared to previous raster-based
techniques (Zimbrao and de Souza, 1998; Georgiadis and Mamoulis, 2023).

###  3.1. A\- and F-Interval Lists

With APRIL, we reduce the approximation complexity of RI through two major
changes. First, we unify the Weak and Strong cell types to a single cell type
called Partial. Partial are non-empty cells which overlap with the polygon’s
area in less than $100\%$ of their area; i.e., the cells that are intersected
by the polygon’s edges. Second, APRIL discards the bit-coding of RI; instead,
each polygon is approximated simply by two sorted interval lists: the A-list
and the F-list. The A-list is formed by intervals that concisely capture all
cells that overlap with the polygon, regardless their type (Full or Partial),
whereas the F-list captures only Full cells. An interval list having $n$
intervals is stored as a simple sorted integer sequence in which the $i$-th
interval’s $start,end$ are located at positions $2i$ and $2i+1$ respectively,
for $i\in[0,n)$.

Figure 4. The interval generation for a polygon in a $8\times 8$ space,
without bit-coding and using interval lists.

The A-list and F-list for the example polygon of Figure 3 are shown in Figure
4. Strong and Weak cell types become Partial and the representation compared
to RI is simplified. Note that the set of intervals in each of the A\- and F\-
lists are disjoint. The new relationship identification table for a cell
shared by two polygons, is shown in Table 3. Removing the Strong cell type
renders the approximation unable to detect true hits for cells of the Strong-
Strong case, as common cells that are both Partial cannot decide definite
intersection between the two polygons.111As we have found experimentally
(Section 6), this has minimal effect on the amount of true hits and true
negatives that the intermediate filter manages to detect. This is due to the
fact that the only cases of true hits missed are pairs of polygons that
intersect with each other exclusively in cells typed Strong for both polygons
and nowhere else.

Table 3. APRIL: Do two objects intersect in a common cell? | Partial | Full
---|---|---
Partial | Inconclusive | yes
Full | yes | yes

Construction To construct an APRIL approximation we need to first identify the
cells intersected by the polygon’s area in the grid, while also labeling each
one of them as Partial or Full. Then, Intervalization derives the F-list, by
sorting the set of Full cells by ID (i.e., Hilbert order) and merging
consecutive cell IDs into intervals. To derive the A-list, we repeat this for
the union of Full and Partial cells. In Section 5, we propose an efficient
algorithm that derives the F- and A-list of a polygon without having to label
each individual cell that intersects it.

###  3.2. APRIL Intermediate Spatial Join Filter

Similar to RI (Georgiadis and Mamoulis, 2023), APRIL is employed by an
intermediate filter (Figure 1), between the MBR-filter and the refinement
phase. Given a pair $(r,s)$ of objects coming as a result of an MBR-join
algorithm (Brinkhoff et al., 1993b; Patel and DeWitt, 1996; Tsitsigkos et al.,
2019), APRIL uses the A- and F-lists of $r$ and $s$ to detect fast whether the
polygons (i) are disjoint (true negative), (ii) are guaranteed to intersect
(true hit), or (iii) are inconclusive, so they have to be forwarded to the
refinement stage to verify their intersection.

Whether $r$ and $s$ are disjoint (i.e. do not intersect), can be determined by
checking whether their A-lists have any pair overlapping of intervals or not.
If they have no overlapping intervals, then $r$ and $s$ do not have any common
cell in the grid and thus they cannot intersect. We check this condition by
merge-joining the A-lists and stoping as soon as we detect two overlapping
intervals.

Pairs of polygons that have at least one pair of overlapping intervals in
their A-lists are then checked using their F-lists. We perform two more merge-
joins: $\textit{A(r)}\bowtie\textit{F(s)}$ and
$\textit{F(r)}\bowtie\textit{A(s)}$; detecting an overlapping intervals pair
in one of these two joins means that there is a Full cell in one object that
is common to a Full or Partial cell of the other object. This guarantees that
the two objects intersect and the pair $(r,s)$ is immediately reported as a
spatial join result. If $\textit{A(r)}\bowtie\textit{F(s)}$ fails to detect
$(r,s)$ as a true hit, then $\textit{F(r)}\bowtie\textit{A(s)}$ is conducted;
if the latter also fails, then $(r,s)$ is an inconclusive candidate join pair,
which is forwarded to the refinement step.

In summary, the APRIL intermediate filter sequence consists of 3 steps: the
AA-join, AF-join, and FA-join, as illustrated in Figure 5 and described by
Algorithm 1. Each step is a simple merge-join between two sorted interval
lists. Since each list contains disjoint intervals, each of the three interval
joins takes $O(n+m)$ time, where $n$ and $m$ are the lengths of the two
interval join input lists. Hence, the total cost of the APRIL filter (i.e.,
Algorithm 1) is linear to the total number of intervals in the A\- and F-lists
of $r$ and $s$.

Figure 5. The 3 steps of the intermediate filter for a candidate pair of
polygons.

1:$(r,s)$ such that $MBR(r)$ intersects $MBR(s)$

2:function IntervalJoin($X,Y$)

3: $i\leftarrow 0$; $j\leftarrow 0$

4: while $i<|X|$ and $j<|Y|$ do

5: if $X_{i}$ overlaps with $Y_{j}$ then

6: return true$\triangleright$ overlap exists

7: end if

8: if $X_{i}.end\leq Y_{j}.end$ then $i\leftarrow i+1$ else $j\leftarrow j+1$

9: end while

10: return false$\triangleright$ no overlaps detected

11:end function

12:

13:if not IntervalJoin($A(r),A(s)$) then

14: return false $\triangleright$ true negative

15:end if

16:if IntervalJoin($A(r),F(s)$) then

17: return true $\triangleright$ true hit

18:end if

19:if IntervalJoin($F(r),A(s)$) then

20: return true $\triangleright$ true hit

21:end if

22:return REFINEMENT$(r,s)$ $\triangleright$ forward pair to refinement

Algorithm 1 APRIL join algorithm.

Join Order Optimization The AA-join, AF-join, and FA-join could be applied in
any order in Algorithm 1. For example, if $(r,s)$ is a true hit, it would be
more beneficial to perform the AF-join and the FA-join before the AA-join, as
this would identify the hit earlier. On the other hand, if $(r,s)$ is a true
negative, conducting the AA-join first avoids the futile AF\- and FA-joins.
However, there is no way to know a priori whether $(r,s)$ is a true hit or a
true negative. In addition, we experimentally found that changing the join
order does not have a high impact on the intermediate filter cost and the
overall cost. For a typical candidate pair $(r,s)$ the common cells are
expected to be few compared to the total number of cells covered by either $r$
or $s$, making AA-join the most reasonable join to start with. This is
confirmed by our experiments where the number of candidate pairs identified as
true negatives is typically much larger compared to the number of identified
true hits.

###  3.3. Generality

In this section, we demonstrate the generality of APRIL in supporting other
queries besides spatial intersection joins between polygon-sets. We first show
how we can use it as an intermediate filter in selection (range) queries.
Then, we discuss its application in spatial within joins. Finally, we discuss
the potential of using APRIL approximations of polygons and raster
approximation of linestrings to filter pairs in polygon-linestring
intersection joins.

####  3.3.1. Selection Queries

Similarly to joins, APRIL can be used in an intermediate filter to reduce the
cost of selection queries. Consider a spatial database system, which manages
polygons and where the user can draw a selection query as arbitrary polygon
$QP$; the objective is to retrieve the data polygons that intersect with the
query polygon $QP$. Assuming that we have pre-processed all data polygons and
computed and stored their APRIL representations, we can process polygonal
selection queries as follows. We first pre-process $QP$ to create its APRIL
approximation. Then, we use the MBR of $QP$ to find fast the data polygons
whose MBR intersects with the MBR of the query (potentially with the help of
an index (Guttman, 1984; Tsitsigkos et al., 2021)). For each such data polygon
$r$, we apply the APRIL intermediate filter for the $(r,QP)$ pair to find fast
whether $r$ is a true negative or a true hit. If $r$ cannot be pruned or
confirmed as a query result, we eventually apply the refinement step.

####  3.3.2. Spatial Within Joins

APRIL can also applied for spatial joins having a within predicate, where the
objective is to find the pairs $(r,s)$, where $r\in R$ and $s\in S$ and $r$ is
within $s$ (i.e., $r$ is completely covered by $s$). In this case, the
intermediate filter performs only 2 of its 3 steps. The AA-join is applied
first to detect whether $r$ and $s$ are disjoint, in which case the pair
should be eliminated. Then, we perform a variant of the AF-join, where the
objective is to find if every interval in the A-list of $r$ is contained in
one interval in the F-list of $s$; if this is true, then $(r,s)$ is guaranteed
to be a within join result and it is reported as a true hit. In the opposite
case, $(r,s)$ is forwarded to the refinement step. We do not apply an FA-join,
because this may only detect whether $s$ is within $r$.

####  3.3.3. Linestring to Polygon Joins

Another interesting question is whether APRIL can be useful for intersection
joins between other spatial data types, besides polygons. The direct answer is
no, since APRIL is designed for voluminous objects. Still, our method can be
useful for the case of joins between polygons and linestrings. A linestring is
a sequence of line segments and it is used to approximate geographic objects
such as roads and rivers. The rasterization of a linestring only gives Partial
cells, as linestrings do not have volume and may not cover a cell entirely. In
addition, as exemplified in Figure 6, linestrings do not really benefit from
merging consecutive cells into intervals, as linestrings that follow the
Hilbert order (or any other fixed space-filling curve) are rare. Hence, it is
more space-efficient to approximate a linestring as a sorted sequence of cell-
IDs (which are guaranteed to be Partial). Having the linestring
approximations, we can evaluate spatial intersection joins between a
collection of polygons and a collection of linestrings, by applying 2 of the 3
steps in the APRIL intermediate filter; namely, (i) a merge-join between the
A-list of the polygon and the cell-ID list of the linestring to find out
whether the pair is a true negative and (ii) a merge-join between the F-list
of the polygon and the cell-ID list of the linestring to find out whether the
pair is a true hit. Algorithm 1 can easily be adapted for polygon-linestring
filtering, by simply changing IntervalJoin($X,Y$) to take a sequence of cell-
IDs $Y$ as treat them as intervals of duration 1.

Figure 6. A linestring’s APRIL approximation size in bytes, if stored as
intervals versus cells.

##  4\. Customization

We have explored a series of optimization and customization options that can
potentially reduce APRIL’s space complexity and improve its performance in
terms of filter effectiveness and speed.

###  4.1. Compression

Recall that the only information that APRIL stores for each polygon is two
interval lists: the A-list and the F-list. The interval lists are essentially
sorted integer arrays, so we can exploit delta encoding and more specialized
lossless compression schemes to reduce their space requirements. Since any of
the AA\- AF\- and FA-join that we may apply on the lists may terminate early
(as soon as an interval overlap is detected), we should go for a compression
scheme that does not require the decompression a list entirely before starting
processing it. In other words, we should be able to perform joins while
decompressing the lists. This way, we may avoid uncompressing the lists at
their entirety and still be able to perform the joins. In view of this, we use
delta encoding, where we store the first value of the list precisely and from
thereon store the differences (gaps) between consecutive numbers.

There are dozens of different compression schemes for gaps between ordered
integers, each with their pros and cons. We chose the Variable Byte (VByte)
method (Cutting and Pedersen, 1990; Thiel and Heaps, 1972), a popular
technique that even though it rarely achieves optimal compression, it is
adequately efficient and really fast (Lemire and Boytsov, 2012). We use the
libvbyte (cruppstahl, 2017) library that has an option for sorted integer list
compression, which matches our case and boosts performance by utilizing delta
encoding.

At the same time, we adapt our interval join algorithm to apply decompression
and join at the same time, i.e., each time it needs to get the next integer
from the list it decompresses its value and adds it to the previous value in
the list.

###  4.2. Partitioning

The accuracy of APRIL as a filter is intertwined with the grid granularity we
choose. A more fine-grained grid results in more Full cells, increasing the
chance of detecting true hits; similarly, empty cells increase, enhancing true
negative detection. However, simply raising the order $N$ is not enough to
improve performance. Increasing $N$ beyond 16 means that a single unsigned
integer is not enough to store a Hilbert curve’s identifier, which range from
$[0,2^{2N}-1]$. For $N=17$ or higher, we would need 8 bytes (i.e., an unsigned
long) to store each interval endpoint, exploding the space requirements and
the access/processing cost.

In view of this, we introduce a partitioning mechanism for APRIL, that divides
the data space into disjoint partitions and defines a dedicated rasterization
grid and Hilbert curve of order $N=16$ to each partition. This increases the
global granularity of the approximation, without using long integers, while
giving us the opportunity to define smaller partitions for denser areas of the
map for which a finer granularity is more beneficial. Partitioning is done
considering all datasets/layers of the map. That is, the same space
partitioning is used for all datasets that are joined together. The contents
of each partition are all objects that intersect it; hence, the raster area of
the partition is defined by the MBR of these objects and may be larger than
the partition, as shown in the example of Figure 7. APRIL approximations are
defined based on the raster area of the partition. The spatial join is then
decomposed to multiple joins, one for each spatial partition. Duplicate join
results are avoided at the filter step of the join (MBR-join) as shown in
(Dittrich and Seeger, 2000; Tsitsigkos et al., 2019) .

Figure 7. Example of a partition $P$, a group of polygons in it and $P$’s
raster area with granularity order $N=8$.

###  4.3. Different Granularity

If we use the same (fine) grid to rasterize all polygons, the APRIL
approximations of large polygons may contain too many intervals, slowing down
the intermediate filter. We can create approximations using a different order
$N$ of the Hilbert curve for different datasets, based on the average sizes of
their contents. There is a trade-off between memory and performance, since an
order lower than $16$ means fewer intervals and thus lower memory requirements
and complexity, but also means reduced APRIL accuracy.

When joining two APRIL approximations of different order, we need to adjust
one of the two interval lists so that it can be joined with the other. For
this, we scale down the list with the highest order. Specifically, before
comparing two intervals $a=[a_{start},a_{end})$ and $b=[b_{start},b_{end})$ at
orders $N$ and $L$ respectively, where $N>L$, the highest order interval $a$
should be right shifted by $n=|N-L|\times 2$ bits, to form a transformed
interval $a^{\prime}$, as follows:

(1) $a^{\prime}=[a_{start}>>n,(a_{end}-1)>>n]$

Right shifting creates intervals in a more coarse-grained grid and thus, they
may represent larger areas than the original. Therefore, this formula works
only for A-intervals, since there is no guarantee that a Full interval at
order $N$ will also be Full at order $L$. For this reason, in Algorithm 1, we
perform only one of the AF\- and FA\- joins, using the F-list of the coarse
approximation (which is not scaled down). This has a negative effect on the
filter’s effectiveness, as a trade-off for the coarser (and smaller) APRIL
approximations that we may use for large polygons.

##  5\. APRIL Approximation Construction

In this section, we present two methods for the construction of a polygon’s
APRIL approximation. In Section 5.1 we present a rasterization approach that
efficiently finds the cells that intersect an input polygon and their types,
based on previous research on polygon rasterization, and then sorts them to
construct the A\- and F-interval lists. In Section 5.2, we propose a more
efficient approach tailored for APRIL, which avoids classifying all cells, but
directly identifies the intervals and constructs the A\- and F-interval lists.

###  5.1. Efficient Graphics-Inspired Rasterization

Previous raster-based filters (Georgiadis and Mamoulis, 2023; Zimbrao and de
Souza, 1998) require the classification of each cell to Full, Strong, Weak, or
Empty, based on the percentage of the cell covered by the original polygonal
geometry. For this, they apply an algorithm that involves numerous polygon
clippings and polygonal area computations, at a high cost. On the other hand,
to define a APRIL approximation, we only need to identify the cells which are
partially or fully covered by the input polygon’s area. Inspired by
rasterization techniques in the graphics community, we propose a polygon
rasterization technique which involves two stages. Firstly, we compute the
Partial cells, which essentially form the boundary of the polygon in the grid.
Next, we compute the Full cells using the previously-computed boundary cells.

Identifying the Partial cells is closely related to the pixel drawing problem
in graphics that involves detecting which cells to “turn on” to draw a target
line. While Bresenham’s algorithm (Bresenham, 1965) is a popular and fast
pixel drawing algorithm, it approximates a line segment by turning on a
minimal amount of cells and may thus not detect all intersected cells. In
contrast, the Digital Differential Analyzer (DDA) method (Museth, 2014) is
slower, but identifies correctly and completely all intersected cells. To
detect the Partial cells, we use an efficient variant of DDA (Amanatides and
Woo, 1987) that uses grid traversal. We execute the grid traversal for each
edge of the polygon and store the IDs of the identified Partial cells in a
list. The leftmost grid in Figure 8 shows the Partial cells detected by the
grid traversal algorithm for the polygon drawn in the figure.

Next, to identify the Full cells, a naive approach would be to sweep the grid
in each line, starting from the polygon’s leftmost Partial cell, and “fill”
the grid until reaching another Partial cell. Instead, we use a more efficient
technique, called flood fill (Smith, 1979), which is commonly used to color or
“fill” a closed area in an image. The classic flood fill algorithm first
selects an unlabeled cell that is guaranteed to be within the polygon, called
seed. Then, it traverses all neighboring cells of the seed until it finds the
boundaries of the closed area, classifying the encountered cells as fully
covered. We implemented a variant of this algorithm which minimizes the number
of point-in-polygon tests required to identify whether a cell is inside or
outside the polygon. Specifically, we iterate through the cells of the
polygon’s MBR area. If a cell $c$ has not been labeled yet (e.g., as Partial),
we perform a point-in-polygon check from $c$’s center. If the cell $c$ is
found to be inside the polygon, $c$ is marked as Full and we perform a flood
fill using $c$ as the seed, stopping at labeled cells, and label all
encountered unchecked cells as Full. If the cell $c$ is found to be outside
the polygon, $c$ is marked as Empty and we perform flood fill to mark Empty
cells. The algorithm repeats as long as there are unchecked cells to flood
fill from. This reduces the number of point-in-polygon tests that need to be
performed, as it suffices to perform a single test for each contiguous region
in the grid with Full or Empty cells.

Figure 8. The flood fill algorithm, performing 3 iterations with different
seeds c to completely fill all unchecked cells.

Figure 8 illustrates the complete flood fill process for an example polygon.
The unchecked cells form three contiguous regions bounded by Partial cells,
two of them being outside the polygon and one inside. Instead of looking for
cells within the polygon to flood fill starting from them, it is faster to
fill both the inside and outside of the polygon (marking cells as Full and
Empty, respectively), as the number of point-in-polygon tests is minimized.

After all Partial and Full cells have been identified, the algorithm merges
consecutive cell identifiers into intervals to create the A\- and F-lists that
form the APRIL approximation.

###  5.2. One-Step Intervalization

The approach described in the previous section identifies the types (Partial,
Full, Empty) of all cells that intersect the MBR of the input polygon. For
polygons which are relatively large and their MBRs define a large raster area
this can be quite expensive. We propose an alternative approach that
identifies the F-intervals of the APRIL approximation efficiently and directly
uses them to identify the A-intervals that include them in one step, without
the need to identify the types of all individual cells in them.

As in Section 5.1, we first apply DDA (Amanatides and Woo, 1987) to detect the
Partial cells and sort them in Hilbert order. An important observation is that
“gaps” between nonconsecutive identifiers in the sorted Partial cells list,
indicate candidate Full intervals on the Hilbert curve. Figure 9 illustrates
how these gaps are formed for an example polygon. Identifying the first cell
$c$ of each candidate interval as Full or Empty, through a point-in-polygon
(PiP) test, is enough to label the whole interval as Full or Empty,
respectively. In the figure, the first “gap” interval is $[7,8)$ containing
just cell $7$, which can be marked empty after a PiP test. From all “gap”
intervals those marked in bold (i.e., 32-34 = $[32,35)$ and 52-54 = $[52,55)$)
are Full intervals and can be identified as such by a PiP test at their first
cell (i.e., $32$ and $52$, respectively).

Figure 9. Example of the intervals/gaps for a set of Partial cells. Whether a
gap will be labeled as Full or Empty, depends on the outcome of the PiP test.

Additionally, we can skip some of these PiP tests by checking all adjacent
cells (north, south, west, east) of the first cell $c$ with smaller
identifiers than $c$; if any of them is Full or Empty, we can also give the
same label to the candidate interval, as it should exist in the same
inner/outer area of the raster image. For example, in Figure 9, when the
algorithm moves to identify the interval $[52,55)$, it can detect that its
first cell $52$ is adjacent to another Full cell with smaller order (cell
$33$), that has been previously identified. Thus, the interval $[52,55)$
exists in the same inner area as cell $33$ and it inherits its label (Full),
without performing another PiP test for it. In this example, a total of 5 PiP
tests will be performed, for the intervals that start with the cells
$7,13,30,32$ and $42$, instead of $11$ PiP tests that would be performed
otherwise, if we did not take into consideration the neighboring cells.

Algorithm 2 is a pseudocode for the one-step intervalization process, which
takes as input the sorted Partial cells list $P$ computed by DDA. The
algorithm creates the A-list, F-list of the polygon in a single loop through
$P$. In a nutshell, the algorithm keeps track of the starting point of every
A-interval and when an empty gap is identified, the algorithm “closes” the
current A-interval and starts the next one from the next Partial cell in the
list. On the other hand, Full intervals start with the identifier of the cell
that is right after the last Partial cell of a consecutive sequence and end
before the next Partial cell in order.

In details, Algorithm 2, starting from the first cell $p$ in $P$, keeps track
of the starting cell-ID $Astart$ of the current A-interval; while the next
cell $p+1$ in Hilbert order is also in $P$ (Lines 4–10) the current A-interval
is expanded. If the next cell $c=p+1$ is not partial, it is the starting cell
of a candidate F-interval. We first apply function $CheckNeighbors(c)$ to find
whether there exists an adjacent cell of $c$ which is part of a $FULL$ or
$EMPTY$ interval. Specifically, for cell $c$ and a neighbor $n$, we first
check whether $n<c$ (if not, $n$ is either Partial or unchecked); if yes, we
binary-search $P$ to check whether $n$ is a $P$-cell. If not, we apply a
special binary search method on the current F-list to find out whether $n$ is
part of an interval in it. If we find $n$ as part of an F-interval, then $c$
is definitely a Full cell. If we do no find $n$, then $c$ is definitely an
Empty cell because $n<c$ and $n$ is not Partial. If for all neighbors $n$ of
$c$, either $n>c$ or $n$ is Partial, then we cannot determine the type of $c$
based on the current data, so we perform a PiP test to determine $c$’s type
(i.e., Full or Empty). If $c$ is Full, then we know that the entire interval
$[c,p)$ is $FULL$ and append it to the F-list (Line 16). Otherwise ($c$ is
Empty), $c$ is the end of the current A-interval, so the interval is added to
the A-list and the start of the next A-interval is set to the next Partial
cell $p$. The algorithm continues until the list $P$ of partial cells is
exhausted and commits the last A-interval (Line 23).

1:Sorted Partial cell array $P$

2:function OneStepIntervalization($P$)

3: $i\leftarrow 0$ $\triangleright$ current position in array $P$

4: $Astart\leftarrow P_{i}$; $p\leftarrow P_{i}$ $\triangleright$ cell-IDs of
current $A$-interval and partial cell

5: while $i<|P|$ and $p+1=P_{i+1}$ do $\triangleright$ while next cell is
partial

6: $i\leftarrow i+1$

7: $p\leftarrow P_{i}$

8: end while

9: $c\leftarrow p+1$ $\triangleright$ next uncertain cell

10: $i\leftarrow i+1$; $p\leftarrow P_{i}$ $\triangleright$ next partial cell

11: while $i<|P|$ do

12: $type\leftarrow CheckNeighbors(c)$

13: if $type\neq FULL$ and $type\neq EMPTY$ then $\triangleright$ $type$ is
still uncertain

14: $type\leftarrow PointInPolygon(c)$ $\triangleright$ PiP test gives $FULL$
or $EMPTY$

15: end if

16: if $type=FULL$ then

17: $AppendFullInterval([c,p))$

18: else$\triangleright$ $type$ is $EMPTY$

19: $AppendAllInterval([Astart,c))$ $\triangleright$ current A-interval
finalized

20: $Astart\leftarrow p$ $\triangleright$ start new A-interval

21: end if

22: Execute Lines 4–10 $\triangleright$ go through partial cells until next
gap

23: end while

24: $AppendAllInterval([Astart,P_{i-1}+1))$ $\triangleright$ save last $ALL$
interval

25:end function

Algorithm 2 The One-Step Intervalization algorithm.

Our one-step intervalization approach performs $|P|-1$ PiP tests in the worst-
case, which dominate its cost. Compared to the FloodFill-based approach of
Section 5.1, which explicitly marks and then sorts all Full and Partial cells,
Algorithm 2 is expected to be much faster for polygons which are large
compared to the cell size and include a huge number of Full cells. On the
other hand, flood filling may be a better fit for small polygons with a small
MBR and relatively few Full cells.

Table 4. Statistics of the datasets and space requirements of the data and the
approximations

| T1 | T2 | T3 | O5AF | O6AF | O5AS | O6AS | O5EU | O6EU | O5NA | O6NA | O5SA | O6SA | O5OC | O6OC
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---
# of Polygons | 123K | 2.25M | 3.1K | 72K | 191K | 447K | 622K | 1.9M | 7.1M | 4.0M | 999K | 123K | 228K | 107K | 223K
Avg # of vertices | 25.4 | 31.9 | 2285.0 | 58.9 | 36.3 | 45.3 | 41.9 | 35.1 | 32.1 | 37.6 | 47.5 | 47.5 | 41.6 | 48.4 | 42.7
Avg obj MBR area | 1.77E-04 | 4.03E-05 | 3.95E-01 | 2.03E-03 | 1.23E-03 | 1.03E-03 | 9.98E-04 | 1.25E-04 | 1.19E-04 | 1.11E-04 | 4.40E-04 | 1.34E-03 | 2.37E-03 | 5.00E-04 | 5.27E-04
Geometries size (MB) | 51.1 | 1168.1 | 115.3 | 68.9 | 112.7 | 327.9 | 422.1 | 1120.7 | 3746.2 | 2453.4 | 767.4 | 94.9 | 153.7 | 84.2 | 151.3
MBR size (MB) | 4.4 | 81.1 | 0.1 | 2.6 | 6.9 | 16.1 | 22.4 | 70.9 | 258.4 | 144.8 | 36.0 | 4.5 | 8.2 | 3.9 | 8.1
APRIL size (MB) | 14.4 | 134.0 | 57.2 | 14.2 | 25.4 | 55.2 | 64.5 | 180.3 | 968.0 | 251.0 | 155.0 | 25.4 | 44.4 | 7.3 | 15.0
APRIL-C size (MB) | 6.6 | 75.3 | 16.0 | 5.1 | 10.6 | 23.3 | 28.6 | 84.8 | 406.5 | 138.0 | 62.4 | 9.2 | 16.7 | 3.8 | 7.8
RI size (MB) | 19.5 | 138.2 | 968.7 | 18.6 | 55.7 | 57.5 | 109.8 | 180.9 | 942.9 | 238.1 | 213.5 | 31.2 | 143.4 | 14.2 | 39.3
RA size (MB) | 1100.0 | 20000.0 | N/A | 617.2 | 1700.0 | 3700.0 | 5700.0 | 342.2 | 11400.0 | 6200.0 | 1500.0 | 1100.0 | 2100.0 | 898.7 | 2000.0
5C-CH size (MB) | 28.7 | 705.4 | 1.6 | 18.5 | 46.6 | 117.8 | 159.4 | 515.4 | 1700.0 | 1200.0 | 257.7 | 30.4 | 52.9 | 28.8 | 57.7

|  |  |
---|---|---|---
|  |  |
(a) T1 $\Join$ T2 | (b) T1 $\Join$ T3
|  |  |
(a) O5AF $\Join$ O6AF | (b) O5AS $\Join$ O6AS
|  |  |
(a) O5EU $\Join$ O6EU | (b) O5NA $\Join$ O6NA
|  |  |
(a) O5SA $\Join$ O6SA | (b) O5OC $\Join$ O6OC
Figure 10. Filter effectiveness and spatial join cost for various intermediate
filters.

##  6\. Experimental Analysis

We assess the performance of our proposed APRIL method, by experimentally
comparing it with previously proposed polygon approximations for intermediate
filtering of spatial joins. These include the combined use of 5-Corner and
Convex Hull (5C+CH) (as proposed in (Brinkhoff et al., 1994)), Raster
Approximation (RA) (Zimbrao and de Souza, 1998), and the state-of-the-art
Raster Intervals (RI) (Georgiadis and Mamoulis, 2023). We also included a
baseline approach (None), which does not apply an intermediate filter between
the MBR-join and the refinement step. For RA, we set the grid resolution to
$K=750$ cells, except for a few datasets where we use $K=100$, due to memory
constraints. The MBR filter of the spatial join pipeline was implemented using
the algorithm of (Tsitsigkos et al., 2019). The refinement step was
implemented using the Boost Geometry library (Boost, [n. d.]) and its
functions regarding shape intersection. All code was written in C++ and
compiled with the -O3 flag. The experiments were run on a machine with a
3.6GHz Intel i9-10850k and 32GB RAM, running Linux.

###  6.1. Datasets

We used datasets from SpatialHadoop’s (SpatialHadoop, 2015) collection. T1,
T2, and T3 represent landmark, water and county areas in the United States
(conterminous states only). We also used two Open Street Maps (OSM) datasets
(O5 and O6) that contain lakes and parks, respectively, from all around the
globe. We grouped objects into continents and created 6 smaller datasets
representing each one: Africa (O5AF, O6AF), Asia (O5AS, O6AS), Europe (O5EU,
O6EU), North America (O5NA, O6NA), Oceania (O5OC, O6OC) and South America
(O5SA, O6SA). From all datasets, we removed any non-polygonal objects as well
as multi-polygons and self-intersecting polygons. The first three rows of
Table 4 show statistics about the datasets. We conducted spatial joins only
between pairs of datasets that cover the same area (i.e., T1 $\Join$ T2, T1
$\Join$ T3, O5AF $\Join$ O6AF, etc.).

###  6.2. Comparative Study

In the first set of experiments, we compare APRIL with other intermediate
filters in terms of space complexity, filter effectiveness, and filter cost.
For all experiments, we created APRIL and RI using a single partition (i.e.,
the map of the two datasets that are joined in each case), rasterized on a
$2^{16}\times 2^{16}$ grid. We used a fixed order (AA-, AF-, FA-) for the
interval joins of APRIL, as shown in Algorithm 1.

####  6.2.1. Space Complexity

Table 4 shows the total space requirements of the object approximations
required by each intermediate filter, for each of the datasets used in our
experiments. APRIL and APRIL-C refer to the uncompressed and compressed
version of APRIL, respectively. As a basis of comparison we also show the
total space required to store the exact geometries of the objects and their
MBRs. In most cases, APRIL has the lowest space requirements compared to all
other filters. Notably, for most datasets, the compressed APRIL approximations
have similar space requirements as the object MBRs, meaning that we can keep
them in memory and use them in main-memory spatial joins (Nobari et al., 2017)
directly after the MBR-join step, without incurring any I/O.

####  6.2.2. Performance in Spatial Intersection Joins

We evaluate APRIL (both compressed and uncompressed version), 5C+CH, RA, and
RI, on all join pairs, in Figure 10. We compare their ability to detect true
hits and true negatives, their computational costs as filters, and their
impact to the end-to-end cost of the spatial join.

Filter Effectiveness APRIL and RI have the highest filter effectiveness among
all approximations across the board. APRIL’s true hit ratio is slightly
smaller compared to that of RI because APRIL fails to detect the (rare) pairs
of polygons which only have Strong-Strong common cells. However, this only
brings a marginal increase in the refinement step’s cost, at the benefit of
having a faster and more space-efficient filter. In O5AS $\Join$ O6AS and O5OC
$\Join$ O6OC, APRIL and RI have marginally lower true hit ratio compared to
RA; however, in these cases their true negative ratio is much higher than that
of RA. The least effective filter is 5C+CH, mainly due to its inability to
detect true hits.

Intermediate Filter cost 5C+CH are simple approximations (a few points each),
therefore the corresponding filter is very fast to apply. Hence, 5C+CH has the
lowest cost for most joins. Notably, APRIL has a filtering cost very close to
that of 5C+CH and sometimes even lower. This is due to APRIL’s ability to
model a raster approximation as two sequences of integers, which are processed
by a sequence of efficient merge-join algorithms. On the other hand, the
application of the RI filter is more expensive because, besides the interval
join, it requires the alignment and bitwise $AND$ing of the interval bit-
codes. As a result, APRIL is 3.5-8.5 times faster as an intermediate filter
compared to RI. Even though 5C+CH is the fastest filter to apply, it has poor
filtering performance, which negatively affects the total join cost (last
column), whereas APRIL is very fast and very effective at the same time. A
comparison between the filter costs of APRIL and APRIL-C reveals that
decompressing the interval lists while performing the joins in APRIL-C only
brings a small overhead, making compression well worthy, considering the
significant space savings it offers (see Table 4). The decompression cost is
significant only in T1 $\Join$ T3, because T3’s A-lists and F-lists are quite
long. Still, even in this case, APRIL-C is much faster than RI.

Refinement cost The refinement cost is intertwined with the percentage if
indecisive pairs. The detection of fewer candidate pairs as true hits or true
negatives leads to a higher refinement workload; this is why APRIL and RI
result in the lowest refinement cost, compared to the rest of the
approximations.

Overall cost APRIL reduces the overall cost of end-to-end spatial joins up to
3 times compared to the state-of-the-art RI intermediate filter, while also
achieving a speedup of 3.23x-25x against the rest of the approximations.
Adding the APRIL intermediate filter between the MBR-filter and the refinement
step reduces the spatial join cost by 7x-28x. APRIL’s high filtering
effectiveness, low application cost, and low memory requirements render it a
superior approximation for filtering pairs in spatial intersection join
pipelines.

####  6.2.3. Performance in other queries

Next, we evaluate the performance of APRIL in other queries, besides spatial
intersection joins. We start with selection queries of arbitrary shape (see
Section 3.3.1). For this experiment, we sampled 1000 polygons from T3 and
applied them as selection queries on T1 and T2, simulating queries of the
form: find all landmark areas (T1) or water areas (T2) that intersect with a
given US county (T3). As Table 5 shows, compared to RI, APRIL achieves a
3.5x-4x speedup in the total query cost.

Table 5. APRIL vs. RI (polygonal range queries).

| True hits | True negatives | Indecisive | Int. Filter (s) | Refinement (s) | Total (s)
---|---|---|---|---|---|---
| 1000 T3 queries against T1
RI | 69.28% | 28.60% | 2.12% | 0.52 | 0.10 | 0.64
APRIL | 69.27% | 28.60% | 2.13% | 0.06 | 0.10 | 0.18
| 1000 T3 queries against T2
RI | 68.46% | 29.87% | 1.67% | 9.26 | 1.58 | 11.07
APRIL | 68.46% | 29.87% | 1.67% | 1.02 | 1.58 | 2.84

Next, we compare all methods in spatial within joins, where the objective is
to find pairs $(r,s)$ such that $r$ is within $s$ (see Section 3.3.2). As
Table 6 shows, APRIL again achieves the best performance, due to its extremely
low filtering cost. APRIL is even faster than 5C+CH, because 5C+CH performs
two polygon-in-polygon tests which are slower compared to a polygon
intersection test.

Table 6. Performance of filters (spatial within joins)

| True hits | True negatives | Indecisive | Int. Filter (s) | Refinement (s) | Total (s)
---|---|---|---|---|---|---
| T2 $\Join$ T1 (Tiger water in landmark areas)
None | 0.00% | 0.00% | 100.00% | 0.00 | 3.61 | 3.64
5C+CH | 0.00% | 34.71% | 65.29% | 0.10 | 1.33 | 1.46
RA | 13.48% | 29.18% | 57.34% | 0.14 | 1.11 | 1.28
RI | 18.48% | 59.46% | 22.06% | 0.20 | 0.48 | 0.71
APRIL | 18.48% | 59.42% | 22.11% | 0.05 | 0.49 | 0.58
| T1 $\Join$ T3 (Tiger landmark in county areas)
None | 0.00% | 0.00% | 100.00% | 0.00 | 20.14 | 20.19
5C+CH | 0.00% | 20.72% | 79.28% | 0.37 | 14.02 | 14.44
RA | 44.35% | 14.29% | 41.36% | 0.51 | 8.26 | 8.82
RI | 68.05% | 28.13% | 3.82% | 1.56 | 0.80 | 2.41
APRIL | 68.05% | 28.13% | 3.82% | 0.21 | 0.80 | 1.06
| T2 $\Join$ T3 (Tiger water in county areas)
None | 0.00% | 0.00% | 100.00% | 0.00 | 383.49 | 384.23
5C+CH | 0.00% | 22.17% | 77.83% | 7.70 | 274.54 | 282.98
RA | 42.50% | 15.25% | 42.25% | 9.53 | 165.50 | 175.77
RI | 67.36% | 29.88% | 2.75% | 27.08 | 12.22 | 40.04
APRIL | 67.36% | 29.88% | 2.75% | 3.47 | 12.22 | 16.43

Finally, we test the effectiveness of APRIL in polygon-linestring joins, as
described in Section 3.3.3. For this experiment, we join the polygon sets T1,
T2, and T3 with dataset T8 (from the same collection), which contains 16.9M
linestrings (roads in the United States), each having 20.4 vertices on
average. In this comparison, we do not include RI and RA, because Strong cell
types cannot be used to detect true hits. Table 7 compares APRIL with 5C+CH
and the skipping of an intermediate filter (None). 5C+CH only detects true
negatives (in the case where the 5C+CH approximations do not intersect). APRIL
outperforms 5C+CH by at least three times in total join time and by orders of
magnitude in T3 $\Join$ T8, where it can identify the great majority of join
results as true hits.

Table 7. Polygon-linestring spatial intersection joins.

| True hits | True negatives | Indecisive | Int. Filter (s) | Refinement (s) | Total (s)
---|---|---|---|---|---|---
| T1 $\Join$ T8 (Tiger landmarks and roads)
None | 0.00% | 0.00% | 100.00% | 0.00 | 27.82 | 28.25
5C+CH | 0.00% | 45.24% | 54.76% | 1.07 | 15.99 | 17.49
APRIL | 12.70% | 55.01% | 32.29% | 0.93 | 3.82 | 5.18
| T2 $\Join$ T8 (Tiger water areas and roads)
None | 0.00% | 0.00% | 100.00% | 0.00 | 238.91 | 241.59
5C+CH | 0.00% | 68.13% | 31.87% | 6.24 | 90.60 | 99.52
APRIL | 0.08% | 90.22% | 9.71% | 5.58 | 19.92 | 28.17
| T3 $\Join$ T8 (Tiger county areas and roads)
None | 0.00% | 0.00% | 100.00% | 0.00 | 2546.48 | 2543.37
5C+CH | 0.00% | 22.79% | 77.21% | 16.21 | 1855.63 | 1878.73
APRIL | 66.25% | 30.77% | 2.98% | 25.64 | 58.23 | 90.77

###  6.3. Optimizations and Customizations

####  6.3.1. Join Order

So far the interval joins in APRIL have been applied in a fixed order: AA, AF,
and FA. As discussed in Section 3.2, the joins can be performed in any order.
Table 8 tests different join orders for T1 $\Join$ T2 and T1 $\Join$ T3. T1
$\Join$ T2 (like the majority of tested joins) has a high percentage of true
negatives, so the original order is the most efficient one (changing the order
of AF and FA does not make a difference). On the other hand, for T1 $\Join$
T3, where the true hits are more, pushing the AA-join at the end is more
beneficial. Since knowing the number (or probability) of true negatives and
true hits a priori is impossible and because the join order does not make a
big difference in the efficiency of the filter (especially to the end-to-end
join time), we suggest using the fixed order, which is the best one in most
tested cases. In the future, we investigate the use of data statistics and/or
object MBRs to fast guess a good join order on an object pair basis.

Table 8. Join order effect on APRIL filter cost.

Join Order | True hits | True negatives | Indecisive | Int. Filter (s)
---|---|---|---|---
| T1 $\Join$ T2
AA-AF-FA | 24.29% | 59.42% | 16.29% | 0.0505
AA-FA-AF | 24.29% | 59.42% | 16.29% | 0.0501
AF-FA-AA | 24.29% | 59.42% | 16.29% | 0.0585
FA-AF-AA | 24.29% | 59.42% | 16.29% | 0.0601
| T1 $\Join$ T3
AA-AF-FA | 69.84% | 28.13% | 2.03% | 0.1872
AA-FA-AF | 69.84% | 28.13% | 2.03% | 0.1891
AF-FA-AA | 69.84% | 28.13% | 2.03% | 0.1737
FA-AF-AA | 69.84% | 28.13% | 2.03% | 0.1773

####  6.3.2. Partitioning

Tables 9 and 10 illustrate the effect of data partitioning (Section 4.2) on
the effectiveness, query evaluation time, and space requirements of APRIL
approximations. A higher number of partitions means finer-grained grids per
partition and thus, more intervals per polygon (i.e., more space is required).
Even though this reduces the amount of inconclusive cases, it can slow down
the intermediate filter, since more intervals need to be traversed per
candidate pair. For example, T1 $\Join$ T3 has already a small percentage of
inconclusive pairs, so partitioning may not bring a significant reduction in
the total join time. On the other hand, for joins with high inconclusive
percentage, such as O5AS $\Join$ O6AS, partitioning can greatly reduce the
total cost. In summary, partitioning comes with a time/space tradeoff.

Table 9. # partitions per dimension effect on join time.

# | Indecisive | Int. Filter (s) | Refinement (s) | Total time (s)
---|---|---|---|---
| T1 $\Join$ T2
1 | 16.29% | 0.08 | 0.27 | 0.39
2 | 12.81% | 0.06 | 0.22 | 0.32
3 | 11.36% | 0.08 | 0.20 | 0.30
4 | 10.50% | 0.09 | 0.20 | 0.32
| T1 $\Join$ T3
1 | 2.03% | 0.47 | 0.34 | 0.86
2 | 1.77% | 0.29 | 0.29 | 0.62
3 | 1.67% | 0.37 | 0.27 | 0.69
4 | 1.64% | 0.49 | 0.26 | 0.80
| O5AF $\Join$ O6AF
1 | 26.92% | 0.06 | 0.36 | 0.45
2 | 21.24% | 0.06 | 0.29 | 0.37
3 | 18.26% | 0.07 | 0.25 | 0.34
4 | 16.63% | 0.08 | 0.24 | 0.35
| O5AS $\Join$ O6AS
1 | 30.76% | 0.43 | 7.48 | 8.04
2 | 24.07% | 0.41 | 5.30 | 5.83
3 | 20.52% | 0.46 | 4.34 | 4.93
4 | 18.39% | 0.55 | 3.61 | 4.29
| O5EU $\Join$ O6EU
1 | 34.32% | 5.83 | 30.55 | 38.01
2 | 27.97% | 5.35 | 24.24 | 31.22
3 | 24.84% | 6.06 | 21.55 | 29.24
4 | 22.60% | 6.61 | 19.99 | 28.23
| O5NA $\Join$ O6NA
1 | 22.26% | 3.56 | 24.08 | 28.49
2 | 17.58% | 3.14 | 18.81 | 22.81
3 | 15.68% | 3.65 | 17.13 | 21.64
4 | 14.45% | 4.52 | 16.02 | 21.40
| O5SA $\Join$ O6SA
1 | 25.80% | 0.17 | 1.44 | 1.66
2 | 20.74% | 0.14 | 1.21 | 1.39
3 | 18.39% | 0.17 | 1.12 | 1.33
4 | 17.03% | 0.20 | 1.07 | 1.30
| O5OC $\Join$ O6OC
1 | 24.42% | 0.10 | 1.51 | 1.65
2 | 18.89% | 0.12 | 1.09 | 1.25
3 | 16.17% | 0.14 | 0.95 | 1.13
4 | 14.65% | 0.16 | 0.88 | 1.08

Table 10. # of partitions per dim. effect on APRIL size (MB).

# | T1 | T2 | T3 | O5AF | O6AF | O5AS | O6AS | O5EU | O6EU | O5NA | O6NA | O5SA | O6SA | O5OC | O6OC
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---
1 | 14.4 | 134.0 | 57.2 | 14.2 | 25.4 | 55.2 | 64.5 | 180.3 | 968.0 | 251.0 | 155.0 | 25.4 | 44.4 | 7.3 | 15.0
2 | 26.1 | 236.3 | 112.0 | 29.2 | 49.2 | 106.9 | 124.2 | 336.9 | 1900.0 | 453.4 | 311.8 | 51.5 | 86 | 14.3 | 49.2
3 | 37.1 | 352.6 | 166.7 | 44.7 | 74.2 | 164.0 | 188.3 | 492.5 | 2800.0 | 654.2 | 459.6 | 76.9 | 129.8 | 35.2 | 76.3
4 | 47.2 | 465.9 | 224.9 | 61.4 | 99.5 | 219.1 | 255.1 | 653.0 | 3700.0 | 875.1 | 619.0 | 104.2 | 172.3 | 49.1 | 107.7

####  6.3.3. Different Granularity

As discussed in Section 4.3, we can define and use APRIL at lower granularity
than $N=16$ for one or both datasets, trading filter effectiveness for space
savings. In Table 11, we study the effect of reducing $N$ for T3 in T1 $\Join$
T3. The size of T3’s APRIL approximations halves every time we decrease $N$ by
one. The filter time also decreases, due to the reduced amount of intervals
from T3 in the interval joins. However, the percentage of indecisive pairs
increases, raising the refinement cost. $N=15$ is the best value for T3,
because it achieves the same performance as $N=16$, while cutting the space
requirements in half.

Table 11. Join between T1 (order 16) and T3 (order $N$).

$N$ | True hits | True negs. | Indecisive | Int. Filter (s) | Refinement (s) | Total (s) | T3 size (MB)
---|---|---|---|---|---|---|---
16 | 69.84% | 28.13% | 2.03% | 0.19 | 0.33 | 0.57 | 57.2
15 | 69.63% | 27.85% | 2.52% | 0.13 | 0.41 | 0.59 | 28.3
14 | 69.18% | 27.46% | 3.36% | 0.11 | 0.54 | 0.70 | 14.0
13 | 68.39% | 26.86% | 4.75% | 0.09 | 0.78 | 0.92 | 6.9
12 | 66.63% | 25.70% | 7.67% | 0.09 | 1.23 | 1.37 | 3.4

###  6.4. APRIL Construction Cost

We now evaluate the APRIL construction techniques that we have proposed in
Section 5, comparing them with the rasterization method used in previous work
(Zimbrao and de Souza, 1998; Georgiadis and Mamoulis, 2023) that employs
polygon clipping and polygon-cell intersection area computations. Table 12
shows the time taken to compute the APRIL approximations of all polygons in
each dataset (for $N=16$), using (i) the rasterization+intervalization
approach of (Georgiadis and Mamoulis, 2023), after unifying Strong and Weak
cells, (ii) the FloodFill approach tailored for APRIL presented in Section
5.1, and (iii) two versions of our novel OneStep intervalization approach
(Section 5.2): one that performs a point-in-polygon (PiP) test for each first
cell $c$ of a candidate Full interval and one that checks the Neighbors of $c$
before attempting the PiP test.

Table 12. Total construction cost (sec) for all datasets. Dataset | (Georgiadis and Mamoulis, 2023) | FloodFill | OneStep (PiPs) | OneStep (Neighbors)
---|---|---|---|---
T1 | 143.62 | 3.90 | 3.74 | 2.19
T2 | 601.67 | 28.05 | 33.76 | 23.43
T3 | 9919.06 | 265.72 | 75.40 | 28.33
O5AF | 264.45 | 4.25 | 11.00 | 4.72
O6AF | 468.47 | 13.06 | 5.66 | 4.17
O5AS | 486.86 | 11.69 | 21.28 | 11.78
O6AS | 994.93 | 28.98 | 65.01 | 25.07
O5EU | 1193.71 | 36.08 | 55.79 | 33.71
O6EU | 5493.15 | 172.20 | 243.17 | 156.94
O5NA | 1530.92 | 53.33 | 133.39 | 66.60
O6NA | 1630.29 | 43.40 | 51.79 | 30.71
O5SA | 361.87 | 6.67 | 14.74 | 6.77
O6SA | 1478.05 | 34.56 | 22.86 | 10.52
O5OC | 39.99 | 2.88 | 3.82 | 2.49
O6OC | 113.99 | 9.32 | 20.75 | 8.56

Observe that our OneStep intervalization algorithm employing the Neighbors
check is the fastest approach in most of the cases. OneStep (Neighbors)
applies $40\%-70\%$ fewer PiP tests compared to OneStep (PiPs) that does not
apply the Neighbors check. Only in a few datasets containing relatively small
polygons OneStep (Neighbors) is up to 24% slower than the FloodFill method. On
the other hand, in some datasets containing large polygons (e.g., T3, O6AF,
O6SA) OneStep is up to one order of magnitude faster than FloodFill. Both
methods proposed in Section 5 are orders of magnitude faster compared to
previously applied rasterization techniques (Georgiadis and Mamoulis, 2023)
mainly due to the simplicity of APRIL compared to previous raster-based
intermediate filters (Zimbrao and de Souza, 1998; Georgiadis and Mamoulis,
2023).

Comparison to IDEAL We also compared OneStep to the rasterization technique
used in IDEAL (Teng et al., 2021), as implemented in (Teng, 2021). We modified
IDEAL’s granularity definition formula accordingly to match APRIL’s Hilbert
space grid of order $N=16$. For such high granularity, IDEAL demanded too much
memory for most datasets and crashed, so we could only run it for three
datasets as shown in Table 13. In all these cases, OneStep has 2x-3x lower
cost compared to IDEAL’s rasterization approach.

Table 13. Comparison with IDEAL’s rasterization (Teng et al., 2021). Dataset | One-Step (Neighbors) | IDEAL
---|---|---
T1 | 2.19 | 6.41
O5AF | 4.72 | 10.80
O5OC | 2.49 | 7.13

Applicability of OpenGL rasterization Finally, we have investigated the
applicability of GPU-based rasterization approaches in the construction of
APRIL approximations. For this, we tested an OpenGL implementation that uses a
GPU (NVIDIA GeForce RTX 3060) and follows the approach described in
(Zacharatou et al., 2017) to identify Partial and Full cells of a polygon on a
raster. OpenGL is an API that supports the graphics pipeline to perform
efficient rasterization and drawing of the raster cells (pixels) into a frame
buffer for visualization. In addition to rasterization, APRIL requires the
retrieval of the cells’ Hilbert curve identifiers and cell type information to
create interval lists. Furthermore, OpenGL’s rendering pipeline is designed to
work with triangles, and thus we have to triangulate all our input polygons
before rendering. Finally, the resolution of the frame buffer plays a crucial
role in rasterization accuracy.

The frame buffer ’s resolution must match the desired granularity (i.e.,
$2^{16}\times 2^{16}$) of APRIL approximations. However, OpenGL does not allow
frame buffers to have resolution higher than $2^{15}\times 2^{15}$ pixels, so
APRIL approximations created using OpenGL are destined to have lower filter
effectiveness than if they were created using our CPU-based methods (Section
5).

In addition, in our experiments, we have found that triangulation, which is a
pre-requisite of using OpenGL’s rendering, takes up $66\%$ \- $94\%$ of the
total rasterization time. For example, triangulating the T3 dataset in its
entirety takes around $160$ seconds, which is already about 6x more expensive
than the end-to-end production of the APRIL approximations of all objects in
T3 using our OneStep approach (see Table 12).

Overall, its limitations in setting an appropriate resolution and the high
costs for initializing and postprocessing its rasterization process, make
OpenGL-based APRIL construction suboptimal compared to our CPU-based
algorithms.

##  7\. Related Work

Most previous works on spatial intersection joins (Jacox and Samet, 2007)
focus on the filter step of the join (denoted by MBR-join). They either
exploit the pre-existing indexes (Brinkhoff et al., 1993b; Mamoulis and
Papadias, 2003) or partition the data on-the-fly and perform the join
independently at each partition (Patel and DeWitt, 1996; Nobari et al., 2013;
Tsitsigkos et al., 2019). Each partition-to-partition MBR-join can be
performed in memory with the help of plane-sweep (Brinkhoff et al., 1993b;
Arge et al., 1998).

Intermediate filters Finer (but more space-consuming) approximations have been
proposed to be used in an intermediate filter step that identifies true
negatives and/or true positives, as described in Section 2. The first work in
this direction (Brinkhoff et al., 1994) proposed the use of simple convex
polygons (convex hull and the minimum bounding 5-corner convex polygon (5C)).
Another approach (Sidlauskas et al., 2018) extends the MBR to capture the
empty space around its corners, which may help in the detection of false
positives. Raster approximations of object MBRs have also been suggested, with
a classification of the cells therein based on their coverage by the object
(Zimbrao and de Souza, 1998). Recently, this approach has been improved in
(Georgiadis and Mamoulis, 2023) to (i) apply on a global grid, (ii) represent
the cells as intervals with bitcodes of the cell types, (iii) perform the
intermediate filter as a specialized interval join, as described in Section 2.
A hierarchical raster approximation for window and distance queries was
proposed in (Fang et al., 2008). Raster approximations have also been combined
with vector approximations in (Teng et al., 2021). However, neither (Fang et
al., 2008) nor (Teng et al., 2021) studied the spatial intersection join, for
which the state-of-the-art intermediate filter is RI (Georgiadis and Mamoulis,
2023).

Refinement step Verifying whether two polygons overlap is CPU-intensive,
requiring the application of an intersection detection algorithm between sets
of line segments and two point-in-polygon tests (Brinkhoff et al., 1994). To
speed it up, Brinkhoff et al. (Brinkhoff et al., 1994) suggest decomposing
polygons into sets of trapezoids while (Badawy and Aref, 1999) suggests
alternative polygon decomposition approaches. These techniques are orthogonal
to APRIL, as they aim to speed up the refinement step, while APRIL reduces the
number of candidate join pairs that require refinement.

Approximate spatial joins The approximate representation of objects and
approximate spatial query evaluation using space-filling curves was first
suggested by Orenstein (Orenstein, 1989). Recent work explores the use of
raster approximations for the approximate evaluation of spatial joins and
other operations (Kipf et al., 2020; Zacharatou et al., 2021; Winter et al.,
2021). RI (Georgiadis and Mamoulis, 2023) and our work are the first to
approximate polygon rasterizations as intervals for exact spatial query
evaluation.

Spatial joins on GPUs The widespread availability of programmable GPUs has
inspired several research efforts that leverage GPUs for spatial joins (Sun et
al., 2003; Aghajarian et al., 2016; Aghajarian and Prasad, 2017; Liu et al.,
2019; Liu and Puri, 2020). Sun et al. (Sun et al., 2003) accelerated the join
refinement step by incorporating GPU rasterization as an intermediate filter.
This filter identifies _only true negatives_ using a low resolution, and has
thus limited pruning effectiveness. Aghajarian et al. (Aghajarian et al.,
2016; Aghajarian and Prasad, 2017) proposed a GPU approach to process point-
polygon and polygon-polygon joins for datasets that can be accommodated in GPU
memory. Liu et al. (Liu et al., 2019; Liu and Puri, 2020) also proposed GPU-
accelerated filters to reduce the number of refinements. These filters
(Aghajarian et al., 2016; Aghajarian and Prasad, 2017; Liu et al., 2019; Liu
and Puri, 2020), in contrast to APRIL, _do not identify true hits_ , but
rather focus on finding the intersection points between a candidate pair.
Furthermore, the above approaches (Aghajarian et al., 2016; Aghajarian and
Prasad, 2017; Liu et al., 2019; Liu and Puri, 2020) do not involve
rasterization and rely on CUDA, which is exclusive to NVIDIA GPUs. A recent
line of work (Zacharatou et al., 2017; Doraiswamy and Freire, 2020; Zacharatou
et al., 2021; Doraiswamy and Freire, 2022) proposes to use the GPU
rasterization pipeline as an integral component of spatial query processing.
Doraiswamy et al. (Doraiswamy and Freire, 2020, 2022) introduced a spatial
data model and algebra that is designed to exploit modern GPUs. Their approach
leverages a data representation called _canvas_ , which stores polygons as
collections of pixels. The canvas includes a flag that differentiates between
pixels that lie on the boundary of the polygon and those that are entirely
covered by it. Although current-generation GPUs can handle millions of
polygons at fast frame rates, the evaluation of spatial queries is still
dominated by other costs, such as triangulating polygons and performing I/Os
(Doraiswamy and Freire, 2022).

Scalability in spatial data management The emergence of cloud computing has
led to many efforts to scale out spatial data management (Pandey et al.,
2018b). SJMP (Zhang et al., 2009) is an adaptation of the PBSM spatial join
algorithm (Patel and DeWitt, 1996) for MapReduce. Other spatial data
management systems that use MapReduce or Spark and handle spatial joins
include Hadoop-GIS (Aji et al., 2013), SpatialHadoop (Eldawy and Mokbel,
2015), Magellan (Sriharsha, [n. d.]), SpatialSpark (You et al., 2015), Simba
(Xie et al., 2016), and Apache Sedona (Yu et al., 2019). All the
aforementioned systems focus only on the filter step of spatial joins.

##  8\. Conclusions

We propose APRIL, an approximation technique for polygons, to use as an
intermediate filter in the spatial intersection join pipeline. Compared to
previous approaches (Brinkhoff et al., 1994; Zimbrao and de Souza, 1998;
Georgiadis and Mamoulis, 2023), APRIL is (i) lightweight, as it represents
each polygon by two lists of integers that can be effectively compressed; (ii)
effective, as it typically filters the majority of MBR-join pairs as true
negatives or true positives; and (iii) efficient to apply, as it only requires
at most three linear scans over the interval lists. APRIL is a general
approximation for polygons that can also be used in selection queries, within-
joins and joins between polygons and linestrings. We propose a compression
technique for APRIL and customizations that trade space for filter
effectiveness. Finally, we propose efficient construction techniques for APRIL
approximations, which greatly perform rasterization-based techniques from
previous work. In the future, we plan to explore the integration of APRIL in a
spatial database system, investigate further the problem of interval join
order optimization for APRIL for candidate join pairs, and explore the
effectiveness of APRIL for queries that involve 3D objects (e.g., polytopes).

## References

  * (1)
  * Aghajarian and Prasad (2017) Danial Aghajarian and Sushil K. Prasad. 2017.  A Spatial Join Algorithm Based on a Non-uniform Grid Technique over GPGPU. In _Proceedings of the 25th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, GIS 2017, Redondo Beach, CA, USA, November 7-10, 2017_ , Erik G. Hoel, Shawn D. Newsam, Siva Ravada, Roberto Tamassia, and Goce Trajcevski (Eds.). ACM, 56:1–56:4.
  * Aghajarian et al. (2016) Danial Aghajarian, Satish Puri, and Sushil K. Prasad. 2016\.  GCMF: an efficient end-to-end spatial join system over large polygonal datasets on GPGPU platform. In _Proceedings of the 24th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, GIS 2016, Burlingame, California, USA, October 31 - November 3, 2016_. ACM, 18:1–18:10.
  * Aji et al. (2013) Ablimit Aji, Fusheng Wang, Hoang Vo, Rubao Lee, Qiaoling Liu, Xiaodong Zhang, and Joel H. Saltz. 2013.  Hadoop-GIS: A High Performance Spatial Data Warehousing System over MapReduce.  _Proc. VLDB Endow._ 6, 11 (2013), 1009–1020.
  * Amanatides and Woo (1987) John Amanatides and Andrew Woo. 1987.  A Fast Voxel Traversal Algorithm for Ray Tracing. In _8th European Computer Graphics Conference and Exhibition, Eurographics 1987, Amsterdam, The Netherlands, August 24-28, 1987, Proceedings_. North-Holland / Eurographics Association.
  * Arge et al. (1998) Lars Arge, Octavian Procopiuc, Sridhar Ramaswamy, Torsten Suel, and Jeffrey Scott Vitter. 1998\.  Scalable Sweeping-Based Spatial Join. In _VLDB’98, Proceedings of 24rd International Conference on Very Large Data Bases, August 24-27, 1998, New York City, New York, USA_ , Ashish Gupta, Oded Shmueli, and Jennifer Widom (Eds.). Morgan Kaufmann, 570–581.
  * Badawy and Aref (1999) Wael M. Badawy and Walid G. Aref. 1999.  On Local Heuristics to Speed Up Polygon-Polygon Intersection Tests. In _ACM-GIS ’99, Proceedings of the 7th International Symposium on Advances in Geographic Information Systems, November 2-6, 1999, Kansas City, USA_. ACM, 97–102.
  * Boost ([n. d.]) Boost. [n. d.].  Boost C++ Libraries.  http://www.boost.org/.
  * Bresenham (1965) Jack Bresenham. 1965\.  Algorithm for Computer Control of a Digital Plotter.  _IBM Syst. J._ 4, 1 (1965), 25–30.
  * Brinkhoff et al. (1993a) Thomas Brinkhoff, Hans-Peter Kriegel, and Ralf Schneider. 1993a.  Comparison of Approximations of Complex Objects Used for Approximation-based Query Processing in Spatial Database Systems. In _Proceedings of the Ninth International Conference on Data Engineering, April 19-23, 1993, Vienna, Austria_. IEEE Computer Society, 40–49.
  * Brinkhoff et al. (1994) Thomas Brinkhoff, Hans-Peter Kriegel, Ralf Schneider, and Bernhard Seeger. 1994.  Multi-Step Processing of Spatial Joins. In _Proceedings of the 1994 ACM SIGMOD International Conference on Management of Data, Minneapolis, Minnesota, USA, May 24-27, 1994_ , Richard T. Snodgrass and Marianne Winslett (Eds.). ACM Press, 197–208.
  * Brinkhoff et al. (1993b) Thomas Brinkhoff, Hans-Peter Kriegel, and Bernhard Seeger. 1993b.  Efficient Processing of Spatial Joins Using R-Trees. In _Proceedings of the 1993 ACM SIGMOD International Conference on Management of Data, Washington, DC, USA, May 26-28, 1993_. ACM Press, 237–246.
  * cruppstahl (2017) cruppstahl. 2017\.  _libvbyte - Fast C Library for 32bit and 64bit Integer Compression_.  https://github.com/cruppstahl/libvbyte
  * Cutting and Pedersen (1990) Douglas R. Cutting and Jan O. Pedersen. 1990.  Optimizations for Dynamic Inverted Index Maintenance. In _SIGIR’90, 13th International Conference on Research and Development in Information Retrieval, Brussels, Belgium, 5-7 September 1990, Proceedings_. ACM, 405–411.
  * Dittrich and Seeger (2000) Jens-Peter Dittrich and Bernhard Seeger. 2000.  Data Redundancy and Duplicate Detection in Spatial Join Processing. In _Proceedings of the 16th International Conference on Data Engineering, San Diego, California, USA, February 28 - March 3, 2000_ , David B. Lomet and Gerhard Weikum (Eds.). IEEE Computer Society, 535–546.
  * Doraiswamy and Freire (2020) Harish Doraiswamy and Juliana Freire. 2020.  A GPU-friendly Geometric Data Model and Algebra for Spatial Queries. In _Proceedings of the 2020 International Conference on Management of Data, SIGMOD Conference 2020, online conference [Portland, OR, USA], June 14-19, 2020_. ACM, 1875–1885.
  * Doraiswamy and Freire (2022) Harish Doraiswamy and Juliana Freire. 2022.  SPADE: GPU-Powered Spatial Database Engine for Commodity Hardware. In _38th IEEE International Conference on Data Engineering, ICDE 2022, Kuala Lumpur, Malaysia, May 9-12, 2022_. IEEE, 2669–2681.
  * Eldawy and Mokbel (2015) Ahmed Eldawy and Mohamed F. Mokbel. 2015.  SpatialHadoop: A MapReduce framework for spatial data. In _31st IEEE International Conference on Data Engineering, ICDE 2015, Seoul, South Korea, April 13-17, 2015_ , Johannes Gehrke, Wolfgang Lehner, Kyuseok Shim, Sang Kyun Cha, and Guy M. Lohman (Eds.). IEEE Computer Society, 1352–1363.
  * Fang et al. (2008) Yi Fang, Marc T. Friedman, Giri Nair, Michael Rys, and Ana-Elisa Schmid. 2008.  Spatial indexing in microsoft SQL server 2008. In _Proceedings of the ACM SIGMOD International Conference on Management of Data, SIGMOD 2008, Vancouver, BC, Canada, June 10-12, 2008_. 1207–1216.
  * Georgiadis and Mamoulis (2023) Thanasis Georgiadis and Nikos Mamoulis. 2023.  Raster Intervals: An Approximation Technique for Polygon Intersection Joins. In _Proceedings of the 2023 ACM SIGMOD International Conference on Management of Data, Seattle, Washington, USA, June_.
  * Guttman (1984) Antonin Guttman. 1984\.  R-Trees: A Dynamic Index Structure for Spatial Searching. In _SIGMOD’84, Proceedings of Annual Meeting, Boston, Massachusetts, USA, June 18-21, 1984_ , Beatrice Yormark (Ed.). ACM Press, 47–57.
  * Hilbert (1891) David Hilbert. 1891\.  Über die stetige Abbildung einer Linie auf ein Flächenstück.  _Mathematische Annalen_ 38, 1 (1891), 459–460.
  * Jacox and Samet (2007) Edwin H. Jacox and Hanan Samet. 2007.  Spatial join techniques.  _ACM Trans. Database Syst._ 32, 1 (2007), 7\.
  * Kipf et al. (2020) Andreas Kipf, Harald Lang, Varun Pandey, Raul Alexandru Persa, Christoph Anneser, Eleni Tzirita Zacharatou, Harish Doraiswamy, Peter A. Boncz, Thomas Neumann, and Alfons Kemper. 2020.  Adaptive Main-Memory Indexing for High-Performance Point-Polygon Joins. In _Proceedings of the 23rd International Conference on Extending Database Technology, EDBT 2020, Copenhagen, Denmark, March 30 - April 02, 2020_. OpenProceedings.org, 347–358.
  * Lemire and Boytsov (2012) Daniel Lemire and Leonid Boytsov. 2012.  Decoding billions of integers per second through vectorization.  _CoRR_ abs/1209.2137 (2012).
  * Liu and Puri (2020) Yiming Liu and Satish Puri. 2020.  Efficient Filters for Geometric Intersection Computations using GPU. In _SIGSPATIAL ’20: 28th International Conference on Advances in Geographic Information Systems, Seattle, WA, USA, November 3-6, 2020_ , Chang-Tien Lu, Fusheng Wang, Goce Trajcevski, Yan Huang, Shawn D. Newsam, and Li Xiong (Eds.). ACM, 487–496.
  * Liu et al. (2019) Yiming Liu, Jie Yang, and Satish Puri. 2019.  Hierarchical Filter and Refinement System Over Large Polygonal Datasets on CPU-GPU. In _26th IEEE International Conference on High Performance Computing, Data, and Analytics, HiPC 2019, Hyderabad, India, December 17-20, 2019_. IEEE, 141–151.
  * Mamoulis and Papadias (2003) Nikos Mamoulis and Dimitris Papadias. 2003.  Slot Index Spatial Join.  _IEEE Trans. Knowl. Data Eng._ 15, 1 (2003), 211–231.
  * Museth (2014) Ken Museth. 2014\.  Hierarchical digital differential analyzer for efficient ray-marching in OpenVDB. In _Special Interest Group on Computer Graphics and Interactive Techniques Conference, SIGGRAPH ’14, Vancouver, Canada, August 10-14, 2014, Talks Proceedings_. ACM, 40:1.
  * Nobari et al. (2017) Sadegh Nobari, Qiang Qu, and Christian S. Jensen. 2017\.  In-Memory Spatial Join: The Data Matters!. In _Proceedings of the 20th International Conference on Extending Database Technology, EDBT 2017, Venice, Italy, March 21-24, 2017_. OpenProceedings.org, 462–465.
  * Nobari et al. (2013) Sadegh Nobari, Farhan Tauheed, Thomas Heinis, Panagiotis Karras, Stéphane Bressan, and Anastasia Ailamaki. 2013.  TOUCH: in-memory spatial join by hierarchical data-oriented partitioning. In _Proceedings of the ACM SIGMOD International Conference on Management of Data, SIGMOD 2013, New York, NY, USA, June 22-27, 2013_. ACM, 701–712.
  * Orenstein (1989) Jack A. Orenstein. 1989\.  Redundancy in Spatial Databases. In _Proceedings of the 1989 ACM SIGMOD International Conference on Management of Data, Portland, Oregon, USA, May 31 \- June 2, 1989_. ACM Press, 295–305.
  * Pandey et al. (2018a) Varun Pandey, Andreas Kipf, Thomas Neumann, and Alfons Kemper. 2018a.  How Good Are Modern Spatial Analytics Systems?  _Proc. VLDB Endow._ 11, 11 (2018), 1661–1673.
  * Pandey et al. (2018b) Varun Pandey, Andreas Kipf, Thomas Neumann, and Alfons Kemper. 2018b.  How Good Are Modern Spatial Analytics Systems?  _Proc. VLDB Endow._ 11, 11 (2018), 1661–1673.
  * Papadakis et al. (2021) George Papadakis, Georgios M. Mandilaras, Nikos Mamoulis, and Manolis Koubarakis. 2021.  Progressive, Holistic Geospatial Interlinking. In _WWW ’21: The Web Conference 2021, Virtual Event / Ljubljana, Slovenia, April 19-23, 2021_. ACM / IW3C2, 833–844.
  * Patel and DeWitt (1996) Jignesh M. Patel and David J. DeWitt. 1996.  Partition Based Spatial-Merge Join. In _Proceedings of the 1996 ACM SIGMOD International Conference on Management of Data, Montreal, Quebec, Canada, June 4-6, 1996_. ACM Press, 259–270.
  * Ray et al. (2014) Suprio Ray, Bogdan Simion, Angela Demke Brown, and Ryan Johnson. 2014.  Skew-resistant parallel in-memory spatial join. In _Conference on Scientific and Statistical Database Management, SSDBM ’14, Aalborg, Denmark, June 30 - July 02, 2014_. ACM, 6:1–6:12.
  * Shinya and Forgue (1991) Mikio Shinya and Marie-Claire Forgue. 1991.  Interference detection through rasterization.  _Comput. Animat. Virtual Worlds_ 2, 4 (1991), 132–134.
  * Sidlauskas et al. (2018) Darius Sidlauskas, Sean Chester, Eleni Tzirita Zacharatou, and Anastasia Ailamaki. 2018.  Improving Spatial Data Processing by Clipping Minimum Bounding Boxes. IEEE Computer Society, 425–436.
  * Smith (1979) Alvy Ray Smith. 1979\.  Tint fill. In _Proceedings of the 6th Annual Conference on Computer Graphics and Interactive Techniques, SIGGRAPH 1979, Chicago, Illinois, USA, August 8-10, 1979_ , Thomas A. DeFanti, Bruce H. McCormick, Bary W. Pollack, Norman I. Badler, and S. H. Chasen (Eds.). ACM, 276–283.
  * SpatialHadoop (2015) SpatialHadoop. 2015\.  _TIGER datasets_.  http://spatialhadoop.cs.umn.edu/datasets.html
  * Sriharsha ([n. d.]) Ram Sriharsha. [n. d.].  Magellan: Geospatial Analytics Using Spark.  https://github.com/harsha2010/magellan.
  * Sun et al. (2003) Chengyu Sun, Divyakant Agrawal, and Amr El Abbadi. 2003\.  Hardware Acceleration for Spatial Selections and Joins. In _Proceedings of the ACM SIGMOD International Conference on Management of Data, San Diego, California, USA_. ACM, 455–466.
  * Teng (2021) Dejun Teng. 2021\.  _IDEAL_.  https://github.com/tengdj/IDEAL
  * Teng et al. (2021) Dejun Teng, Furqan Baig, Qiheng Sun, Jun Kong, and Fusheng Wang. 2021.  IDEAL: a Vector-Raster Hybrid Model for Efficient Spatial Queries over Complex Polygons. In _22nd IEEE International Conference on Mobile Data Management, MDM 2021, Toronto, ON, Canada, June 15-18, 2021_. IEEE, 99–108.
  * Theocharidis et al. (2019) Konstantinos Theocharidis, John Liagouris, Nikos Mamoulis, Panagiotis Bouros, and Manolis Terrovitis. 2019.  SRX: efficient management of spatial RDF data.  _VLDB J._ 28, 5 (2019), 703–733.
  * Thiel and Heaps (1972) Larry H. Thiel and H. S. Heaps. 1972.  Program design for retrospective searches on large data bases.  _Inf. Storage Retr._ 8, 1 (1972), 1–20.
  * Tsitsigkos et al. (2019) Dimitrios Tsitsigkos, Panagiotis Bouros, Nikos Mamoulis, and Manolis Terrovitis. 2019.  Parallel In-Memory Evaluation of Spatial Joins. In _Proceedings of the 27th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, SIGSPATIAL 2019, Chicago, IL, USA, November 5-8, 2019_. ACM, 516–519.
  * Tsitsigkos et al. (2021) Dimitrios Tsitsigkos, Konstantinos Lampropoulos, Panagiotis Bouros, Nikos Mamoulis, and Manolis Terrovitis. 2021.  A Two-layer Partitioning for Non-point Spatial Data. In _37th IEEE International Conference on Data Engineering, ICDE 2021, Chania, Greece, April 19-22, 2021_. IEEE, 1787–1798.
  * Winter et al. (2021) Christian Winter, Andreas Kipf, Christoph Anneser, Eleni Tzirita Zacharatou, Thomas Neumann, and Alfons Kemper. 2021.  GeoBlocks: A Query-Cache Accelerated Data Structure for Spatial Aggregation over Polygons. In _Proceedings of the 24th International Conference on Extending Database Technology, EDBT 2021, Nicosia, Cyprus, March 23 - 26, 2021_. OpenProceedings.org, 169–180.
  * Xie et al. (2016) Dong Xie, Feifei Li, Bin Yao, Gefei Li, Liang Zhou, and Minyi Guo. 2016.  Simba: Efficient In-Memory Spatial Analytics. In _Proceedings of the 2016 International Conference on Management of Data, SIGMOD Conference 2016, San Francisco, CA, USA, June 26 \- July 01, 2016_ , Fatma Özcan, Georgia Koutrika, and Sam Madden (Eds.). ACM, 1071–1085.
  * You et al. (2015) Simin You, Jianting Zhang, and Le Gruenwald. 2015\.  Large-scale spatial join query processing in Cloud. In _CloudDB, ICDE Workshops_. 34–41.
  * Yu et al. (2019) Jia Yu, Zongsi Zhang, and Mohamed Sarwat. 2019.  Spatial data management in apache spark: the GeoSpark perspective and beyond.  _GeoInformatica_ 23, 1 (2019), 37–78.
  * Zacharatou et al. (2017) Eleni Tzirita Zacharatou, Harish Doraiswamy, Anastasia Ailamaki, Cláudio T. Silva, and Juliana Freire. 2017.  GPU Rasterization for Real-Time Spatial Aggregation over Arbitrary Polygons.  _Proc. VLDB Endow._ 11, 3 (2017), 352–365.
  * Zacharatou et al. (2021) Eleni Tzirita Zacharatou, Andreas Kipf, Ibrahim Sabek, Varun Pandey, Harish Doraiswamy, and Volker Markl. 2021.  The Case for Distance-Bounded Spatial Approximations. In _11th Conference on Innovative Data Systems Research, CIDR 2021, Virtual Event, January 11-15, 2021, Online Proceedings_. www.cidrdb.org.
  * Zhang et al. (2009) Shubin Zhang, Jizhong Han, Zhiyong Liu, Kai Wang, and Zhiyong Xu. 2009.  SJMR: Parallelizing spatial join with MapReduce on clusters. In _Proceedings of the 2009 IEEE International Conference on Cluster Computing, August 31 - September 4, 2009, New Orleans, Louisiana, USA_. IEEE Computer Society, 1–8.
  * Zimbrao and de Souza (1998) Geraldo Zimbrao and Jano Moreira de Souza. 1998.  A Raster Approximation For Processing of Spatial Joins. In _VLDB’98, Proceedings of 24rd International Conference on Very Large Data Bases, August 24-27, 1998, New York City, New York, USA_. 558–569.