Endre søk
RefereraExporteraLink to record
Permanent link

Direct link
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annet format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annet språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
Efficient Comparison of Contiguous Sequential Patterns in GPS Trajectory Data by Bidirectional Pruning
KTH, Skolan för arkitektur och samhällsbyggnad (ABE), Samhällsplanering och miljö, Geoinformatik.ORCID-id: 0000-0001-5361-6034
KTH, Skolan för arkitektur och samhällsbyggnad (ABE), Samhällsplanering och miljö, Geoinformatik.ORCID-id: 0000-0003-1164-8403
(engelsk)Manuskript (preprint) (Annet vitenskapelig)
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. 

Emneord [en]
Contiguous sequential pattern, Sequential pattern comparison
HSV kategori
Forskningsprogram
Datalogi
Identifikatorer
URN: urn:nbn:se:kth:diva-286316OAI: oai:DiVA.org:kth-286316DiVA, id: diva2:1503559
Merknad

QC 20210122

Tilgjengelig fra: 2020-11-24 Laget: 2020-11-24 Sist oppdatert: 2022-06-25bibliografisk kontrollert
Inngår i avhandling
1. Efficient Map Matching and Discovery of Frequent and Dominant Movement Patterns in GPS Trajectory Data
Åpne denne publikasjonen i ny fane eller vindu >>Efficient Map Matching and Discovery of Frequent and Dominant Movement Patterns in GPS Trajectory Data
2020 (engelsk)Doktoravhandling, med artikler (Annet vitenskapelig)
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.

sted, utgiver, år, opplag, sider
Stockholm: KTH Royal Institute of Technology, 2020. s. 62
Serie
TRITA-ABE-DLT ; 2041
Emneord
map matching, contiguous sequential pattern mining, contiguous sequential pattern comparison, movement pattern detection, Kartmatchning, sammanhängande sekventiellt mönster utvinning, sammanhängande sekventiellt mönster jämförelse, rörelsemönster detektering
HSV kategori
Forskningsprogram
Geodesi och geoinformatik, Geoinformatik
Identifikatorer
urn:nbn:se:kth:diva-286318 (URN)978-91-7873-734-5 (ISBN)
Disputas
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 (engelsk)
Opponent
Veileder
Merknad

QC 20201125

Tilgjengelig fra: 2020-11-25 Laget: 2020-11-24 Sist oppdatert: 2022-06-25bibliografisk kontrollert

Open Access i DiVA

Fulltekst mangler i DiVA

Person

Yang, CanGidofalvi, Gyözö

Søk i DiVA

Av forfatter/redaktør
Yang, CanGidofalvi, Gyözö
Av organisasjonen

Søk utenfor DiVA

GoogleGoogle Scholar

urn-nbn

Altmetric

urn-nbn
Totalt: 161 treff
RefereraExporteraLink to record
Permanent link

Direct link
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annet format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annet språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf