## 3 Methodology
### Spatial Layer Construction
#### 3.1.2 Trie Tree for Managing Non-Equal Length-Encoding Sets
### Index Construction Time and Space Cost

We compared the time consumption of the index construction of R-tree, KD-tree, ZM index, and GLMI on Trip and Traj datasets, respectively. The results are shown in Figure 8. On both datasets, the construction time of GLMI is lower than that of R-tree and the ZM index. This is because GLMI only needs to traverse the dataset once when constructing the spatial layer and the temporal layer. During the construction process of R-tree, node splitting or merging operations need to be performed continuously to maintain the balance of the tree, which increases the complexity of construction. The ZM index uses a neural network model, and the training process will take a lot of time. We compared the space occupied by the indexes, and the results are shown in Figure 9. Under the same dataset, compared with the traditional index structures of R-tree and KD-tree, GLMI has a significant advantage in space occupation. The reason is that R-tree and KD-tree, as traditional tree structures, need to spend a lot of space to store pointer information in addition to storing data keys, while GLMI only needs to store the Trie tree used to manage the encoding set and the piecewise linear model parameters. The ZM index only needs to store data keys and neural network models, so the space cost is the lowest. ### Query Performance Evaluation

In this section, we compare the point query and range query performance of R-tree, KD-tree, ZM index, and GLMI. As shown in Figure 10a,b, all four index structures can

Figure 8: Comparison of index build time. Figure 9: Comparison of index space cost. achieve stable point query efficiency, and the query time increases approximately linearly with the amount of data. However, GLMI is significantly better than the R-tree in point query efficiency, and slightly better than the KD-tree and ZM index. This is because GLMI constructs a double-layer index, which can locate data partitions more quickly in the spatial layer, and use piecewise linear models in the partitions to learn the distribution of time-dimensional data, thereby improving the efficiency of point queries. For range queries, the results are shown in Figure 10c,d. The horizontal axis is selectivity, which refers to the proportion of the result set returned by a given query condition relative to the entire dataset. The vertical axis is the query request execution time. On the Trip and Traj datasets, GLMI is significantly better than KD-tree and the ZM index. In the case of low selectivity, the efficiency is comparable to that of the R-tree. In the case of high selectivity, GLMI performs worse than the R-tree on the Trip dataset, but slightly better than the R-tree on the Traj dataset. This difference is related to the characteristics of the dataset. Considering the double-layer indexing mechanism of GLMI, it requires more computing resources for the partition search when processing queries involving a large spatial range. ### Insertion Performance Evaluation

We compare the performance of indexes in data insertion. This experiment compares the time-consuming aspect of R-tree, KD-tree, and GLMI index in inserting different numbers of data points on the Trip dataset. The experimental results are shown in Figure 5:0 As can be seen from the figure, in terms of data insertion performance, as the amount of inserted data increases, the retrieval time of R-tree and KD-tree will increase proportionally. The insertion efficiency of GLMI is similar to that of the KD-tree. Compared with R-tree, the performance is significantly improved. This is due to its delayed update strategy. Data will be inserted into the buffer first, but when the inserted data reach the threshold, GLMI needs to be merged with the data points in the buffer and reconstruct the piecewise linear model. The insertion time is mainly due to reconstructing the piecewise linear model. Figure 5:1 Comparison of index query performance.