## 3 Methodology
### Spatial Layer Construction
#### 3.1.2 Trie Tree for Managing Non-Equal Length-Encoding Sets
When inserting, each key value is first inserted into the basic layer, then randomly promoted to the upper layer with a probability of 1/2. This promotion process is accompanied by the creation of a logical node copy in the previous layer, and continues until the promotion fails or the preset maximum number of layers is reached. During a search operation, the upper layer nodes are compared with the search keyword, allowing the links in the upper layer to quickly skip over irrelevant nodes. If the keyword is larger, the search continues layer by layer until reaching the base layer. Through this design, the skiplist provides a logarithmic average search time complexity and can effectively support fast data insertion and search operations. Figure 5 shows the basic structure of the skiplist. ### Query Algorithm Based on GLMI

#### 3.4.1 Point Query Algorithm

The point query process in GLMI involves both the spatial and temporal layers. Given a query point (\(\textit{lng},\textit{lat},\textit{t}\)), first find the partition corresponding to (\(\textit{lng},\textit{lat}\))through Algorithm 1, and then perform a query at the temporal layer. The query at the temporal layer includes two steps: (1) a query in the buffer corresponding to the partition, and (2) a query using the piecewise linear model. When executing a query, the piecewise linear model first finds the segment _seg_ to which the query point belongs, and then calculates the predicted position of the query point in the segment _seg_ through Formula (1). \[pos=(t-\text{seg.startx})*\text{seg.slope}+\text{seg.starty} \tag{1}\]

For the segments constructed by the ShrinkingCone algorithm, the true position of the elements must be within the error threshold. Therefore, it is only necessary to use the binary search algorithm in the range [_pos_-error, _pos_ + error] to find the true position of the query point. Figure 5: Skiplist layered pointer structure. Achieves fast search by traversing multiple nodes across different levels through its multi-level structure. ```
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 3** Point query algorithm

#### 3.4.2 Range Query Algorithm

Given a query range \(Q=[lng_{1},\,lng_{2}]\times[lat_{1},\,lat_{2}]\times[t_{1},\,t_{2}]\), according to the function findLeafNodes in Algorithm 4, the spatial partitions involved in the rectangular range \([lng_{1},\,lng_{2}]\times[lat_{1},\,lat_{2}]\) are calculated, and then the time layer query is performed. The position of \(t_{1}\) and \(t_{2}\) in the segment is calculated according to the piecewise linear model, and finally filtered to obtain the result set \(R\). The steps of the function findLeafNodes are as follows: (1) Calculate the encoding of the bottom-left point \(bl\) and the upper top-right \(tr\) of the rectangular range.