Change search
ReferencesLink to record
Permanent link

Direct link
Mining Long, Sharable Patterns in Trajectories of Moving Objects
Uppsala University, Department of Information Technology.ORCID iD: 0000-0003-1164-8403
Aalborg University, Department of Computer Science.
2009 (English)In: Geoinformatica, ISSN 1384-6175, E-ISSN 1573-7624, Vol. 13, no 1, 27-55 p.Article in journal (Refereed) Published
Abstract [en]

The efficient analysis of spatio-temporal data, generated by moving objects, is an essential requirement for intelligent location-based services. Spatio-temporal rules can be found by constructing spatio-temporal baskets, from which traditional association rule mining methods can discover spatio-temporal rules. When the items in the baskets are spatio-temporal identifiers and are derived from trajectories of moving objects, the discovered rules represent frequently travelled routes. For some applications, e.g., an intelligent ridesharing application, these frequent routes are only interesting if they are long and sharable, i.e., can potentially be shared by several users. This paper presents a database projection based method for efficiently extracting such long, sharable frequent routes. The method prunes the search space by making use of the minimum length and sharable requirements and avoids the generation of the exponential number of sub-routes of long routes. Considering alternative modelling options for trajectories, leads to the development of two effective variants of the method. SQL-based implementations are described, and extensive experiments on both real life- and large-scale synthetic data show the effectiveness of the method and its variants.

Place, publisher, year, edition, pages
2009. Vol. 13, no 1, 27-55 p.
Keyword [en]
intelligent transportation systems, ride-sharing, moving object trajectories, spatio-temporal data, mining, frequent itemset mining, SQL-based pattern mining
National Category
Computer Science
URN: urn:nbn:se:kth:diva-82001DOI: 10.1007/s10707-007-0042-zISI: 000262396900002OAI: diva2:499980
QC 20120217Available from: 2012-02-13 Created: 2012-02-11 Last updated: 2012-02-17Bibliographically approved
In thesis
1. Spatio-Temporal Data Mining for Location-Based Services
Open this publication in new window or tab >>Spatio-Temporal Data Mining for Location-Based Services
2008 (English)Doctoral thesis, comprehensive summary (Other academic)
Abstract [en]

Largely driven by advances in communication and information technology, such as the increasing availability and accuracy of GPS technology and the miniaturization of wireless communication devices, Location–Based Services (LBS) are continuously gaining popularity. Innovative LBSes integrate knowledge about the users into the service. Such knowledge can be derived by analyzing the location data of users. Such data contain two unique dimensions, space and time, which need to be analyzed.

The objectives of this thesis are three–fold. First, to extend popular data mining methods to the spatio–temporal domain. Second, to demonstrate the usefulness of the extended methods and the derived knowledge in two promising LBS examples. Finally, to eliminate privacy concerns in connection with spatio–temporal data mining by devising systems for privacy–preserving location data collection and mining.


To this extent, Chapter 2 presents a general methodology, pivoting, to extend a popular data mining method, namely rule mining, to the spatio–temporal domain. By considering the characteristics of a number of real–world data sources, Chapter 2 also derives a taxonomy of spatio–temporal data, and demonstrates the usefulness of the rules that the extended spatio–temporal rule mining method can discover. In Chapter 4 the proposed spatio–temporal extension is applied to find long, sharable patterns in trajectories of moving objects. Empirical evaluations show that the extended method and its variants, using high–level SQL implementations, are effective tools for analyzing trajectories of moving objects.

Real–world trajectory data about a large population of objects moving over extended periods within a limited geographical space is difficult to obtain. To aid the development in spatio–temporal data management and data mining, Chapter 3 develops a Spatio–Temporal ACTivity Simulator (ST–ACTS). ST–ACTS uses a number of real–world geo–statistical data sources and intuitive principles to effectively generate realistic spatio–temporal activities of mobile users.


Chapter 5 proposes an LBS in the transportation domain, namely cab–sharing. To deliver an effective service, a unique spatio–temporal grouping algorithm is presented and implemented as a sequence of SQL statements. Chapter 6 identifies ascalability bottleneck in the grouping algorithm. To eliminate the bottleneck, the chapter expresses the grouping algorithm as a continuous stream query in a data stream management system, and then devises simple but effective spatio–temporal partitioning methods for streams to parallelize the computation. Experimental results show that parallelization through adaptive partitioning methods leads to speed–ups of orders of magnitude without significantly effecting the quality of the grouping. Spatio–temporal stream partitioning is expected to be an effective method to scale computation–intensive spatial queries and spatial analysis methods for streams.


Location–Based Advertising (LBA), the delivery of relevant commercial information to mobile consumers, is considered to be one of the most promising business opportunities amongst LBSes. To this extent, Chapter 7 describes an LBA framework and an LBA database that can be used for the management of mobile ads. Using a simulated but realistic mobile consumer population and a set of mobile ads, the LBA database is used to estimate the capacity of the mobile advertising channel. The estimates show that the channel capacity is extremely large, which is evidence for a strong business case, but it also necessitates adequate user controls.


When data about users is collected and analyzed, privacy naturally becomes a concern. To eliminate the concerns, Chapter 8 first presents a grid–based framework in which location data is anonymized through spatio–temporal generalization, and then proposes a system for collecting and mining anonymous location data. Experimental results show that the privacy–preserving data mining component discovers patterns that, while probabilistic, are accurate enough to be useful for many LBSes.


To eliminate any uncertainty in the mining results, Chapter 9 proposes a system for collecting exact trajectories of moving objects in a privacy–preserving manner. In the proposed system there are no trusted components and anonymization is performed by the clients in a P2P network via data cloaking and data swapping. Realistic simulations show that under reasonable conditions and privacy/anonymity settings the proposed system is effective.

Place, publisher, year, edition, pages
Department of Computer Science, Aalborg University, 2008. 198 p.
, Ph.D. Thesis, ISSN 1601-0590 ; 44
spatio-temporal data mining; location-based services; location and trajectory anonymization
National Category
Computer Science
urn:nbn:se:kth:diva-86310 (URN)
Public defence
2008-03-11, 0.2.13, Aalborg University, Selma Lagerløfs vej 300, Aalborg, 14:00 (English)
QC 20120215Available from: 2012-02-15 Created: 2012-02-13 Last updated: 2012-02-15Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full text

Search in DiVA

By author/editor
Gidofalvi, Gyözö
In the same journal
Computer Science

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 101 hits
ReferencesLink to record
Permanent link

Direct link