# GeoBERT: Pre-Training Geospatial Representation Learning on Point-of-Interest
## 3 Materials and Methods
### Build Training Corpus
#### 3.4.1 Shortest Path  
The \"shortest path\" method introduced by [PERSON] et al. [3] constructs a POI sequence based on the Greedy Algorithm. If documents are constructed based on the principle of global optimization, the time cost is exceptionally high, rendering the method unfeasible. However, when dealing with long sequences (e.g., 800+ POIs in a grid), the original shortest path method is still too time-consuming. Therefore, we follow [PERSON] et al. 's idea and improve the algorithm by using a matrix calculation and putting it on a GPU, which significantly reduces the computation time. The pseudo-code of our shortest path is illustrated in Algorithm 1. Assuming that there are \(n\) POIs in a given grid \(G\) and denoting \(G=\{P_{1},P_{2}\ldots,P_{n}\}\), the algorithm returns a sequence \(L\) with the shortest path through all POIs. First, we initialize a distance matrix \(M_{dis}(n\times n)\) as the Euclidean distance between each pair of POIs <P, P>. We then take the farthest POI pair as the start point and the end point of the path, namely \(P_{s}\) and \(P_{e}\). At this time, the current path is \(L=\{P_{s},P_{e}\}\), and the wait-to-insert set is \(W=\{P_{w}|P_{w}\in G-L\}\). The next task is to keep looking for the correct position and insert the right POI until the set \(W\) is empty. The correct position makes the path length shortest under each loop. The pseudo-code of finding correct location and POI is illustrated in Algorithm 2. First, we set up a sub-matrix \(M_{sub}(l\times w)\) considering only all possible locations and POIs waiting to be inserted; \(landw\) represent the length of \(L\) and \(W\). Suppose that, at the step t+1, POI \(P_{i}\) is inserted between \(P_{m},P_{n}\). The path length can be computed as \(\eta_{t+1}=\eta_{t}+S_{m,j}+S_{i_{n}}-S_{m,n}\). Specifically, we concat each two adjacent rows in \(M_{sub}\) and obtain a 3D matrix \(M_{3d}\) (\((l-1)\times 2\times w\)) to represent each possible location. There are \((l-1)\) positions in a sequence of length \(l\). Then, we sum the two adjacent rows to obtain the additional distance. The length reduced when inserting a new POI is calculated as \(Edge_{break}\). Finally, we argmin the loss matrix \(M_{loss}\). The correct position index \(idx\) and the POI \(P_{ins}\) to be inserted in the next step are obtained. ```
0: POIs in a Grid \(G=\{P_{1},P_{2}\ldots,P_{n}\}\)
0: shortest path of POIs in grid \(L=\{P_{s},\ldots,P_{i}\ldots,P_{e}\}\)
1: Initialize POIs wait-to-insert \(W=\{entities\ in\ G\}\)
2: Initialize shortest Path \(L=\{\}\)
3: Initialize matrix \(M_{dis}\) (\(n\times n\)) as Euclidean distance between each pair of \(<P,P>\). 4:\(P_{s},P_{e}=argmax(M_{dis})\) [Find the farthest POI pair \(<P_{s},P_{e}>\)]
5:\(L=[P_{s},P_{e}]\)
6:\(W=\{P_{W}|P_{W}\in G-L\}\) {Remove POIs already sorted}
7:while\(W\)do
8:\(idx,P_{ins}=QueryPOI(M_{dis},L,W)\) {Find the POI and location to insert}
9:\(Linsert(idx,P_{ins})\)
10:\(W.remove(P_{insert})\)
11:endwhile
12:return\(L\)
```  
**Algorithm 1** Shortest Path For POIs In A Grid```
0: Euclidean distance between each pair of POIs \(M_{dis}\); Current shortest path sequence \(L\); POIs wait to insert \(W\)
0: Insert index \(idx\), Insert POI \(P_{ins}\)
1:\(M_{sub}=M_{dis}[L][W]\) (only consider POIs wait to insert]
2:\(M_{3d}=stack([M_{sub}[idx[0:-1]],M_{sub}[idx[1:]]],dim=1)\) {obtain all possible positions to insert by splitting 2d matrix into any 3d matrix with each two adjacent rows}
3:\(M_{2d}=Sum(M_{3d},dim=1)\) {Calculate additional distances for all possible insertion positions}
4:\(Edge_{break}=M_{dis}[L[0:-1]][:,L[1:]].diag()\) {The distance reduced when inserting a new POI}
5:\(M_{loss}=M_{2d}-Edge_{break}.repeat(len(W)).T\) {The total loss of each possible insertion}
6:\(idx,ins=argmin(M_{loss})\). 7:return\(idx,P_{ins}\)
```

**Algorithm 2** Query POI

#### 3.4.2 Center Distance Path

POIs in a grid are sorted by the distance between each POI and the grid center. The principle is shown in Figure 4. This method was also proved effective by [PERSON] et al. (2016).