GRID-BASED ANALYSIS OF GEOSPATIAL TRAJECTORIES

• US 20150363508A1
• Filed: 06/17/2014
• Published: 12/17/2015
• Est. Priority Date: 06/17/2014
• Status: Active Grant

• Current Assignee: SAP SE
• Original Assignee: SAP SE
• Inventors: NANDAN, Naveen
• Granted Patent: US 10,387,457 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2228 Indexing structures
• CPC Class Codes: G06F 16/29 Geographical information databases

Abstract

Described herein is a framework for analyzing geospatial trajectory data. In accordance with one aspect, a grid model of a geographical area of interest is generated in response to a user event. The grid model includes a grid having a plurality of rows and columns of cells, in which the cells may be identified by unique cell numbers. Geospatial trajectory data of users may be mapped to the cells in the grid to generate mapped data with unique cell numbers associated to the geospatial trajectory data. The mapped data may further be analyzed to identify cell transitions based on the mapped data. Identifying the cell transitions includes determining cell density sequences and cell dwell-time sequences of the users. The cell density and cell dwell-time sequences may further be analyzed to perform a similarity analysis. Results of the similarity analysis may be presented to the end-user device of a user.

Claims

1. A computer-implemented method of analyzing geospatial trajectories, comprising:

in response to a user event from an end-user device, generating a grid model of a geographical area of interest by a server, wherein the grid model comprises a grid having a plurality of rows and columns of cells, wherein the cells are identified by unique cell numbers;

mapping geospatial trajectory data of users to the cells in the grid by the server, the geospatial trajectory data comprises 2-dimensional spatial-temporal data with longitude and latitude information related to trajectory of the users, wherein mapping the trajectory data generates mapped data with unique cell numbers associated to the geospatial trajectory data;

analyzing the mapped geospatial trajectory data to identify cell transitions based on the mapped data, wherein identifying the cell transitions comprises

determining cell density sequences of the users, and

determining cell dwell-time sequences of the users;

analyzing the cell density and cell dwell-time sequences to perform a similarity analysis; and

presenting results of the similarity analysis to the end-user device of a user.

2. The computer-implemented method of claim 1 wherein:

a boundary of the grid is defined by latitude 1 (lat₁), latitude 2 (lat₂), longitude 1 (lon₁) and longitude 2 (lon₂); and

mapping geospatial trajectory data comprises using

3. The computer-implemented method of claim 1 wherein:

the geospatial trajectory data of the users comprises log entries stored as a raw trajectory table in a database;

attributes of the table includes

user id,

location which includes latitude and longitude information, and

time at which data point was recorded;

each data point corresponds to a row in the table; and

each attribute correspond to a column in the table.

4. The computer-implemented method of claim 3 wherein mapping the data comprises generating cell number for each data point in the raw trajectory table.

5. The computer-implemented method of claim 1 wherein determining the cell density sequences of the users comprises, for each user, determining a cell sequence of cells visited and number of log entries for each cell in the cell sequence.

6. The computer-implemented method of claim 1 wherein determining the cell dwell-time sequences of the users comprises, for each user, determining a cell sequence of cells visited and dwell-time for each cell in the cell sequence.

7. The computer-implemented method of claim 1 wherein:

determining the cell density sequences of the users comprises, for each user, determining a cell sequence of cells visited and number of log entries for each cell in the cell sequence; and

determining the cell dwell-time sequences of the users comprises, for each user, determining a cell sequence of cells visited and dwell-time for each cell in the cell sequence.

8. The computer-implemented method of claim 7 wherein the similarity analysis comprises a longest common subsequence (LCS) analysis between trajectories of first and second users.

9. The computer-implemented method of claim 8 wherein the LCS analysis comprises:

performing the LCS on the cell density sequences of the first and second users;

performing the LCS on the cell dwell-time sequences of the first and second users; and

performing the LCS on a combination of the cell density and cell dwell-time sequences of the first and second users.

10. A data analysis system comprising:

a database module for storing geospatial trajectory data of users as a data table, wherein log entries of the geospatial trajectory data of the users correspond to rows in the data table;

a data analyzer comprising

a modeling module, the modeling module defines a grid covering an area of interest, wherein the grid includes a plurality of rows and columns of cells uniquely identified by cell numbers, the modeling module generates mapped data by mapping the log entries of the geospatial trajectory data to unique cell numbers;

a characterization module, the characterization module analyzes the mapped data to determine cell transitions of log entries of the users; and

a mining module, the mining module analyzes the cell transitions to determine similarities in the trajectories of the users.

11. The data analysis system of claim 10:

comprising

a frontend subsystem running on an end-user device, the frontend subsystem includes an interface;

a backend subsystem running on a server, wherein the backend subsystem comprises

a first stage, the first stage includes the database module, and the data analyzer,

a second stage that includes a layer to expose data of the first stage, and

a third stage that includes a visualization application; and

wherein a user interacts with the backend subsystem using the interface.

12. The data analysis system of claim 11 wherein the frontend and backend subsystems communicate using web services.

13. The data analysis system of claim 11 wherein the frontend subsystem comprises leaflet maps for visualizing results of the data analyzer.

14. The data analysis system of claim 10 wherein the characterization module determines cell density sequences and cell dwell-time sequences of the users.

15. The data analysis system of claim 10 wherein the grid comprises a boundary defined by latitude 1 (lat₁), latitude 2 (lat₂), longitude 1 (lon₁) and longitude 2 (lon₂).

16. The data analysis system of claim 15 wherein the mapped data is generated by

17. A computer-implemented method of analyzing geospatial trajectories, comprising:

in response to a user event, generating a grid model of a geographical area of interest by a server, wherein the grid model comprises a grid having a plurality of rows and columns of cells, wherein the cells are identified by unique cell numbers;

mapping geospatial trajectory data of users to the cells in the grid, wherein mapping the data generates mapped data with unique cell numbers associated to the geospatial trajectory data;

analyzing the mapped geospatial trajectory data to identify cell transitions based on the mapped data, wherein identifying the cell transitions comprises determining cell density and cell dwell-time information; and

analyzing the cell density and cell dwell-time information, wherein the analysis comprises a user similarity mining.

18. The computer-implemented method of claim 17 wherein:

a boundary of the grid is defined by latitude 1 (lat₁), latitude 2 (lat₂), longitude 1 (lon₁) and longitude 2 (lon₂); and

mapping geospatial trajectory data comprises using

19. The computer-implemented method of claim 17 wherein:

the geospatial trajectory data of the users comprises log entries stored as a raw trajectory table in a database;

attributes of the table includes

user id,

location which includes latitude and longitude information, and

time at which data point was recorded;

each data point corresponds to a row in the table; and

each attribute correspond to a column in the table.

20. The computer-implemented method of claim 17 wherein:

determining cell density information of the users comprises, for each user, determining a cell sequence of cells visited and number of log entries for each cell in the cell sequence; and

determining cell dwell-time information of the users comprises, for each user, determining a cell sequence of cells visited and dwell-time for each cell in the cell sequence.