The book “Computing with Spatial trajectories” is a classic book on spatial trajectories co-authored by Dr. Zheng Yu while working at Microsoft Research Asia with Professor Zhou Xiaofang of the University of Queensland. Electronic address: http://www.doc88.com/p-4781605475300.html There is no Chinese version of the book at present, the online shopping price is about 1200 yuan, here is a link to JINGdong, after all, now Dr. Zheng Yu is the vice president of Jingdong and chief data scientist of Jingdong digital Technology. Without further ado, the following is a translation of the preface of the book.
preface
Space trajectoryThe trajectory of an object as it moves through geographic space, usually as a series of points arranged conveniently by time, e.g
Due to the progress of positioning and wireless communication technology, mobile computing systems and location-based services (LBS) are rapidly becoming popular, which leads to the generation of spatial tracks representing various moving objects, such as people, vehicles, animals and various natural phenomena in indoor or outdoor environments. Here are some examples.
1) Mobility: People have been using spatial trajectories to record their movements in the real world, either passively or actively. – Active recording: for example, travelers actively record their travel routes with GPS tracks and post them in their personal space to share their experiences with friends. Cyclists or joggers can record their exercise footprints for analysis. In Flickr, each photo with a location tag to indicate where it was taken and a timestamp to indicate when it was taken can make a series of spatial tracks with geotagged photos. Similarly, the check-ins in the corresponding area can be viewed as a chronological track.
- Passive recording: When the user carries a mobile phone, through information interaction with the corresponding mobile phone signal tower, the location information represented by the ID of the mobile phone signal tower and the time record of switching between service areas are inadvertently left, as well as a rich spatial track. Credit card transactions can also indicate the holder’s spatial movements, since each transaction contains a timestamp and a merchant ID that indicates the location of the transaction.
2) Movement of vehicles: In recent years, a large number of vehicles equipped with GPS have appeared in our lives. For example, there are a large number of taxis equipped with GPS sensors in major cities, enabling them to send time-marked location information to the data center at a certain frequency. Such reports generate a large number of spatial tracks that can be used for traffic resource optimization, safety management and flow analysis.
3) The movement of animals and natural phenomena: biologists need research projects to understand the movements of animals such as migratory birds. Climatologists, too, are busy collecting the tracks of natural phenomena such as hurricanes, tornadoes and ocean currents. These tracks provide scientists with a wealth of information about their subjects.
All in all, spatial trajectories have provided us with an unprecedented wealth of information to study and understand moving objects, which requires systematic research and development of new computing techniques for processing, retrieval, mining and exploration of more applications. Therefore, the calculation of spatial trajectory has become an increasingly important research topic and has attracted extensive attention. Within this research topic, there are many fields, including computer science, biology, sociology, geography and climatology.
Although there are many books on spatial database, mobile computing and data mining, it is the first book devoted to the calculation of spatial trajectory data, with a wide coverage and authoritative perspective. Aimed at senior undergraduates, graduate students, researchers and professionals, it covers the basics of spatial trajectory computing and key issues in the field. Each chapter is a tutorial on important aspects of spatial trajectory calculation, and contains many related research papers and valuable references. This book provides a comprehensive overview of spatial trajectory indexing, search, and data mining, as well as general concepts for research and program development, as well as new methods and applications to help researchers explore this exciting field. It also Outlines recent developments to attract researchers and other interested readers to this promising field of research.
We selected 17 researchers active in spatial trajectory computing from their specialties to contribute to the chapters of this book. The chapters of the book are organized as follows: “Trajectory preprocessing (before database) -> Trajectory Indexing and Retrieval (in database) -> Advanced Topics (outside database)”, as shown in Figure 1.
- The first two chapters of this book introduce the basis of spatial trajectory data processing: trajectory preprocessing (Chapter 1) and trajectory index and retrieval (Chapter 2).
- The second part is composed of six advanced topics: the uncertainty of space trajectory (chapter 3), the privacy of space trajectory (chapter 4), (chapter 5) trajectory model of mining, based on spatial trajectory motion recognition (chapter 6), driving analysis (chapter 7), and location based social networking applications (eighth and ninth chapter).
Specifically, the book will gradually introduce various concepts and techniques to solve some of the problems faced by new learners in this field, from initial data preprocessing to spatial motion trajectory, followed by uncertainty mining, privacy protection and trajectory pattern recognition. Finally, a series of advanced applications, including behavior recognition, driving and location-based social networking, are implemented using spatial motion trajectories. Here is a brief introduction to each chapter:
Chapter 1: Spatial trajectories carry a wealth of information that can be used in a variety of applications. We need to deal with many problems before using them. In general, the continuous motion of an object is approximately recorded in the form of discrete position sampling. High sampling rates generate accurate trajectory data, but lead to huge overhead in data storage, communication and processing. Therefore, it is necessary to design a technique that can compress the trajectory data and ensure the trajectory validity. At the same time, the track data usually produce noise due to outliers or poor signal of the positioning system. For example, when a vehicle is driving in an “urban canyon,” satellite signals are often poorly received by GPS devices, resulting in a series of coordinate points that are significantly different from their real location. In some cases, the offset was more than a mile. Therefore, it is very useful to design a technique to reduce trajectory noise for the system of such trajectory application. Therefore, it is necessary to preprocess the noise data with the filtering method of spatial trajectory technology. In order to solve these two problems, a data compression technique that can be run in batch mode (offline) and a data compression technique that can be processed online are presented in Chapter 1. The second part of this chapter introduces the methods used to filter and measure noise from spatial trajectories, including mean and median filtering, Kalman filtering and particle filtering. In conclusion, this chapter provides a basic framework for the preprocessing of spatial trajectories for beginners.
Chapter 2: The popularity of various location-based services leads to countless trajectory data, and computing these trajectory data is a huge burden for application systems. If the trajectory data is not well organized, obtaining information from the trajectory data will be a time-consuming job for branch factories. For example, retrieving a track that passes through an intersection is a simple task, but if these systems have to scan a large set of track data directly to retrieve it, such an online system is not feasible at all. In many cases, we may also need to search for specific trajectories that meet certain conditions, which requires retrieval through time and space constraints. For example, a tourist needs to retrieve the spatial trajectory through a specific area in a specific time frame to help him make travel plans. Practical applications require us to develop effective trajectory indexing and retrieval techniques. Therefore, in chapter 2, we introduce the method of querying the track data frequently in the database and the query process supported by the retrieval technology.
Chapter 3: After preprocessing and structuring the spatial trajectory data using relevant techniques, we can use them in various applications. However, locators are inherently imprecise, leading to a certain amount of uncertainty in the positions we obtain about moving objects. GPS sensor readings, for example, often have a positioning error of 10 meters or more. With such readings, it may be difficult to identify the exact location of an object of interest (such as a restaurant or a mall), especially in crowded urban areas. At the same time, objects move continuously, but their positions change only in discrete time, so there is uncertainty between the exact positions of the two updates. There are two reasons for the long update interval. One is to save energy consumption and the other is to save communication bandwidth. When the interval between updates is more than a few minutes or even order hours, the uncertainty of the spatial trajectory severely reduces its utility and presents new challenges in searching for moving objects.
In order to solve the above uncertainties, related concepts of uncertain space trajectory and various problems and solutions are introduced in Chapter 3. It introduces modeling issues and how to represent uncertainty in the Moving Object Database (MOD). Some efficient algorithms are also discussed to deal with different spatio-temporal query problems. Note that the query processing in Chapter 2 does not take into account the uncertainties of spatial trajectories, which are the focus of this chapter.
Chapter 4: Although LBS services provide many valuable applications for mobile users, there are privacy concerns that individuals’ private locations may be exposed to untrusted LBS service providers. How to strike a balance between the services provided by LBS service providers and the protection of user location privacy? The more accurately a user’s location is located, the better the quality of service can be provided, but the less privacy can be protected. Generally speaking, there are two types of LBS, namely snapshot LBS and continuous LBS services. For the LBS service of the snapshot type, mobile users report their current location to the service provider only when they need to obtain information. In fact, users do not feel the need to submit their exact location through the LBS system when using the service. For example, to find nearby hotels, users need only report a rough geographic area with current location information. Many articles have discussed protecting user snapshot locations, so chapter 4 will not cover that. On the other hand, users need to submit their location information to service providers periodically or on demand in order to obtain continuous LBS services (for example, to obtain real-time traffic information or to select the nearest gas station while driving). Protecting users’ location privacy on continuous LBS services is more challenging than snapshot LBS services, because malicious actors can use temporal and spatial correlation of users’ movement samples to accurately infer users’ location information. In short, if the original spatial trajectory is open to the public or third parties, it may cause serious privacy issues. Therefore, at present, the privacy protection of continuous LBS and corresponding trajectory data release has received the focus of the industry. In this case, we introduce the latest privacy protection technology of continuous LBS and spatial trajectory in Chapter 4.
Chapter 5: The large volume of spatial trajectories enables us to analyze the behavior patterns of moving objects, which can be represented by a single trajectory containing a certain pattern or multiple groups of similar patterns. It can also be a segment with similar properties but different trajectories (for example, a data set that defines a fixed range of time and space), or a set of all trajectories that satisfy the same conditions. These models can bring great value to practical applications, including transportation, biological research, sports, and social services. For example, finding different track clusters with similar patterns can help detect users’ driving routes or study birds’ migration routes. In addition, the identification of groups of people who exercise together, offer advice, or allow taxi sharing can facilitate the exploration of social relationships. Chapter 5 introduces and evaluates some existing literature on index structure and pattern mining for classification of trajectory model information according to different patterns.
Chapter 6: After the preprocessing, management and pattern mining of spatial trajectoryone may ask what applications can be made based on these trajectorydata. Behavior recognition is a core application that can utilize direct trajectory information. Intuitively, the human-generated spatial trajectory implies the user’s behavior and activity, so that some low-level sensor readings can provide new insights into the high-level user’s goals. First, a person’s activities can be used to trigger services that meet user needs. For example, if the user is known to be driving a vehicle, her mobile phone can automatically display traffic conditions on the road around the user and temporarily disable the phone’s entertainment function (for her safety) because it distracts the driver. If we know the user is in a meeting or watching a movie, then the user’s phone can be switched to silent mode. Second, multi-user activities enable us to mine collective behavior and help us analyze social networks and traffic information. If there are multiple users interacting with each other, we can make more accurate estimates based on the similarities between the two, so we can provide better social discovery services and suggestions about friends and locations.
Because of the richer data information provided by the snapshot location service, spatial trajectory also requires more advanced technology based on behavior recognition. To help new learners, Chapter 6 describes trail-based behavior recognition searches and classifies them.
Chapter seven: The trajectory of vehicles shows a strong connection with transportation, because driving is one of the most central links in our life. Abundant information can be obtained from these tracks, such as road network, traffic network and other information obtained from drivers’ behavior information, so as to give suggestions beneficial to driving experience from different aspects. For example, creating a road map based on GPS tracks is a cheaper way to get an up-to-date road map than the traditional way. On the other hand, based on the trajectory of one or more experienced drivers will produce more effective recommendations.
Chapter 7 introduces how driving behavior can benefit from the analysis of spatial motion trajectory. The following is a basic paradigm for application: “Creating road maps from GPS trajectories -> mapping drivers’ single movement trajectories to road networks -> mining effective driving routes -> learning specific driving habits based on preferences from drivers’ personalized driving route trajectories”.
Chapter 8 and 9: The advancement of location and mobile communication technology makes individual users also generate a variety of spatial trajectory, which means rich user behavior, interests and preferences and other information. More recently, people have started sharing their tracking data through online social networking services for different reasons, which has fostered a wave of track-centric LBSNS applications (location-based social networking). For example, a user can record his driving routes and share his travel experiences through GPS tracks in an online community, or analyze or share experiences through jogging logs and cycling activities. In addition, check-in-like apps “treat a user’s travel photos as a spatial trajectory” within Foursquare or Flickr apps. LBSNS, centered around these tracks, enable us to understand user behavior and location and explore their relationships.
On the one hand, we can get to know a person by discovering their similarity through the track between him and other different users, so as to provide personalized services, and also carry out friend recommendation and community discovery. On the other hand, we are able to recognize the location and, based on the user’s information and the relationship between the two different locations, provide the user with better suggestions for things like travel.
In chapter 8, location-based social networks are defined and the research philosophy of LBSNS is discussed from the perspective of users and locations. In the track-oriented LBSN, this chapter explores and concerns the following two basic questions for understanding the user’s location. One is the modeling of individual historical trajectory data for individual locations. Another is to estimate the similarity between two different users based on their historical location. Similarity represents the distance between two users of location-based social networks, through which friend recommendations or community discovery can be provided. Some of the available methods for profiling these applications are discussed, and some publicly available data sets are listed in Chapter 8.
Although Chapter 8 studies the research philosophy behind location-based social networks from the perspective of users, Chapter 9 will further explore and study LBSNS from the perspective of location. To facilitate travel, a series of research projects have mined collective behavior from users’ GPS tracks. The first is general travel advice, which provides the user with places of interest in a given area, travel sequences, travel experts, and an effective itinerary that is modulated by the user’s starting time and location. Second, personalized travel advice can find some content that matches the user’s personal interests, and these personalized suggestions can be collected from the user’s personal historical location data.
Finally, we hope that this book will provide you with a useful overview of the use of the guide, and for young people interested in the field of computing and spatial trajectories.
Microsoft Research Asia Yu Zheng Xiaofang Zhou, University of Queensland, Australia, July 2011