  We are witnessing an enormous growth in the volume of data generated by
various online services. An important portion of this data contains geographic
references, since many of these services are \emph{location-enhanced} and thus
produce spatio-temporal records of their usage. We postulate that the
spatio-temporal usage records belonging to the same real-world entity can be
matched across records from different location-enhanced services. Linking
spatio-temporal records enables data analysts and service providers to obtain
information that they cannot derive by analyzing only one set of usage records.
In this paper, we develop a new \emph{linkage model} that can be used to match
entities from two sets of spatio-temporal usage records belonging to two
different location-enhanced services. This linkage model is based on the
concept of $k$-$l$ \emph{diversity} --- that we developed to capture both
spatial and temporal aspects of the linkage. To realize this linkage model in
practice, we develop a scalable linking algorithm called \emph{ST-Link}, which
makes use of effective spatial and temporal filtering mechanisms that
significantly reduce the search space for matching users. Furthermore,
\emph{ST-Link} utilizes sequential scan procedures to avoid random disk access
and thus scales to large datasets. We evaluated our work with respect to
accuracy and performance using several datasets. Experiments show that
\emph{ST-Link} is effective in practice for performing spatio-temporal linkage
and can scale to large datasets.
