## 3 Methodology
### Spatial Layer Construction
#### 3.1.2 Trie Tree for Managing Non-Equal Length-Encoding Sets
The data are divided into segments of variable size, with each segment represented by a linear function, requiring only the storage of the segment's starting point and slope. This design effectively captures the data distribution and reduces space consumption. This paper uses the ShrinkingCone algorithm [23], commonly applied in learned indexes, to construct the piecewise linear model. The algorithm determines a slope range for the starting point to form a cone. If the point to be added falls within the cone, the new high and low slopes are recalculated based on the starting point, the key to be added, and the set error, thereby shrinking the cone. If the point to be added is outside the cone, it becomes the starting point of a new segment. The ShrinkingCone algorithm requires only a single traversal of the dataset, with a time complexity of O(\(n\)), where n is the number of data points. This algorithm is not only fast to build but also ensures that the error in the linear function for each data segment does not exceed the given threshold. Algorithm 2 outlines the data segmentation process. ```
Input: data: data to be sharded, error: preset error; Output: result: the starting key array of each data slice;
1: slope_high \(\leftarrow\)\(\infty\), slope_low \(\gets\) 0;
2: for i \(\gets\) 1 to data.length, do
3: low \(\leftarrow\) max((Loc[i] - error - start_y)/(data[i] - start_x), slope_low);
4: up \(\leftarrow\) min((Loc[i] + error - start_y)/(data[i] - start_x), slope_up);
5: if low \(<\) up then
6: slope_low \(\leftarrow\) low;
7: slope_high \(\leftarrow\) up;
8: else:
9: result. append (data[i]);
10: slope_high \(\leftarrow\)\(\infty\), slope_low \(\gets\) 0;
11: end if
12: end for
13: return result. ```
**Algorithm 2** The ShrinkingCone algorithm

### Data Insertion

#### 3.3.1 Data Insertion Strategy

When inserting new data, the system first locates the partition through the spatial layer. If the partition's data volume does not exceed the threshold after insertion, the data are inserted into the temporal layer. Otherwise, the partition is split first, and then the data are inserted into the temporal layer. When performing in-place data insertion, two key impacts must be considered: (1) the insertion may increase the error within the existing segment, and (2) inserting in place requires moving elements within the segment to maintain the order of timestamps. Under heavy write loads, increased errors and frequent element movement can significantly degrade index performance. To solve the above problems, GLMI draws on the delayed update idea of LSM Tree. GLMI maintains an ordered buffer in memory for each spatial partition, allowing for fast data merging and efficient search operations. New data are added to the buffer of the corresponding partition. When the buffer data reaches a certain size, the ShrinkingCone algorithm is used to re-segment all the data within the partition, and the buffered data are then written to storage. This design ensures that the cost of re-segmentation is relatively low because the amount of data in a partition will not exceed a specified threshold. To reduce the cost of frequent data merging and re-segmentation under heavy write loads, and to prevent query operations from being blocked by re-segmentation, GLMI implements an asynchronous strategy that decouples the buffer-merging process from the main worker thread. When the buffer reaches a predefined size threshold, a background thread is initiated to merge and re-segment the data. By executing these operations asynchronously, the main thread can continue without interruption, minimizing the impact of heavy write loads on query latency and improving overall system throughput. #### 3.3.2 Skiplist

In the GLMI architecture, a skiplist is selected as the core component of the memory buffer to optimize the data management of each spatial partition. The skiplist is an ordered probabilistic data structure, improved upon the traditional linear linked list. It enhances data access efficiency by introducing multi-level indexes.