Recent advances in communication and information technology, such as the increasing accuracy of GPS technology and the miniaturization of wireless communication devices pave the road for Location–Based Services (LBS). To achieve high quality for such services, spatio–temporal data mining techniques are needed. In this paper, we describe experiences with spatio–temporal rule mining in a Danish data mining company. First, a number of real world spatio–temporal data sets are described, leading to a taxonomy of spatio–temporal data. Second, the paper describes a general methodology that transforms the spatio–temporal rule mining task to the traditional market basket analysis task and applies it to the described data sets, enabling traditional association rule mining methods to discover spatio–temporal rules for LBS. Finally, unique issues in spatio–temporal rule mining are identified and discussed.

Creating complex spatio–temporal simulation models is a hot issue in the area of spatio–temporal databases [7]. While existing Moving Object Simulators (MOSs) address different physical aspects of mobility, they neglect the important social and geo–demographical aspects of it. This paper presents ST–ACTS, a Spatio–Temporal ACTivity Simulator that, using various geo–statistical data sources and intuitive principles, models the so far neglected aspects. ST–ACTS considers that (1) objects (representing mobile users) move from one spatio–temporal location to another with the objective of performing a certain activity at the latter location; (2) not all users are equally likely to perform a given activity; (3) certain activities are performed at certain locations and times; and (4) activities exhibit regularities that can be specific to a single user or to groups of users. Experimental results show that ST-ACTS is able to effectively generate realistic spatio–temporal distributions of activities, which make it essential for the development of adequate spatio–temporal data management and data mining techniques.

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.

Transportation–related problems, like road congestion, parking, and pollution, are increasing in most cities. In order to reduce traffic, recent work has proposed methods for vehicle sharing, for example for sharing cabs by grouping “closeby” cab requests and thus minimizing transportation cost and utilizing cab space. However, the methods published so far do not scale to large data volumes, which is necessary to facilitate large–scale collective transportation systems, e.g., ride–sharing systems for large cities.

This paper presents highly scalable trip grouping algorithms, which generalize previous techniques and support input rates that can be orders of magnitude larger. The following three contributions make the grouping algorithms scalable. First, the basic grouping algorithm is expressed as a continuous stream query in a data stream management system to allow for a very large flow of requests. Second, following the divide–and–conquer paradigm, four space–partitioning policies for dividing the input data stream into sub–streams are developed and implemented using continuous stream queries. Third, using the partitioning policies, parallel implementations of the grouping algorithm in a parallel computing environment are described. Extensive experimental results show that the parallel implementation using simple adaptive partitioning methods can achieve speed–ups of several orders of magnitude without significantly degrading the quality of the grouping.

Delivering ‘relevant’ advertisements to consumers carrying mobile devices is regarded by many as one of the most promising mobile business opportunities. The relevance of a mobile ad depends on at least two factors: (1) the proximity of the mobile consumer to the product or service being advertised, and (2) the match between the product or service and the interest of the mobile consumer. The interest of the mobile consumer can be either explicit (expressed by the mobile consumer) or implicit (inferred from user characteristics). This paper tries to empirically estimate the capacity of the Mobile Advertising channel, i.e. the number of relevant ads that can be delivered to mobile consumers. The estimations are based on a simulated mobile consumer population and simulated mobile ads. Both of the simulated data sets are realistic and derived based on real-world data sources about population geo-demographics, businesses offering products or services, and related consumer surveys. The estimations take into consideration both the proximity and interest requirements of mobile ads, i.e. ads are delivered only to mobile consumers that are close-by and are interested, where interest is either explicit or implicit. Results show that the capacity of the Location-Based Advertising channel is rather large, which is evidence for a strong business case, but it also indicates the need for user-control of the received mobile ads.

The popularity of embedded positioning technologies in mobile devices and the development of mobile communication technology have paved the way for powerful location-based services (LBSs). To make LBSs useful and user–friendly, heavy use is made of context information, including patterns in user location data which are extracted by data mining methods. However, there is a potential conflict of interest: the data mining methods want as precise data as possible, while the users want to protect their privacy by not disclosing their exact movements. This paper aims to resolve this conflict by proposing a general framework that allows user location data to be anonymized, thus preserving privacy, while still allowing interesting patterns to be discovered. The framework allows users to specify individual desired levels of privacy that the data collection and mining system will then meet. Privacy-preserving methods are proposed for a core data mining task, namely finding dense spatio–temporal regions. An extensive set of experiments evaluate the methods, comparing them to their non-privacy-preserving equivalents. The experiments show that the framework still allows most patterns to be found, even when privacy is preserved.

In order to provide context–aware Location–Based Services, real location data of mobile users must be collected and analyzed by spatio–temporal data mining methods. However, the data mining methods need precise location data, while the mobile users want to protect their location privacy. To remedy this situation, this paper first formally defines novel location privacy requirements. Then, it briefly presents a system for privacy–preserving trajectory collection that meets these requirements. The system is composed of an untrusted server and clients communicating in a P2P network. Location data is anonymized in the system using data cloaking and data swapping techniques. Finally, the paper empirically demonstrates that the proposed system is effective and feasible.

The efficient analysis of spatio–temporal data, generated by moving objects, is an es-sential requirement for intelligent locationbased services. Spatio-temporal rules can befound by constructing spatio–temporal baskets, from which traditional association rulemining methods can discover spatio–temporal rules. When the items in the baskets arespatio–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 requent 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 subroutes of long routes. A SQL–based implementation is described, and experiments on real life data show the effectiveness of the method.

Delivering “relevant” advertisements to consumers carrying mobile devices is regarded by many as one of the most promising mobile business opportunities. The relevance of a mobile ad depends on at least two factors: (1) the proximity of the mobile consumer to the product or service being advertised, and (2) the match between the product or service and the interest of the mobile consumer. The interest of the mobile consumer can be either explicit (expressed by the mobile consumer) or implicit (inferred from user characteristics). This paper tries to empirically estimate the capacity of the mobile advertising channel, i.e., the number of relevant ads that can be delivered to mobile consumers. The estimations are based on a simulated mobile consumer population and simulated mobile ads. Both of the simulated data sets are realistic and derived based on real world data sources about population geo–demographics, businesses offering products or services, and related consumer surveys. The estimations take into consideration both the proximity and interest requirements of mobile ads, i.e., ads are only delivered to mobile consumers that are close-by and are interested, where interest is either explicit or implicit. Results show that the capacity of the LBA channel is rather large, which is evidence for a strong business case, but also indicate the need for user–control of the received mobile ads.