# Collecting Sensed Data with Opportunistic Networks: The Case of Contact Information Overhead
## 4 An Algorithm for Reducing Contact Information Overhead
### PoiFord Design
#### 4.2.1 Phase 1: Identification of Significant Locations
```
Input:\((x_{i},y_{i})\), location references in \(LT\{loc_{a}\}\), \(r\) Output:\(loc_{i}\)
1 foreach incoming location \((x_{i},y_{i})\) in sampling interval \(\Delta t_{i}\)do
2 foreachInput \(\{loc_{a}\}\)do
3\(d_{a,i}=\sqrt{(x_{a}-x_{i})^{2}+(y_{a}-y_{i})^{2}}\);
4 if\(d_{a,i}<2r\)then
5\(loc_{i}=\langle x_{a},y_{a}\rangle\);
6 break;
7 end if
8 else
9\(loc_{i}=\langle x_{i},y_{i}\rangle\);
10
11 end if
12
13 end if
14 return\(loc_{i}\);
```  
**Algorithm 1** The algorithm for recording location information  
Algorithm 1 summarizes how \(loc_{i}\) is acquired using the current location in the form of latitude \(x_{i}\) and longitude \(y_{i}\), the previous location references in \(LT\), and a threshold distance \(r\). Consequently, the number of recurrences of a location reference \(loc_{a}\) in \(LT\) represents the number of periods in which the user is present in the circular area formed by \(r\) from location \((x_{a},y_{a})\). Figure 2: Structure of the location table. Extracting significant locations.Significant locations are identified by more number of recurrences in \(LT\). At every sampling interval \(\Delta wt\), a node running on PoiFord extracts the two most recurring location references from its location table--where \(w\) is a constant of the algorithm. These locations represent POIs, and are referred to as the node's home and work locations, \((x_{h},y_{h})\) and \((x_{w},y_{w})\), respectively. Although incoming GPS coordinates may slightly vary each time the node is in either location, the location reference records only a single pair of approximated coordinates each sampling interval \(\Delta t\), provided the circular area formed by the incoming pair of coordinates intersects with that of a previous coordinate. Here, to facilitate understanding, we further explain the working principle of PoiTrace with an example scenario. Consider the map of a fictional city in Figure 3 which is divided into 9 regions labelled \(A\) to \(I\). [PERSON], a user in the city, lives in region \(C\) and travels to work in region \(G\). The first three GPS readings take place in his house at location \(a\), \(b\), and \(c\). The next reading takes place on his way to work, at location \(d\). The next two readings take place in his office, at location \(e\). and \(f\). \((x_{a},y_{a})\), the GPS reading in location \(a\) is recorded as \(\langle x_{a},y_{a}\rangle\) in the location table. However, as shown in Table 4, the readings at location \(b\) (i.e., \((x_{b},y_{b})\)) and \(c\) (i.e., \((x_{c},y_{c})\)) are also recorded as \(\langle x_{a},y_{a}\rangle\), instead of \(\langle x_{b},y_{b}\rangle\) and \(\langle x_{c},y_{c}\rangle\), respectively. This is because the circle of radius \(r\) formed from these locations intersects with the circle formed from a previous location, i.e., location \(a\). Likewise, the readings at \(e\) and \(f\) are both recorded as \(\langle x_{e},y_{e}\rangle\). After a period of \(\Delta\delta t_{1}\) (here we take \(w\) as \(\delta\)