{'fraction_non_alphanumeric': 0.04301606922126082, 'fraction_numerical': 0.007557831538054035, 'mean_word_length': 4.2398223538119915, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 1, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 4, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Spatial Interpolation-based Learned Index for Range and kNN Queries

A corpus of recent work has revealed that the learned index can improve query performance while reducing the storage overhead. It potentially offers an opportunity to address the spatial query processing challenges caused by the surge in location-based services. Although several learned indexes have been proposed to process spatial data, the main idea behind these approaches is to utilize the existing one-dimensional learned models, which requires either converting the spatial data into one-dimensional data or applying the learned model on individual dimensions separately. As a result, these approaches cannot fully utilize or take advantage of the information regarding the spatial distribution of the original spatial data. To this end, in this paper, we exploit it by using the spatial (multi-dimensional) interpolation function as the learned model, which can be directly employed on the spatial data. Specifically, we design an efficient SPatial inteRpolation functIon based Grid index (SPRIG) to process the range and kNN queries. Detailed experiments are conducted on real-world datasets, and the results indicate that our proposed learned index can significantly improve the performance in comparison with the traditional spatial indexes and a state-of-the-art multi-dimensional learned index.


I. INTRODUCTION
As location-based services (LBS) have been widely deployed and have become highly popular, spatial query processing has attracted considerable interests in the research community. Although several spatial indexes, such as R-tree and k-d tree, have been proposed to facilitate spatial query performance, it is still challenging to process the spatial queries efficiently due to the rapidly growing volume of spatial data. Recently, Kraska et al. [1] suggested substituting the traditional indexes with machine learned based indexes (also called learned index). Since then, several follow-up research projects [2], [3], [4], [5], [6] have shown that the learned index can indeed improve query performance by learned data distribution and query workload patterns.
Typically, there are two main aspects involving a learned index, namely, a learned model and a local search. The former is trained and used to quickly locate the approximate position of a search key, while the latter is responsible for refining the accurate position. Since the latter can be achieved by performing a local binary or exponential search, it is a fundamental but challenging topic to find a reasonable learned model and further employ it as the learned index. Existing learned indexes are constructed based on mainly one of two categories of learned models: machine learning [1] and piecewise linear functions [3]. However, to the best of our knowledge, both of these learned models can be only applied in single dimensional data. As a result, the current spatial learned indexes either transform multi-dimensional data into one-dimensional data before introducing the learned model as a foundation [7], [8] or apply a learned model on every single dimension [6]. For this reason, the question then arises, "Is there a learned model that can be directly applied to spatial (multi-dimensional) data and achieve better performance?" Aiming to address the above-mentioned question, in this paper, we explore how to utilize spatial (two-dimensional) interpolation functions as the learned models to directly predict the position of a spatial search key. Based on this idea, we propose a SPatial inteRpolation functIon based Grid index (SPRIG) to support range and kNN queries over spatial data. In particular, we sample the spatial data to construct an adaptive grid and use the sample data as inputs to fit a spatial interpolation function. Given a spatial search key, first, we can use the fitted spatial interpolation function to predict the approximate position of the key. Then, around the estimated position, we can conduct a local binary search to find the target key. However, it entails a new challenge: how to guarantee that the target key is in the local search range. To address this issue, we introduce the maximum estimation error based error guarantee, which is derived based on the query workload. Furthermore, we propose efficient range and kNN query execution strategies using our proposed index. In these strategies, we take full advantage of the properties of the adaptive grid to facilitate the query executions, and a pivot based filtering technique is introduced to improve the kNN query performance.
We conduct extensive experiments to evaluate our learned index, SPRIG. First, we evaluate five spatial interpolation functions and choose the bilinear interpolation function, which has the best performance and estimation accuracy, as our learned model. Then, we compare SPRIG against the state-ofthe-art multi-dimensional learned index Flood [6], along with a few spatial indexes. The experimental results involving realworld datasets show that: 1) SPRIG outperforms the alternative spatial indexes on range queries and is competitive on kNN queries in terms of execution time. In the best case, SPRIG is 3× faster than Flood with range queries and 9× faster than Flood with kNN queries; 2) SPRIG consumes less storage to achieve a favorable execution performance compared with the traditional indexes. Our evaluations demonstrate that SPRIG can reduce the storage footprint of traditional spatial indexes by orders of magnitude.
The remainder of this paper is organized as follows. In Section II, we discuss the related work. Then, we introduce the spatial interpolation function, error guarantee, and pivot based filtering in Section III. After that, we present our SPRIG in Section IV, followed by performance evaluation in Section V. Finally, we draw our conclusion in Section VI.

II. RELATED WORK
Kraska et al. [1] presented the idea of the learned index, which is based on learning the relationship between keys and their positions in a sorted array. They adopted a machine learning based technique as the learned model and built a recursive model index (RMI), which predicts the position of a search key within a known error bound. Since then, a variety of learned indexes was proposed to handle one-dimensional data. Recently, Tang et al. [2] proposed a scalable learned index XIndex based on RMI, which focuses on handling concurrent writes without affecting the query performance. Very differently, Galakatos et al. [3] exploited the piecewise linear function as the learned model to build a data-aware index FITing-tree that replaces leaf nodes of B+-tree with the learned piecewise linear functions. Unlike FITing-tree, Ferragina et al. [4] introduced a pure learned index PGM-index that does not mix the traditional data structure and learned model. However, their work still focuses on one-dimensional data and uses the existing linear learned model. Naturally, the idea of the learned index has been extended to spatial and multi-dimensional data. Wang et al. [7] proposed a learned index ZM-index for spatial queries. In that work, the authors utilized the Z-order curve to convert two-dimensional data into one-dimensional values, and then applied a machine learning model to predict a key's position on one-dimensional data. Qi et al. [5] refined the idea of ZM-index and built a recursive spatial model index (RSMI). Before applying Z-order curve, their work adopts a rank space-based transformation technique to mitigate the uneven-gap problem. LISA [9] is a disk-based spatial learned index that achieves low storage consumption and I/O cost. In this work, the authors used a mapping function to map spatial keys into one-dimensional values and a monotone shard prediction function, which is similar to the piecewise linear functions, to predict the shard id for a given mapped value. Extending to multi-dimensional data, ML-index [8] is an RMI based learned index. It first converts the multi-dimensional data into one dimension by employing the i-Distance technique. Based on the one-dimensional data, ML-index uses the RMI to estimate the approximate position of a search key. Recently proposed index Flood [6] can also support multi-dimensional data and is very relevant to our

III. BACKGROUND
Before delving into the details of SPRIG, in this section, we introduce three basic concepts: 1) Spatial Interpolation Function; 2) Error Guarantee; and 3) Pivot Based Filtering, which serve as the building blocks of the proposed index.

A. Spatial Interpolation Function
Given a set of 2-dimensional sample points {(x i , y i )|1 ≤ i ≤ n} and their corresponding values {v i = f (x i , y i )|1 ≤ i ≤ n}, one can construct a spatial (two-dimensional) interpolation function F in = f (x, y) that passes through all these sample points [10]. Afterward, given any point (x, y), it is easy to estimate the value of f (x, y) with the interpolation function. Borrowing the idea from the learned index [1], if we treat v i as the position of the point (x i , y i ), we can use F in to quickly estimate the position of any given point. Moreover, if the sample points are not random but can represent the distribution of the original spatial dataset, we can use fewer sample points to fit the spatial interpolation function for estimating positions. It indicates that the spatial interpolation function can learn the spatial position distribution with a lower storage overhead, which fits well with the goal of the learned index. Therefore, it is feasible and promising to exploit the spatial interpolation function F in as the learned model.

B. Error Guarantee
For a learned index, it is essential to conduct a local search after predicting the position of a given point. Generally, the local search range is [pos − eg, pos + eg], where pos is the predicted position and eg is the estimation error, also called error guarantee. Consequently, eg is an essential concept in a learned index. Different from FITing-tree [3] (used in Flood [6]), we adopt the maximum estimation error as the error guarantee in our scheme, which can be determined by a query workload W.
where (q x , q y ) ∈ W. Regarding a spatial point, its spatial position can be determined by its x and y coordinates. Therefore, in our scheme, we project the estimated spatial position to x dimension and y dimension and obtain two error guarantees, i.e, where P x () and P y () project a spatial position to x dimension and y dimension, respectively.

C. Pivot Based Filtering
Assume that a set D contains n 2-dimensional points, i.e, where q c is a point, and r is a radius. Launching a query Q c over D means one would like to find points in D that satisfy d(p i , q c ) ≤ r, where d(·) calculates the Euclidean distance between two spatial points. The intuitive solution is to scan and check points in D one by one. However, it is inefficient. Although we can build tree based index structures, such as k-d tree and Mtree [11], to speed up the query processing, it will incur much extra storage. In order to improve the performance of Q c without introducing too much storage overhead, we adopt a pivot based filtering technique. The key idea is to select a virtual pivot p v for D and calculate distances d(p i , p v ) for each point p i . Then, sort D according to the corresponding d(p i , p v ). When performing a query Q c over D, we can only calculate the distance d(q c , p v ) and check the points whose This optimization technique is based on triangle inequality, and its correctness is as follows:

The above inequality indicates that if
Thus, we can narrow down the scan range from the whole dataset D to the points that have distances d(

IV. OUR PROPOSED INDEX-SPRIG
In this section, we present the details of our proposed index, SPRIG. Fig. 1 depicts the system architecture of our index, which is comprised of two parts: index building and query processing. In the following, we first discuss how to build the learned index. Then, we describe the detailed query processing on our index.

A. Index Building
Our SPRIG mainly consists of three components: 1) An n × m grid layout G n×m , where n is the number of columns along x dimension and m is for y dimension; 2) A table T ; and 3) A spatial interpolation function F in based learned model, as shown in Fig. 1. Here, we may use some parameters for our index, which will be further discussed in Section IV-C. To build the n × m grid layout, we first find n − 1 boundaries on x dimension to generate n non-equal size columns, and add these boundaries into a set B x . Our goal is to make data records evenly distributed across columns, i.e., each column has a roughly equal number of records (in this paper, we use "point" and "record" interchangeably). For y dimension, there will be m − 1 boundaries in set B y . We denote the maximum and minimum values in x dimension as {x min , x max }, while those are {y min , y max } for y dimension. After adding {x min , x max } into B x and {y min , y max } into B y , we separately sort B x and B y in an increasing order, where |B x | = n + 1 and |B y | = m + 1. Totally, there are n × m cells for the grid, and we have G n×m = (B x , B y ). Algorithm 2 shows the process of building the grid.
Next, we allocate integers in the range [0, n × m − 1] as cell ids along x dimension and define a 2-dimensional array C id to index these cell ids: Afterward, we can build a table T to map the cell id to the covered records, in which the key is the cell id and the value is a pair (firstAddress, size) indicating the pointer to the first record and the number of records in the cell. Based on G n×m and C id , we can fit a spatial interpolation function F in . In particular, we treat {B x , B y } as inputs and C id as the desired estimation values to determine F in , i.e., C id ← F in (B x , B y ). Besides, to speed up the distance related search, for example, kNN queries, we employ the pivot based filtering technique, which drives us to select a pivot p v in a cell and sort the records (in a cell) according to the distances d(p i , p v ). In this paper, we adopt the k-means clustering to select pivots for each cell. It is worth noting this technique does not incur much extra storage except for pivot points.

B. Query Processing
In this paper, we focus on the range and kNN queries, in which the point query is implicitly included. Next, we describe our approaches.
Range Query. For spatial data, the range query identifies the records p i that fall within Q r =(q b , q t ), where q b = [b x , b y ] and q t = [t x , t y ] are the bottom left and top right point of a query window, respectively. The main idea of processing a range query is to convert it to locate the cell ids of q b and q t . Here, we take locating q b 's cell id as an example, and the steps are as follows.
• Step-1. Given q b , we can use F in to obtain a predicted cell id pid b . It is simple to calculate the locations of pid b in set B x and B y . That is, l px = pid b mod n and l py = pid b / n.

Algorithm 1 GetRealCellId
Input: A given point (x, y); The grid layout, Gn×m = (Bx, By); A predicted cell id of the given point, pid; Trained error guarantee eg = (eg x , eg y ); Output: The real cell id rid of the given point (x, y).
1: n ← |Bx| − 1 2: lpx ← pid mod n; lpy ← pid / n 3: lrx ← BinarySearch(Bx, x, lpx − eg x , lpx + eg x ) 4: lry ← BinarySearch(By, y, lpy − eg y , lpy + eg y ) 5: return lry · n + lrx cell id rid t of q t . After that, the range query result can be collected with the following strategy: 1) For cells intersected by query window Q r , we scan the records in these cells and put the records that fall within Q r into the range query result.
2) For cells contained inside query window Q r , we directly add all the records covered in these cells into the result.
As shown in Fig. 2(a), the intersected cells must be on the vertical and horizontal lines of rid b and rid t . Therefore, it is easy to determine the intersected cells (gray area) and contained cells (blue area).
kNN Query. In this paper, we denote the kNN query as Q kNN = (q k , k), where q k is a point, and k is the number of nearest neighbors. The formal definition is: ∀p i ∈ S, ∀p j ∈ D \ S, d(q k , p j ) ≥ d(q k , p i ), where S is the result set of kNN query. For kNN queries, our solution is to locate the real cell id of the query point q k . Then, starting from the cell, we recursively spread the search range and incrementally check the records in the outer-layer adjacent cells until the result is complete. To facilitate improved performance, we employ two pruning techniques. One is the closest point pruning technique that is used to determine whether a cell should be checked. A cell may have different closest points to the different query points. However, in our scheme, since it is simple to obtain the locations (l rx , l ry ) of the located real cell, we can get the closest point of the cell, denoted as p c , with the help of B x and B y easily. In Fig. 2 cntY ← (mapY.get(entry.y)is ∅) ? 1:mapY.get(entry.y) + 1 6: mapY.put(entry.y, cntY) 7: (xmin, ymin) ← findMin(D); (xmax, ymax) ← findMax(D) 8: mapX.sortByKey(); mapY.sortByKey() #Ascending 9: avgX ← D.size/n; avgY ← D.size/m 10: Bx ← getBoundary(mapX, avgX, xmin, xmax) 11: By ← getBoundary(mapY, avgY, ymin, ymax) 12: return (Bx, By) spreading outwards strategy, closest-point pruning, and pivot based filtering, our kNN solution works as follows and is formally depicted in Algorithm 3: • Step-1. Locate the real cell of q k . With F in and local binary search, we obtain a real cell id rid of the query point q k , which is shown in line 1 and line 2. • Step-2. Calculate the distances from q k to the borders of the located cell. We denote them as c t , c b , c l , and c r , as shown in Fig. 2(b). Then, we obtain a radius r=min(c t , c b , c l , c r ). See line 6 -line 8 for this step.

12:
if d(q k , cell.pc) < queue.peek.dist then 13: records ← PivotFilter(cell, q k , queue) Step-3. Scan records in the cell. After filtering the records by the pivot based filtering technique, we put a record p i into a priority queue if the queue's size is less than k or d(p i , q k ) < σ, where σ is the distance between queue.peek and q k . Besides, we use a counter k cnt to record the result size and increase it if d(p i , q k ) ≤ r.
In Algorithm 3, we use a separate function putQueue() (line 21 − line 31) to show the details of this step. • Step-4. If k cnt < k, we expand the search range and calculate a new radius r=min(c t , c b , c l , c r ), where c t , c b , c l , c r are the distances from q k to the borders of outer layer adjacent cells. For each adjacent cell, we first check whether d(p c , q k ) > σ. If yes, we skip the cell. Otherwise, perform Step-3. As shown in Fig. 2(b), we would skip cell A and further process cell B.

Repeat
Step-4 and Step-3 until k cnt ≥ k. Eventually, the priority queue holds the result of kNN query. Note that, since the collectAdjacent() and PivotFilter() functions are straightforward, we do not present them in Algorithm 3 due to the limited space.

C. Cost Model
In this section, we build a cost model, which can be used to determine the number of columns in x dimension and y dimension, i.e., the values of n and m. Motivated by [6], we model the execution time of performing a query over our index. Here, we take the range query workload as an example. From Section IV-B, we know that the query time of range queries consists of four parts: 1) Prediction; 2) Local binary search; 3) Retrieve cells; 4) Scan and check data points in the intersected cells. Clearly, different n and m will generate different B x , B y . Consequently, the execution time of F in and the local binary search will be affected. For ease of description, we denote the execution time of the spatial interpolation function as T(F n×m in ) and the execution time of local binary search as T(B n×m ). Assume there are N i intersected cells and N c contained cells fall within the range query Q r . Meanwhile, we define N p as the data points in the intersected cells. Through simulations, we can obtain the average time of retrieving a cell and scanning a data point, which are denoted as T r and T s , respectively. Putting these four parts together, the time cost of performing a rang query is modeled as: Given a dataset D and a query workload W, where Q r ∈ W, we expect to obtain the best layout parameter: n × m that makes Time have minimal average value.

V. EVALUATION
In this section, we experimentally evaluate the performance of our index and compare it with alternative schemes in processing range and kNN queries. Specifically, we first explore the efficiency and accuracy of the typical spatial interpolation functions. Then, we compare SPRIG with traditional indices and Flood [6], which is a recently proposed multi-dimensional learned index, in terms of range and kNN query time and storage overheads. We implemented all indexes in Java and evaluated them with in-memory versions. To analyze the impact of dataset size on index performance, we adopt three Twitter datasets [12] consisting of tweets with their locations: Tweet200k, Tweet2M, and Tweet20M that have 200k, 2M, and 20M spatial points, respectively. All experiments are conducted on a machine with 16 GB memory and 3.4 GHz Intel(R) Core(TM) i7-3770 processors and running Ubuntu 16.04 OS.
Efficiency and Accuracy of Spatial Interpolation Functions. We evaluate five spatial (two-dimensional) interpolation functions on adaptive grids, i.e., bilinear interpolation, bicubic interpolation, piecewise bicubic interpolation, Shepard interpolation, and radial based function (RBF) interpolation [13]. Given a query workload, we expect to evaluate the average execution time and maximum estimation errors of these five functions varying grid layout from 10 × 10 to 200 × 200. It is noted that, for ease of comparison, we adopt eg (Eq. (1)) instead of eg x and eg y to evaluate the accuracy of F in . All of these interpolation functions are evaluated on Tweet200k. Fig. 5(a) shows the average execution time for three interpolation functions: bilinear, bicubic, and piecewise bicubic, while Fig. 5(b) presents their accuracy. We exclude the Shepard and RBF interpolation functions, for which they have  Table II due to its significant execution time.   Table I, we can see that the bilinear interpolation function has the best efficiency and accuracy in all grid layouts. Therefore, in the following comparisons, we apply bilinear interpolation function in our index. It is interesting that the maximum estimation error of bilinear interpolation function is always n + 1, which makes it quite suitable to reduce the execution time of the local search.
Comparison on Range Query. For range queries, we compare our proposed index with other multi-dimensional indexes that support range queries over the aforementioned three datasets. We choose R-tree, k-d tree, and Flood as the competing indexes, in which the first two are representative traditional indexes, and the third one is a state-of-the-art learned index and similar to our work. In addition, we consider five sets of queries with different selectivities {0.1%, 0.5%, 1%, 1.5%, 2%}. Aggregating these query sets as a big query workload, we tune our index by the cost model (See details in Section IV-C) to obtain the best grid layout. To be fair, we also train Flood by the approach proposed in [6], which can obtain the best layout and error guarantee. Similarly, the traditional indices, R-tree and k-d tree, are tuned to obtain their best parameter, i.e., the maximum number of children for a node. Therefore, all indexes participating in the comparison are evaluated with their best parameters. From Fig. 3, we can see that SPRIG is always significantly faster than the traditional indexes in all selectivities, which is more advantageous on big data set. For example, on the Tweet20M dataset (Fig. 3(c)), our index achieves up to an order of magnitude better performance than k-d tree for range queries. Besides, our index outperforms Flood in most cases. This benefit comes from the fact that Flood only learns the distribution of one dimension, while SPRIG learns the spatial distribution, which allows us to do more fine-grained filtering.
Comparison on kNN Query. For kNN queries, we replace R-tree with M-tree [11]. It is because R-tree is much slower than other indexes in kNN queries, and M-tree is a typical kNN-support index. Since Flood does not provide any detail about how to deal with kNN queries, we implement it with a similar kNN search strategy as our index. In the kNN query comparison, we consider k = {4, 8, 16, 32, 64}. Similar to the range query, we tune all the comparison indexes to obtain their best parameters. From Fig. 4, we can see that M-tree is more expensive than our index in executing kNN queries. For Flood, our index outperforms this learned index on all datasets. Since Flood is much slower than other indexes on the Tweet20M dataset, we exclude it from Fig. 4(c) and list its performance as follows. As shown in Fig. 4 and Table II, our index is   TABLE II  around 2×, 5×, and 9× faster than Flood on the Tweet200k, Tweet2M, and Tweet20M dataset, respectively. For k-d tree, our index is at least 2× faster on the Tweet200k dataset and is slightly faster on the Tweet2M dataset. For the Tweet20M dataset, although our index still has a huge advantage over Mtree and Flood in the query performance, it is not as good as k-d tree. However, k-d tree has a significantly higher storage footprint to achieve such query performance. We demonstrate the storage overheads of these indexes in the next section. Storage Overhead. Due to the limited space, we only compare the storage overheads of different indexes on the Tweet20M dataset, which actually has a similar relationship between indexes on the other two datasets. In the range and kNN query comparisons, we use the corresponding query workload to tune these indexes for their best parameters. For example, our index has the best grid layout 710 × 690 on rang query workload, while it is 3000×10 for kNN query workload. Since different parameters of one index may lead to different storage overheads, we compare the storage overheads of these indexes on the range and kNN query workloads, separately, as shown in Table III and Table IV, respectively. To obtain the storage footprint of a tree index, we evaluate the necessary storage of one node, e.g., the minimum bounding rectangle (MBR) of R-tree, and count the total number of internal nodes by traversing the tree. For Flood, it has two components: a FITing-tree on one dimension and a table to map a cell to the covered data records. For our index, there are three components: a grid layout G n×m , a table T for managing the cells, and a spatial interpolation function F in . The storage consumption of these two learned indexes is related to their grid layout. Table III and Table IV show that both the learned indexes have less storage overheads than traditional indexes on the range and kNN query workloads. Although our index consumes more storage compared to Flood, we achieve better query performance with an acceptable storage overhead. Recall that in the kNN query time comparison, our index is slower than k-d tree on Tweet20M. However, as shown in Table IV, the storage overhead of k-d tree is three orders of magnitude larger than that of our index, which renders it challenging to use in practice. Thus, our index is more practical than k-d tree with big datasets.

VI. CONCLUSION
In this paper, we have proposed a new learned model that can learn the spatial distribution of the spatial data directly. Based on the learned model, we have built a novel learned spatial index SPRIG and designed the range and kNN query execution strategies over the index. Our experimental results suggest that 1) the bilinear interpolation function is the best option as the spatial learned model compared with the other spatial interpolation functions; 2) our index SPRIG is efficient with the relatively small storage footprint. In our future work, we expect to further reduce the average query time of kNN queries on big datasets and make our index more flexible.