## 3 Methodology
### Spatial Layer Construction
#### 3.1.2 Trie Tree for Managing Non-Equal Length-Encoding Sets
(2) Decode the calculated encoding to obtain the coordinates of the center points of the partitions where \(bl\) and \(tr\) are located. (3) Calculate the longitude and latitude intervals based on the encoding precision. (4) Calculate the set of all partition center points covered by the rectangular range using the longitude and latitude intervals and the center coordinates of the two partitions. (5) Traverse the point set and find the corresponding nodes according to Algorithm 1. ```
Input: GLMI: index, QR: query range;  
Output: result: collection, whose value in QR;  
1: leafNodes \(\leftarrow\) findLeafNodes(GLMI, QR);  
2: result\(\leftarrow\) \(\emptyset\);  
3: for node in leafNodes, do  
4: result.append (findrangefrombuffer(node.buff,t1,t2));  
5: result.append (findrangefromsegments(node.data,t1,t2));  
6: end for  
7: filter in result by Q  
8: return result  
9: function findLeafNodes(GLMI, QR)  
10: begin  
11: cbl \(\leftarrow\) Geohash_Hilbert.encode(QR.bl, precision);  
12: ctr \(\leftarrow\) Geohash_Hilbert.encode(QR.tr, precision);  
13: r\({}_{1}\) \(\leftarrow\) Geohash_Hilbert.decode(cbl, precision);  
14: r\({}_{2}\) \(\leftarrow\) Geohash_Hilbert.decode(ctr, precision);  
15: Use r\({}_{1}\)bl and r\({}_{2}\).tr to form a rectangular r;  
16: Calculate the longitude interval l\({}_{1}\) and latitude interval l\({}_{2}\) based on precision;  
17: Divide \(\epsilon\) evenly by l\({}_{1}\) and l\({}_{2}\), and calculate the center point of each rectangle to obtain the point set Points;  
18: for point in Points, do  
19: node \(\leftarrow\) find the leaf node of Trie tree according to Algorithm 1;  
20: leafNodes.append(node);  
21: end for  
22: return leafNodes;  
23: end function. ```

**Algorithm 4** Range query algorithm

## 4 Experimental Results

In this paper, the performance of GLMI is compared with that of R-tree, KD-tree, and the ZM index. R-tree and KD-tree are traditional spatial indexes, while ZM index is a popular multidimensional data learned index. We conducted all experiments on a single server with an Intel i7-12700 CPU (3.2 GHz, 12 cores) and 32 GB RAM. All experiments were performed in a single-threaded environment. The experimental dataset includes the following: the Trip dataset, which is derived from the trip records of real New York axis in the United States and is composed of three dimensions: longitude, latitude, and timestamp, and the data volume is 5 million; the Traj dataset, which contains the trajectory records of 1000 Beijing taxis and about 1.57 million datasets [35; 36]. The distribution of spatiotemporal data points in the two datasets is shown in Figure 6.

### Feasibility of Piecewise Linear Models on Timestamp Data

The experiment in this section selects the timestamp data of the New York taxi dataset as the research object, with a total data volume of 50 million. We compared the performance of the piecewise linear model constructed by the ShrinkingCone algorithm and the B+ tree index structure in terms of data carrying capacity. The results are shown in Figure 7. The results show that under the same error threshold and leaf node size of B+ tree, the data carrying capacity of the piecewise linear model is significantly better than that of the B+ tree node. The reason is that the piecewise linear model can adaptively fit according to the actual distribution of the data, thereby achieving coverage of a wider range of data. In contrast, the size of the leaf nodes of the B+ tree is fixed, which limits its data carrying flexibility. The adaptability of the piecewise linear model not only improves the efficiency of data storage, but also allows it to locate key data faster than the traditional B+ tree structure. This has significant advantages in reducing query response times and reducing the storage space required for indexes. Figure 6: Spatiotemporal distribution of experimental data. Figure 7: The fitting power of the piecewise linear models.