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
Discovering Contiguous Sequential Patterns in Network-Constrained Movement
KTH, School of Architecture and the Built Environment (ABE), Urban Planning and Environment, Geoinformatics.ORCID iD: 0000-0001-5361-6034
2017 (English)Licentiate thesis, comprehensive summary (Other academic)
Abstract [en]

A large proportion of movement in urban area is constrained to a road network such as pedestrian, bicycle and vehicle. That movement information is commonly collected by Global Positioning System (GPS) sensor, which has generated large collections of trajectories. A contiguous sequential pattern (CSP) in these trajectories represents a certain number of objects traversing a sequence of spatially contiguous edges in the network, which is an intuitive way to study regularities in network-constrained movement. CSPs are closely related to route choices and traffic flows and can be useful in travel demand modeling and transportation planning. However, the efficient and scalable extraction of CSPs and effective visualization of the heavily overlapping CSPs are remaining challenges.

To address these challenges, the thesis develops two algorithms and a visual analytics system. Firstly, a fast map matching (FMM) algorithm is designed for matching a noisy trajectory to a sequence of edges traversed by the object with a high performance. Secondly, an algorithm called bidirectional pruning based closed contiguous sequential pattern mining (BP-CCSM) is developed to extract sequential patterns with closeness and contiguity constraint from the map matched trajectories. Finally, a visual analytics system called sequential pattern explorer for trajectories (SPET) is designed for interactive mining and visualization of CSPs in a large collection of trajectories.

Extensive experiments are performed on a real-world taxi trip GPS dataset to evaluate the algorithms and visual analytics system. The results demonstrate that FMM achieves a superior performance by replacing repeated routing queries with hash table lookups. BP-CCSM considerably outperforms three state-of-the-art algorithms in terms of running time and memory consumption. SPET enables the user to efficiently and conveniently explore spatial and temporal variations of CSPs in network-constrained movement.

Place, publisher, year, edition, pages
Stockholm: KTH Royal Institute of Technology, 2017. , p. 63
Series
TRITA-SOM, ISSN 1653-6126 ; 2017-13
Keyword [en]
map matching, trajectory pattern mining, closed contiguous sequential pattern mining, trajectory pattern visualization
National Category
Other Computer and Information Science
Research subject
Geodesy and Geoinformatics
Identifiers
URN: urn:nbn:se:kth:diva-217998ISBN: 978-91-7729-589-1 (print)OAI: oai:DiVA.org:kth-217998DiVA, id: diva2:1158938
Presentation
2017-12-13, Sal L51, Drottning Kristinas Väg 30, KTH, Stockholm, 14:00 (English)
Opponent
Supervisors
Note

QC 20171122

Available from: 2017-11-22 Created: 2017-11-21 Last updated: 2018-01-13Bibliographically 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
Keyword
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: 2018-02-02Bibliographically 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
2017 (English)In: International Journal of Geographical Information Science, ISSN 1365-8816, E-ISSN 1365-8824, p. 1-23Article 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, 2017
Keyword
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)
Note

QC 20171121

Available from: 2017-11-20 Created: 2017-11-20 Last updated: 2017-11-22Bibliographically approved

Open Access in DiVA

fulltext(6586 kB)28 downloads
File information
File name FULLTEXT01.pdfFile size 6586 kBChecksum SHA-512
ee1ddfad8a1e607e4d5674140740a34439cef9f9facf7e03a4734d44ede42e31f18ad2c3f5d5cd8ae2a01266ed132587a7e54a495217db394937dff6f928d822
Type fulltextMimetype application/pdf

Search in DiVA

By author/editor
Yang, Can
By organisation
Geoinformatics
Other Computer and Information Science

Search outside of DiVA

GoogleGoogle Scholar
Total: 28 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: 244 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