Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

Efficient Method for Mapping a Large Set of GPS Traces to Road Segments

IP.com Disclosure Number: IPCOM000243491D
Publication Date: 2015-Sep-24
Document File: 3 page(s) / 106K

Publishing Venue

The IP.com Prior Art Database

Abstract

Disclosed is an efficient method of computing the Hidden Markov Model (HMM)-based map-matching algorithm by Osogami and Raymond*. The novel method drastically reduces the computation time for the most time consuming part of the HMM-based map matching.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 53% of the total text.

Page 01 of 3

Efficient Method for Mapping a Large Set of GPS Traces to Road Segments

Increasingly, Global Positioning System (GPS) sensors are embedded and connected to the Internet. As a result, lot of GPS trace data has been accumulated in the age of Internet of Things (IoT). Analyzing the accumulated GPS trace data is an important application of business analytics. For example, analyzing the GPS traces running on the traffic conditions of each road segment can be useful for developing methods to reduce traffic congestion or recommending active retail areas .

Map matching is a task in which GPS traces are input and allow the identification of the corresponding road segments in a road network. In Figure 1, the left side shows an example of a GPS trace and the right side shows a sequence of corresponding road segments. Because GPS data is noisy, it is difficult to find the correct corresponding road segments. Moreover, it takes a lot of time to analyze a large amount of GPS traces.

Figure 1: Example of GPS trace and corresponding road segments

The novel contribution is an efficient method of computing the Hidden Markov Model (HMM)-based map-matching algorithm by Osogami and Raymond*. The novel method drastically reduces the computation time for the most time consuming part of the HMM-based map matching. The core components of the approach are to :

• Execute a one-to-many shortest path query in the reversed graph • Cut off the shortest path query based on log likelihood of candidate paths
• Cut off the shortest path query based on the number of connections between

  hidden states realized so far
• Reuse the data structure of the shortest path query by storing the data in a Least Recently Used (LRU) cache

Figure 2 depicts the outline of the entire system of map matching . It splits the given GPS traces into multiple sets of GPS traces and then applies the map matching to each set independently in parallel. The...