In this work, we investigate methods for merging spatiotemporal usage and entity records across two locationenhanced services, even when the datasets are semantically di erent. To address both e ectiveness and e ciency, we study this linkage problem in two parts: model and framework. First we discuss models, including k-l diversity| a concept we developed to capture both spatial and temporal diversity aspects of the linkage, and probabilistic linkage. Second, we aim to develop a framework that brings e cient computation and parallelization support for both models of linkage.
An important portion of digital footprint left behind by
entities interacting with online services contains spatio-temporal
references. This footprint is a fertile resource for business
intelligence applications [
Records with similar location and time naturally observe similar phenomena. The data analyst can gather such data from multiple sources, which are typically anonymized due to privacy concerns. These sources could generate semantically di erent datasets, or the semantic link between the sources could have been lost due to anonymization. As most data science tasks require large amount of data for accurate training with higher con dence, scientists need to combine data from multiple sources to produce accurate aggregate patterns. For example, spatio-temporal usage records belonging to the same real-world user can be matched across 1www.foursquare.com / www.swarmapp.com records from two di erent location-enhanced services, even when the datasets are semantically di erent. Another example would be linkage of the sensor data from di erent vendors that are embedded to the same moving system, i.e. self-driving cars. This linkage enables data scientists and service providers to obtain information that they cannot derive by mining only one set of usage records. Consider a LES provider who combines user segmentation results derived from its own usage records with social segmentation results derived from the publicly available Swarm records. There are several algorithmic and systems challenges to merge information from multiple sources of anonymized spatiotemporal data that are collected with necessary permissions. To cover both e ectiveness and e ciency, we divide this linkage problem into two parts: model and framework.
To develop e ective models, one needs to de ne a
similarity or probabilistic measure for linkage, which considers
time, location, and the relationship between the two. This
is relatively simpler for many record linkage tasks [
Considering that location-based social networks get
millions of updates every day, linkage over hundreds of days of
data would take impractically long amount of time. Nave
record linkage algorithms that compare every pair of records
take O(n2) time [
Datasets. We denote the two spatio-temporal usage record datasets from the two LES across which the linkage is to be performed as I and E.
Entities and events. Entities, or users, are real-world systems or people who use LES. We use the terms user and entity interchangeably. They are represented in the datasets with their ids, potentially anonymized, which are di erent for the two LES. Events correspond to usage records generated by a LES as a result of users interacting with the service. For an event e 2 E (or i 2 I), e:u (or i:u) represents the entity associated with the event. We use UE and UI to denote the set of entity ids in the datasets E and I, respectively. We have UE = fe:u : e 2 Eg and UI = fi:u : i 2 Ig. Location and time. Each event in the dataset contains location and time information. The location information is in the form of a region, denoted as e:r for event e. We do not use a point for location, as for most LES the location information is in the form of a region. We assume the time information is a point in time. 2.1
k-l Diversity The core idea behind the k-l diversity model is to locate pairs of entities whose events satisfy k-l diversity. Furthermore, such pairs of entities must not have any alibis. Co-occurrence. Two events from di erent datasets are called co-occurring if they are close in space and time. For two records i 2 I and e 2 E, closeness is de ned in terms of intersection of regions. To capture closeness in time, we use a parameter , and call two events are close in time if they are within a window of time units of each other. Alibi. While a de nition of similarity is necessary to link events from two di erent datasets, a de nition of dissimilarity is also required to rule out pairs of entities as potential matches in our linkage. Such negative matches enable us to rule out incorrect matches and also reduce the space of possible matches throughout the linkage process. We refer to these negative matches as alibi s. In this work, we use alibi to de ne events from two di erent datasets that happened around the same time but at di erent locations, such that it is not possible for a user to move from one of these locations to the other within the duration de ned by the di erence of the timestamps of the events.
Entity linkage. Let x 2 UI and y 2 UE be two entities. In order to be able to decide whether two entities are the same, we search for k co-occurring event pairs and at least l of them are at diverse locations. However, each co-occurring event pair does not count as 1, since each of these events could co-occur with many other events. Let C(i; e) be the a b c 1/6 1/2 1/4 1 x y d f e function to represent aforementioned co-occurrence relation of records i, and e, We weight these co-occurring event pairs as: w(i; e) =jfi1:u : C(i1; e) ^ i1 2 Igj 1 jfe1:u : C(i; e1) ^ e1 2 Egj 1 (1) Given a co-occurring event pair between two entities, we check how many possible entities' events could be matched to these events. For instance, in Figure 1, consider the solid line at the top with the weight 1=6. The event on its left could be matched to events of 2 di erent entities, and the event on its right could be matched to events of 3 di erent entities. To compute the weight of a co-occurring pair, we multiply the inverse of these entity counts, assuming the possibility of matching from both sides are independent. As such, in the Figure 1, we get 1=2 1=3 = 1=6. l diverse event pairs. For the same entity pair to be considered l-diverse, there needs to be at least l unique locations for the co-occurring event pairs in it. However, for a location to be counted towards these l locations, the weights of the co-occurring event pairs for that location must be at least 1. Here, one subtle issue is de ning a unique location. Intuitively, when datasets have di erent granularities for space, using the higher granularity ones to de ne uniqueness would give more accurate results. This could simply be a grid-based division of the space.
Entities x and y could be linked to each other, if they have k co-occurring event pairs in l diverse locations and their datasets do not contain alibi event pairs. Moreover, we only consider entity pairs for which there is no ambiguity, i.e. no two pairs (x; y) and (x; z) that are k-l diverse. Setting too low k-l values would lead many ambiguous pairs while too high values would lead many false negatives. To nd the balance in between these two, we apply elbow detection techniques on k, and l distributions. 2.2
Besides k-l diversity, we aim to model the spatio-temporal linkage problem using a probabilistic model. For consistency, we try to use the same notation with k-l diversity model as much as possible.
Probabilistic model starts by aggregating all of the entities on a common grid using the spatio-temporal features of the datasets. Gk denotes the set of entities in a speci c cell in the grid and jGkI (t)j denotes the number of entities from dataset I in cell Gk at some time interval [t t + ]. Let x 2 UI and y 2 UE be two entities, and set of entities colocated with entity x in UE , and set of entities co-located with entity y in UI at time [t t + ], in the grid is given as Gx(t), and Gy(t) respectively.
Assuming two sets, S1 and S2, where jS1j = jS2j = n, the number of possible di erent complete matches (CM) (each element in S1 has a partner in S2) between the elements of these sets is n!, using trivial combinations without repetition. If the number of elements in the sets are not equal, i.e. jS1j = n 6= jS2j = m then the problem turns into choosing m out of n (where n m) and calculating complete match with m elements, i.e. CM (n; m) = mn m!.
As the user set of one LES is typically not a subset of the second, we de ne the partial match (PM) where only k out of the m elements in S2 match with k out of n elements in S1. In this case we also need to choose k out of m and use the complete match, i.e. P M (n; m; k) = mk CM (n; k) = mk nk k!.
Let x y represents entities x, and y are the same realworld entity (match), the probability of a pair of speci c two items to match each other is calculated by the number of events where x and y match divided by the number of events in the universal set of all possibilities.
If we are given a single snapshot of the grid at time t the probability of a randomly chosen pair of co-located entities in the di erent services being the same entity (we are assuming a complete match case only) can be found as following: P (x y) = If we have more than one sample of the entity (for time slots t0 to time slot tT where we don't necessitate the slots to be sequential in time) and the grid we can then use the history of the entity. The probability is similar except taking the tracks of the entities into account: ( Pkm=P1 kmP=M1 (PnM1(;nm;m;k)
1;k 1) ; Gx(ti) = Gy(ti) 8ti 0; otherwise (5) (6) P (x
y) = where n > m.
An important issue is the decision on the values of n and m. If the entities x and y have l events sharing the same cell and time interval, one must look for all possible pairs that satisfy this property. Since the number of users in the intersection are smaller and is expected to decrease rapidly for large l values the probability of two users in respective services being the same user with the same track will be considerably high.
It is fair to assume that both the systems have considerable amount of common entities which will match. This commonality needs to be calculated empirically by ground truth values. After this value is found we can use this value to limit the k values (e.g. k 2 [k1 : k2]) when calculating the probabilities and the probability in Theorem turns to: P (x y) =
Pkk==kk21 P M (n 1; m 1; k
1)
Pkk==kk21 P M (n; m; k)
One can relax the condition of equality for the tracking based on the location accuracy of the services and the chosen grid sizes. Moreover, similar to the diversity concept of the k-l diversity model, the distance among the shared cells could be used to distinguish between multiple pairs sharing a common user, with close matching probabilities, i.e. P (x y) = P (x z). 3.
The second component of this doctoral work is the
framework to perform the linkage e ciently. Nave record linkage
algorithms that compare every pair of records take O(n2)
time [
The ST-Link algorithm uses two ltering steps before pairwise comparisons of candidate entities are performed to compute the nal linkage. It rst distributes entities (users) over coarse-grained geographical regions that we call dominating grid cells. Such grid cells contain most of the activities of their users. For two users to link, they must have a common dominating grid. Once this step is over, the linkage is independently performed over each dominating grid cell. To identify the dominating grids, we make a sequential scan over all records, and utilize a quad-tree based index, which limits the area of the smallest grid from below. During the temporal ltering step, ST-Link uses a sliding window based scan to build candidate user pairs, while also pruning this = = (
0; P M (n
1; m 1; m
P M (n; m; m) CM (n 1; m
CM (n; m) 1) = 1) 1 n 1 max(jGkI(t)j;jGkE (t)j) ; if Gx(t) = Gy(t) = Gk otherwise (2) (3) (4) This is an intuitive result since a random entity from the smaller set can be equal to any element in the larger set with an equal probability. list as alibis are encountered for the current candidate pairs. Finally, our complete linkage model is evaluated over candidate pairs of users that remain following the spatial and temporal ltering steps. During this linkage step, we will need the time sorted events of the users at hand. For that purpose, during the forward scan, we also create a disk-based index sorted by the user id and event time. This index enables us to quickly iterate over the events of a given user in timestamp order, which is an operation used by the linkage step. Also, if one of the datasets is more sparse than the other, it performs the linkage by iterating over the users of the dense datasets rst, making sure their events are loaded only once. This is akin to the classical join ordering heuristic in databases.
Our experimental evaluation shows that k-l diversity model is e ective (up to 89% precision and 61% recall), yet the e ciency could bene t from a distributed approach. However, distributed processing is challenging due to mobility of users, and the scale of the data. First, distributing records based on their spatio-temporal features would spread records of a single user to multiple processing nodes, hence lead to high inter-machine communications cost. While the concept of dominating grid cells addresses this issue, scalability would still su er from spatial skew of real data (in our experiments %18 of all records were residing on a single grid out of 120 grids). Since the temporal ltering techniques requires at least one batch of data to reside at the same machine (this issue exists in both models either for ltering or aggregating), records cannot be written to machines in parallel which would lead to low write performance. With these challenges identi ed, we are going to focus on optimizations of both models to create a single optimized framework which could e ciently perform linkage for both models. Such framework would be bene cial for both industry and academia when performing aggregation of semantically di erent datasets for social good applications, and when benchmarking the linkage research.
Record Linkage. One of the earliest appearances of the
term record linkage is by Newcombe et al. [
Spatial Record Linkage and Spatial Joins. Many join
algorithms are proposed in the literature for spatial data [
User Identi cation. Our work has commonalities with
the work done in the area of user identi cation. For instance,
de Montjoye et al. [
In this paper, we introduced two linkage models for matching users across location enhanced services, and discussed implementation techniques. We have already realized a single machine implementation of the k-l diversity model with ST-Link algorithm. We are now working on validation and implementation of the probabilistic model, and aim to compare these two models with each other. Our single machine implementations showed that both models could bene t from a parallelized distributed implementation. Therefore, we set the development of a distributed and generic framework as the future goal of this doctoral work. 6.