Computing with Spatial Trajectories

A spatial trajectory is a sequences of (x,y) points, each with a time stamp. This chapter discusses low-level preprocessing of trajectories. First, it discusses how to reduce the size of data required to store a trajectory, in order to save storage costs and reduce redundant data. The data reduction techniques can run in a batch mode after the data is collected or in an on-line mode as the data is collected. Part of this discussion consists of methods to measure the error introduced by the data reduction techniques. The second part of the chapter discusses methods for filtering spatial trajectories to reduce measurement noise and to estimate higher level properties of a trajectory like its speed and direction. The methods include mean and median filtering, the Kalman filter, and the particle filter.

The traveling history of moving objects such as a person, a vehicle, or an animal have been exploited in various applications. The utility of trajectory data depends on the effective and efficient trajectory query processing in trajectory databases. Trajectory queries aim to evaluate spatiotemporal relationships among spatial data objects. In this chapter, we classify trajectory queries into three types, and introduce the various distance measures encountered in trajectory queries. The access methods of trajectories and the basic query processing techniques are presented as another component of this chapter.

This chapter presents a systematic overview of the various issues and solutions related to the notion of uncertainty in the settings of moving objects trajectories. The sources of uncertainty in this context are plentiful: from the mere fact that the positioning devices are inherently imprecise, to the pragmatic aspect that, although the objects are moving continuously, location-based servers can only be updated in discrete times. Hence come the problems related to modelling and representing the uncertainty in Moving Objects Databases (MOD) and, as a consequence, problems of efficient algorithms for processing various spatio-temporal queries of interest. Given the ever-presence of uncertainty since the dawn of philosophy through modern day nano-level science, after a brief introduction, we present a historic overview of the role of uncertainty in parts of the evolution of the human thought in general, and Computer Science (CS) and databases in particular, which are relevant to this chapter. The focus of this chapter, however, will be on the impact that capturing the uncertainty in the syntax of the popular spatio-temporal queries has on their semantics and processing algorithms. We also consider the impact of different models in different settings – e.g., free motion; road-network constrained motion – and discuss the main issues related to exploiting such semantic dimension( s) for efficient query processing.

The ubiquity of mobile devices with global positioning functionality (e.g., GPS and Assisted GPS) and Internet connectivity (e.g., 3G and Wi-Fi) has resulted in widespread development of location-based services (LBS). Typical examples of LBS include local business search, e-marketing, social networking, and automotive traffic monitoring. Although LBS provide valuable services for mobile users, revealing their private locations to potentially untrusted LBS service providers pose privacy concerns. In general, there are two types of LBS, namely, snapshot and continuous LBS. For snapshot LBS, a mobile user only needs to report its current location to a service provider once to get its desired information. On the other hand, a mobile user has to report its location to a service provider in a periodic or on-demand manner to obtain its desired continuous LBS. Protecting user location privacy for continuous LBS is more challenging than snapshot LBS because adversaries may use the spatial and temporal correlations in the user's a sequence of location samples to infer the user's location information with a higher degree of certainty. Such user spatial trajectories are also very important for many applications, e.g., business analysis, city planning, and intelligent transportation. However, publishing original spatial trajectories to the public or a third party for data analysis could pose serious privacy concerns. Privacy protection in continuous LBS and trajectory data publication has increasingly drawn attention from the research community and industry. In this chapter, we describe the state-of-the-art privacy-preserving techniques for continuous LBS and trajectory publication.

In step with the rapidly growing volumes of available moving-object trajectory data, there is also an increasing need for techniques that enable the analysis of trajectories. Such functionality may benefit a range of application area and services, including transportation, the sciences, sports, and prediction-based and social services, to name but a few. The chapter first provides an overview trajectory patterns and a categorization of trajectory patterns from the literature. Next, it examines relative motion patterns, which serve as fundamental background for the chapter's subsequent discussions. Relative patterns enable the specification of patterns to be identified in the data that refer to the relationships of motion attributes among moving objects. The chapter then studies disc-based and density-based patterns, which address some of the limitations of relative motion patterns. The chapter also reviews indexing structures and algorithms for trajectory pattern mining.

In today's world, we have increasingly sophisticated means to record the movement of humans and other moving objects in the form of trajectory data. These data are being accumulated at an extremely fast rate. As a result, knowledge discovery from these data for recognizing activities has become an important problem. The discovered activity patterns can help us understand people's lives, analyze traffic in a large city and study social networks among people. Trajectory-based activity recognition builds upon some fundamental functions of location estimation and machine learning, and can provide new insights on how to infer high-level goals and objectives from low-level sensor readings. In this chapter, we survey the area of trajectory-based activity recognition. We start from research in location estimation from sensors for obtaining the trajectories. We then review trajectory-based activity recognition research. We classify the research work on trajectory-based activity recognition into several broad categories, and systematically summarize existing work as well as future works in light of the categorization.

This chapter discusses the analysis and use of trajectories from vehicles on roads. It begins with techniques for creating a road map from GPS logs, which is a potentially less expensive way to make up-to-date road maps than traditional methods. Next is a discussion of map matching. This is a collection of techniques to infer which road a vehicle was on given noisy measurements of its location. Map matching is a prerequisite for the next two topics: location prediction and route learning. Location prediction works to anticipate where a vehicle is going, and it can be used to warn drivers of upcoming traffic situations as well as give advertising and alerts about future points of interest. Route learning consists of techniques for automatically creating good route suggestions based on the trajectories of one or more drivers.

In this chapter, we introduce and define the meaning of location-based social network (LBSN) and discuss the research philosophy behind LBSNs from the perspective of users and locations. Under the circumstances of trajectory-centric LBSN, we then explore two fundamental research points concerned with understanding users in terms of their locations. One is modeling the location history of an individual using the individual's trajectory data. The other is estimating the similarity between two different people according to their location histories. The inferred similarity represents the strength of connection between two users in a locationbased social network, and can enable friend recommendations and community discovery. The general approaches for evaluating these applications are also presented.

While chapter 8 studies the research philosophy behind a location-based social network (LBSN) from the point of view of users, this chapter gradually explores the research into LBSNs from the perspective of locations. A series of research topics are presented, with respect to mining the collective social knowledge from many users' GPS trajectories to facilitate travel. On the one hand, the generic travel recommendations provide a user with the most interesting locations, travel sequences, and travel experts in a region, as well as an effective itinerary conditioned by a user's starting location and an available time length. On the other hand, the personalized travel recommendations find the locations matching an individual's interests, which can be learned from the individual's historical data.