kth.sePublications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Efficient Map Matching and Discovery of Frequent and Dominant Movement Patterns in GPS Trajectory Data
KTH, School of Architecture and the Built Environment (ABE), Urban Planning and Environment, Geoinformatics.ORCID iD: 0000-0001-5361-6034
2020 (English)Doctoral thesis, comprehensive summary (Other academic)
Abstract [en]

The wide deployment of Global Positioning System (GPS) sensors for movement data collection has enabled a wide range of applications in transportation and urban planning. Frequent and dominant movement patterns embedded in GPS trajectory data provide valuable knowledge including the spatial and temporal distribution of frequent routes selected by the tracked objects and the regular movement behavior in certain regions. Discovering frequent and dominant movement patterns embedded in GPS trajectory data needs to address several tasks including (1) matching noisy trajectories to the road network (referred as map matching), (2) extracting frequent and dominant movement patterns, and (3) retrieving the distribution of these patterns over user-specified attribute (e.g., timestamp, travel mode, etc.). These tasks confront several challenges in observation error, efficiency and large pattern search space.

To address those challenges, this thesis develops a set of algorithms and tools for efficient map matching and discovery of frequent and dominant movement patterns in GPS trajectory data. More specifically, two map matching algorithms are first developed, which improve the performance by precomputation and A-star search. Subsequently, a frequent route is extracted from map matched trajectories as a Contiguous Sequential Pattern (CSP). A novel CSP mining algorithm is developed by performing bidirectional pruning to efficiently search CSP and reduce redundancy in the result. After that, an efficient CSP comparison algorithm is developed to extend the bidirectional pruning to compare multiple sets of CSP. By comparing CSP mined from trajectories partitioned by a user-specified attribute, the distribution of frequent routes in the attribute space can be obtained. Finally, Regional Dominant Movement Pattern (RDMP) in trajectory data is discovered as regions where most of the objects follow a specific pattern. A novel movement feature descriptor called Directional Flow Image (DFI) is proposed to capture local directional movement information of trajectories in a multiple channel image and a convolutional neural network model is designed for DFI classification and RDMP detection.

Comprehensive experiments on both real-world and synthetic GPS datasets demonstrate the efficiency of the proposed algorithms as well as their superiority over state-of-the-art methods. The two map matching algorithms achieve considerable performance in matching densely sampled GPS data to small scale network and sparsely sampled GPS data to large scale network respectively. The CSP mining and comparison algorithms significantly outperform their competitors and effectively retrieve both spatial and temporal distribution of frequent routes. The RDMP detection method can robustly discover ten classes of commonly encountered RDMP in real-world trajectory data. The proposed methods in this thesis collectively provide an effective solution for answering sophisticated queries concerning frequent and dominant movement patterns in GPS trajectory data.

Abstract [sv]

Den utbredda användningen av GPS-sensorer (Global Positioning System) för insamling av rörelsedata har möjliggjort ett brett spektrum av tillämpningar inom transport- och stadsplanering. Frekventa och dominerande rörelsemönster som döljs i GPS-trajektorier ger värdefull kunskap, vilken omfattar den rumsliga och tidsmässiga fördelningen av rutter som frekvent väljs av de spårade föremålen samt det regelbundna rörelsebeteendet i vissa regioner. För att upptäcka frekventa och dominerande rörelsemönster gömda i GPS-trajektorier måste man ta itu med flera uppgifter, däribland (1) att matcha brusiga trajektorier till vägnätet (så kallad kartmatchning), (2) utvinna frekventa och dominerande rörelsemönster och (3) att erhålla fördelningen av dessa mönster över användardefinierat attribut (t.ex. tidsstämpel, reseläge, etc.). Dessa uppgifter står inför flera utmaningar i fråga om observationsfel, effektivitet och stora sökrum av mönster.

För att hantera dessa utmaningar utvecklar denna avhandling en antal algoritmer och verktyg för effektiv kartmatchning och utvinning av frekventa och dominerande rörelsemönster i GPS-trajektorier. Mer specifikt utvecklas först två kartmatchningsalgoritmer som förbättrar prestandan genom förberäkning och A-star sökning. Därefter utvinns en frekvent rutt från kartmatchade trajektorier som ett sammanhängande sekventiellt mönster (CSP). En ny CSP-utvinningsalgoritm har utvecklats genom att utföra dubbelriktad beskärning för att effektivt söka efter CSP och minska redundansen i resultatet. Därefter utvecklas en effektiv algoritm för CSP-jämförelse för att utvidga dubbelriktad beskärning för att jämföra flera uppsättningar CSP. Genom att jämföra CSP som extraheras från trajektorier partitionerade av ett användardefinierat attribut kan fördelningen av frekventa rutter i attributrummet erhållas. Slutligen upptäcks regionalt dominerande rörelsemönster (RDMP) i trajektoriedata i form av regioner där de flesta föremål följer ett specifikt mönster. En ny beskrivning av rörelseattribut som kallas Directional Flow Image (DFI) föreslås för att fånga lokal riktad rörelseinformation för trajektorier i en bild med flera kanaler och en konvolutionell neuralt nätverksmodell utformas för DFI-klassificering och RDMP-detektion.

Omfattande experiment på både verkliga och syntetiska GPS-datamängder visar effektiviteten hos de föreslagna algoritmerna samt deras överlägsenhet över toppmoderna metoder. De två kartmatchningsalgoritmerna uppnår avsevärd prestanda när de matchar tätt samplade GPS-data till småskaliga nätverk och glest samplade GPS-data till storskaliga nätverk. CSP-utvinning- och jämförelsesalgoritmerna överträffar klart sina konkurrenter och hittar effektivt både rumslig och tidsmässig fördelning av frekventa rutter. RDMP-detekteringsmetoden kan på ett robust sätt upptäcka tio klasser av vanligt förekommande RDMP i verkliga trajektoriedata. De föreslagna metoderna i denna avhandling ger tillsammans en effektiv lösning för att svara på sofistikerade frågor om frekventa och dominerande rörelsemönster i GPS-trajektoriedata.

Place, publisher, year, edition, pages
Stockholm: KTH Royal Institute of Technology, 2020. , p. 62
Series
TRITA-ABE-DLT ; 2041
Keywords [en]
map matching, contiguous sequential pattern mining, contiguous sequential pattern comparison, movement pattern detection
Keywords [sv]
Kartmatchning, sammanhängande sekventiellt mönster utvinning, sammanhängande sekventiellt mönster jämförelse, rörelsemönster detektering
National Category
Transport Systems and Logistics Geosciences, Multidisciplinary
Research subject
Geodesy and Geoinformatics, Geoinformatics
Identifiers
URN: urn:nbn:se:kth:diva-286318ISBN: 978-91-7873-734-5 (print)OAI: oai:DiVA.org:kth-286318DiVA, id: diva2:1503570
Public defence
2020-12-16, Videolänk via Zoom - https://kth-se.zoom.us/j/61742782011, Du som saknar datorvana kan kontakta Gyözö Gidofalvi gyozo.gidofalvi@abe.kth.se / Use this e-mail address if you need technical assistance, Stockholm, 13:00 (English)
Opponent
Supervisors
Note

QC 20201125

Available from: 2020-11-25 Created: 2020-11-24 Last updated: 2022-06-25Bibliographically approved
List of papers
1. Fast map matching, an algorithm integrating hidden Markov model with precomputation
Open this publication in new window or tab >>Fast map matching, an algorithm integrating hidden Markov model with precomputation
2017 (English)In: International Journal of Geographical Information Science, ISSN 1365-8816, E-ISSN 1365-8824, p. 1-24Article in journal (Refereed) Published
Abstract [en]

Wide deployment of global positioning system (GPS) sensors has generated a large amount of data with numerous applications in transportation research. Due to the observation error, a map matching (MM) process is commonly performed to infer a path on a road network from a noisy GPS trajectory. The increasing data volume calls for the design of efficient and scalable MM algorithms. This article presents fast map matching (FMM), an algorithm integrating hidden Markov model with precomputation, and provides an open-source implementation. An upper bounded origin-destination table is precomputed to store all pairs of shortest paths within a certain length in the road network. As a benefit, repeated routing queries known as the bottleneck of MM are replaced with hash table search. Additionally, several degenerate cases and a problem of reverse movement are identified and addressed in FMM. Experiments on a large collection of real-world taxi trip trajectories demonstrate that FMM has achieved a considerable single-processor MM speed of 25,000–45,000 points/second varying with the output mode. Investigation on the running time of different steps in FMM reveals that after precomputation is employed, the new bottleneck is located in candidate search, and more specifically, the projection of a GPS point to the polyline of a road edge. Reverse movement in the result is also effectively reduced by applying a penalty.

Place, publisher, year, edition, pages
Taylor & Francis, 2017
Keywords
Map matching, precomputation, performance improvement
National Category
Transport Systems and Logistics
Research subject
Geodesy and Geoinformatics
Identifiers
urn:nbn:se:kth:diva-217993 (URN)10.1080/13658816.2017.1400548 (DOI)000422691100006 ()2-s2.0-85033662435 (Scopus ID)
Note

QC 20171121

Available from: 2017-11-20 Created: 2017-11-20 Last updated: 2024-03-15Bibliographically approved
2. Mining and visual exploration of closed contiguous sequential patterns in trajectories
Open this publication in new window or tab >>Mining and visual exploration of closed contiguous sequential patterns in trajectories
2018 (English)In: International Journal of Geographical Information Science, ISSN 1365-8816, E-ISSN 1365-8824, Vol. 32, no 7, p. 1282-1303Article in journal (Refereed) Published
Abstract [en]

Large collections of trajectories provide rich insight into movement patterns of the tracked objects. By map matching trajectories to a road network as sequences of road edge IDs, contiguous sequential patterns can be extracted as a certain number of objects traversing a specific path, which provides valuable information in travel demand modeling and transportation planning. Mining and visualization of such patterns still face challenges in efficiency, scalability, and visual cluttering of patterns. To address these challenges, this article firstly proposes a Bidirectional Pruning based Closed Contiguous Sequential pattern Mining (BP-CCSM) algorithm. By employing tree structures to create partitions of input sequences and candidate patterns, closeness can be checked efficiently by comparing nodes in a tree. Secondly, a system called Sequential Pattern Explorer for Trajectories (SPET) is built for spatial and temporal exploration of the mined patterns. Two types of maps are designed where a conventional traffic map gives an overview of the movement patterns and a dynamic offset map presents detailed information according to user-specified filters. Extensive experiments are performed in this article. BP-CCSM is compared with three other state-of-the-art algorithms on two datasets: a small public dataset containing clickstreams from an e-commerce and a large global positioning system dataset with more than 600,000 taxi trip trajectories. The results show that BP-CCSM considerably outperforms three other algorithms in terms of running time and memory consumption. Besides, SPET provides an efficient and convenient way to inspect spatial and temporal variations in closed contiguous sequential patterns from a large number of trajectories.

Place, publisher, year, edition, pages
Taylor & Francis, 2018
Keywords
Closed contiguous sequential pattern, trajectory pattern mining, trajectory pattern visualization
National Category
Transport Systems and Logistics
Identifiers
urn:nbn:se:kth:diva-217997 (URN)10.1080/13658816.2017.1393542 (DOI)000432634200002 ()2-s2.0-85032699315 (Scopus ID)
Note

QC 20171121

Available from: 2017-11-20 Created: 2017-11-20 Last updated: 2024-03-15Bibliographically approved
3. Detecting regional dominant movement patterns in trajectory data with a convolutional neural network
Open this publication in new window or tab >>Detecting regional dominant movement patterns in trajectory data with a convolutional neural network
2019 (English)In: International Journal of Geographical Information Science, ISSN 1365-8816, E-ISSN 1365-8824Article in journal (Refereed) Published
Abstract [en]

Detecting movement patterns with complicated spatial or temporal characteristics is a challenge. The past decade has witnessed the success of deep learning in processing image, voice and text data. However, its application in movement pattern detection is not fully exploited. To address the research gap, this paper develops a deep learning approach to detect regional dominant movement patterns (RDMP) in trajectory data. Specifically, a novel feature descriptor called directional flow image (DFI) is firstly proposed to store the local directional movement information in trajectory data. A DFI classification model called TRNet is designed based on convolutional neural network. The model is then trained with a synthetic trajectory dataset covering 11 classes of commonly encountered movement patterns in reality. Finally, a sliding window detector is built to detect RDMP at multiple scales and a clustering-based merging method is proposed to prune the redundant detection results. Training of TRNet on the synthetic dataset achieves considerably high accuracy. Experiments on a real-world taxi trajectory dataset further demonstrate the effectiveness and efficiency of the proposed approach in discovering complex movement patterns in trajectory data.

Place, publisher, year, edition, pages
Taylor and Francis Ltd., 2019
Keywords
convolutional neural network, deep learning, Movement pattern
National Category
Computer Vision and Robotics (Autonomous Systems)
Identifiers
urn:nbn:se:kth:diva-268454 (URN)10.1080/13658816.2019.1700510 (DOI)000502416100001 ()2-s2.0-85076374636 (Scopus ID)
Note

QC 20200409

Available from: 2020-04-09 Created: 2020-04-09 Last updated: 2024-03-18Bibliographically approved
4. Matching Sparse GPS Data to Large Scale Road Network Accelerated by AStar Search
Open this publication in new window or tab >>Matching Sparse GPS Data to Large Scale Road Network Accelerated by AStar Search
(English)Manuscript (preprint) (Other academic)
Abstract [en]

Map matching (MM) infers the path on a road network from a noisy GPS trajectory. It is an important preprocessing procedure in many knowledge discovery tasks concerning GPS data. The bottleneck of MM has been widely recognized as the large number of repeated routing queries. Previous MM methods accelerated by precomputation can effectively address this issue but it can consume extremely high memory when the GPS dataset covers a large scale road network containing millions of edges. This paper studies the problem of matching sparse GPS data to a large scale road network. In addition to the repeated routing queries, another bottleneck of MM is identified as sequential search constraint where candidates of the current GPS observation must be evaluated before examining candidates of the next. With the objective to addressing those two types of bottleneck, this paper proposes an AStar Search based MM (ASMM) algorithm that is applicable for matching sparse GPS data to large scale road network. ASMM transforms MM into a candidate waynode routing problem and introduces level-associated distance label to avoid performing repeated routing queries. Moreover, the sequential search constraint is addressed by employing AStar search strategy. Comprehensive experiments on synthetic GPS dataset demonstrate the superiority of ASMM over three state-of-the-art algorithms. When matching sparse GPS data to a large scale network, the speed of ASMM is about 5 to 20 times of its competitors. When matching to a small scale network, ASMM is still competitive in achieving a similar speed as the fastest algorithm but consumes only 10% of memory. 

Keywords
Map matching A-star search
National Category
Computer and Information Sciences
Research subject
Geodesy and Geoinformatics, Geoinformatics
Identifiers
urn:nbn:se:kth:diva-286315 (URN)
Note

QC 20210122

Available from: 2020-11-24 Created: 2020-11-24 Last updated: 2022-06-25Bibliographically approved
5. Efficient Comparison of Contiguous Sequential Patterns in GPS Trajectory Data by Bidirectional Pruning
Open this publication in new window or tab >>Efficient Comparison of Contiguous Sequential Patterns in GPS Trajectory Data by Bidirectional Pruning
(English)Manuscript (preprint) (Other academic)
Abstract [en]

Contiguous sequential pattern (CSP) represents a contiguous subsequence that frequently appearing in a sequence database. When applies CSP mining to GPS trajectory data collected from vehicles, the discovered CSP reveals a frequent route in a road network. Retrieving the distribution of frequent routes over time or among different groups of users can be formulated as a CSP comparison problem, which has important application in intelligent transportation system. However, it confronts several challenges including compressed CSP information, large search space and redundancy in the output. To address those challenges, this paper proposes a Bidirectional pruning based CSP Comparison (BCSPC) algorithm by employing three tree structures to efficiently search and compare multiple sets of CSP. Comprehensive experiments are performed on a big public real-world GPS trajectory dataset where BCSPC is compared with two other algorithms CSP-FP-tree and BIDE. The results show that when CSP is mined with a small support, BCSPC considerably outperforms two other algorithms with speed improved by 2 to 10 times and memory significantly reduced. The visualization of comparison results demonstrates the effectiveness of BCSPC in answering sophisticated queries regarding the temporal distribution of frequent routes embedded in GPS trajectory data. 

Keywords
Contiguous sequential pattern, Sequential pattern comparison
National Category
Computer Sciences
Research subject
Computer Science
Identifiers
urn:nbn:se:kth:diva-286316 (URN)
Note

QC 20210122

Available from: 2020-11-24 Created: 2020-11-24 Last updated: 2022-06-25Bibliographically approved

Open Access in DiVA

fulltext(3785 kB)316 downloads
File information
File name FULLTEXT02.pdfFile size 3785 kBChecksum SHA-512
dcdc23f905b6918b1e32786648460abc76a600ceccb4086a8b7b2de1007387de1ee640d42240698078778f667a9602509a5b6f67d1e19d91eeccba789c330e34
Type fulltextMimetype application/pdf

Search in DiVA

By author/editor
Yang, Can
By organisation
Geoinformatics
Transport Systems and LogisticsGeosciences, Multidisciplinary

Search outside of DiVA

GoogleGoogle Scholar
Total: 316 downloads
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

isbn
urn-nbn

Altmetric score

isbn
urn-nbn
Total: 1230 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf