Scalable prediction by partial match (PPM) and its application to route prediction View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

2018-12

AUTHORS

Vishnu Shankar Tiwari, Arti Arya, Sudha Chaturvedi

ABSTRACT

Route prediction plays a vital role in many important location-based applications such as resource prediction in grid computing, traffic congestion estimation, vehicular ad hoc networks, and travel recommendation. The goal of this work is to design a scalable route prediction application based on prediction by partial match (PPM) modeling of user travel data. PPM is one of the widely used techniques for text compression as well as string sequence indexing and for prediction. PPM tree construction from the huge volume of data by sequential processing is time consuming in practical implementation. Existing techniques are designed for single machine and their implementation on the distributed environment is still a challenge. This work focuses on achieving a horizontal scalability of PPM and addresses various challenges in distributed construction, such as reducing I/O and parallel computation of sequences, and comes up with a final PPM tree in distributed environment without sacrificing accuracy. A huge corpus of GPS data set is map matched to the road network extracted from the OpenStreetMap and the PPM tree is built on the edges of the road network. A two-step construction of the PPM tree is proposed, which is extended to execute over the MapReduce framework. The MapReduce framework running over the Hadoop distributed file system is used for distributed processing. A horizontally scalable PPM model is built and evaluated for route prediction from a huge corpus of historical GPS traces. Data sets used are GPS traces and road networks. Both of these used in this work are taken from an openly available corpus. Distributed construction of PPM was proposed and evaluated on Hadoop cluster using MapReduce and the detailed results are presented. More... »

PAGES

4

Identifiers

URI

http://scigraph.springernature.com/pub.10.1186/s40535-018-0051-z

DOI

http://dx.doi.org/10.1186/s40535-018-0051-z

DIMENSIONS

https://app.dimensions.ai/details/publication/pub.1106407195


Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
Incoming Citations Browse incoming citations for this publication using opencitations.net

JSON-LD is the canonical representation for SciGraph data.

TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

[
  {
    "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
    "about": [
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0806", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Information Systems", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/08", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Information and Computing Sciences", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Visvesvaraya Technological University", 
          "id": "https://www.grid.ac/institutes/grid.444321.4", 
          "name": [
            "Visvesvaraya Technological University, Bangalore, Karnataka, India"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Tiwari", 
        "givenName": "Vishnu Shankar", 
        "id": "sg:person.014730261445.58", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014730261445.58"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Visvesvaraya Technological University", 
          "id": "https://www.grid.ac/institutes/grid.444321.4", 
          "name": [
            "Visvesvaraya Technological University, Bangalore, Karnataka, India"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Arya", 
        "givenName": "Arti", 
        "id": "sg:person.016323222445.47", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016323222445.47"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Visvesvaraya Technological University", 
          "id": "https://www.grid.ac/institutes/grid.444321.4", 
          "name": [
            "Visvesvaraya Technological University, Bangalore, Karnataka, India"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Chaturvedi", 
        "givenName": "Sudha", 
        "id": "sg:person.010415531645.24", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010415531645.24"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "https://doi.org/10.1080/15472450600793560", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1004178650"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/1365815.1365816", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1005702119"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/1409635.1409677", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1039968496"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1063/1.166191", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1041420640"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/1526709.1526816", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1043251722"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/j.scico.2007.07.001", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1051864156"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/26.61469", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1061137722"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/tcom.1984.1096090", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1061553897"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/iadcc.2013.6514292", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1093384458"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/dcc.1995.515495", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1093432767"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/dcc.2000.838160", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1093957065"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/icit.2014.70", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1095451067"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.4271/2008-01-0201", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1096546100"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1613/jair.1491", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1105579319"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2018-12", 
    "datePublishedReg": "2018-12-01", 
    "description": "Route prediction plays a vital role in many important location-based applications such as resource prediction in grid computing, traffic congestion estimation, vehicular ad hoc networks, and travel recommendation. The goal of this work is to design a scalable route prediction application based on prediction by partial match (PPM) modeling of user travel data. PPM is one of the widely used techniques for text compression as well as string sequence indexing and for prediction. PPM tree construction from the huge volume of data by sequential processing is time consuming in practical implementation. Existing techniques are designed for single machine and their implementation on the distributed environment is still a challenge. This work focuses on achieving a horizontal scalability of PPM and addresses various challenges in distributed construction, such as reducing I/O and parallel computation of sequences, and comes up with a final PPM tree in distributed environment without sacrificing accuracy. A huge corpus of GPS data set is map matched to the road network extracted from the OpenStreetMap and the PPM tree is built on the edges of the road network. A two-step construction of the PPM tree is proposed, which is extended to execute over the MapReduce framework. The MapReduce framework running over the Hadoop distributed file system is used for distributed processing. A horizontally scalable PPM model is built and evaluated for route prediction from a huge corpus of historical GPS traces. Data sets used are GPS traces and road networks. Both of these used in this work are taken from an openly available corpus. Distributed construction of PPM was proposed and evaluated on Hadoop cluster using MapReduce and the detailed results are presented.", 
    "genre": "research_article", 
    "id": "sg:pub.10.1186/s40535-018-0051-z", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": false, 
    "isPartOf": [
      {
        "id": "sg:journal.1053269", 
        "issn": [
          "2196-0089"
        ], 
        "name": "Applied Informatics", 
        "type": "Periodical"
      }, 
      {
        "issueNumber": "1", 
        "type": "PublicationIssue"
      }, 
      {
        "type": "PublicationVolume", 
        "volumeNumber": "5"
      }
    ], 
    "name": "Scalable prediction by partial match (PPM) and its application to route prediction", 
    "pagination": "4", 
    "productId": [
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "0db91ad273240c8a99d5204c09d7bd25bb43262f7a077680183393612fefadb5"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1186/s40535-018-0051-z"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1106407195"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1186/s40535-018-0051-z", 
      "https://app.dimensions.ai/details/publication/pub.1106407195"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2019-04-10T21:30", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-uberresearch-data-dimensions-target-20181106-alternative/cleanup/v134/2549eaecd7973599484d7c17b260dba0a4ecb94b/merge/v9/a6c9fde33151104705d4d7ff012ea9563521a3ce/jats-lookup/v90/0000000001_0000000264/records_8687_00000485.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "http://link.springer.com/10.1186/s40535-018-0051-z"
  }
]
 

Download the RDF metadata as:  json-ld nt turtle xml License info

HOW TO GET THIS DATA PROGRAMMATICALLY:

JSON-LD is a popular format for linked data which is fully compatible with JSON.

curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1186/s40535-018-0051-z'

N-Triples is a line-based linked data format ideal for batch operations.

curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1186/s40535-018-0051-z'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1186/s40535-018-0051-z'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1186/s40535-018-0051-z'


 

This table displays all metadata directly associated to this object as RDF triples.

116 TRIPLES      21 PREDICATES      41 URIs      19 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1186/s40535-018-0051-z schema:about anzsrc-for:08
2 anzsrc-for:0806
3 schema:author Na49f51958b18455898a383faca0a9154
4 schema:citation https://doi.org/10.1016/j.scico.2007.07.001
5 https://doi.org/10.1063/1.166191
6 https://doi.org/10.1080/15472450600793560
7 https://doi.org/10.1109/26.61469
8 https://doi.org/10.1109/dcc.1995.515495
9 https://doi.org/10.1109/dcc.2000.838160
10 https://doi.org/10.1109/iadcc.2013.6514292
11 https://doi.org/10.1109/icit.2014.70
12 https://doi.org/10.1109/tcom.1984.1096090
13 https://doi.org/10.1145/1365815.1365816
14 https://doi.org/10.1145/1409635.1409677
15 https://doi.org/10.1145/1526709.1526816
16 https://doi.org/10.1613/jair.1491
17 https://doi.org/10.4271/2008-01-0201
18 schema:datePublished 2018-12
19 schema:datePublishedReg 2018-12-01
20 schema:description Route prediction plays a vital role in many important location-based applications such as resource prediction in grid computing, traffic congestion estimation, vehicular ad hoc networks, and travel recommendation. The goal of this work is to design a scalable route prediction application based on prediction by partial match (PPM) modeling of user travel data. PPM is one of the widely used techniques for text compression as well as string sequence indexing and for prediction. PPM tree construction from the huge volume of data by sequential processing is time consuming in practical implementation. Existing techniques are designed for single machine and their implementation on the distributed environment is still a challenge. This work focuses on achieving a horizontal scalability of PPM and addresses various challenges in distributed construction, such as reducing I/O and parallel computation of sequences, and comes up with a final PPM tree in distributed environment without sacrificing accuracy. A huge corpus of GPS data set is map matched to the road network extracted from the OpenStreetMap and the PPM tree is built on the edges of the road network. A two-step construction of the PPM tree is proposed, which is extended to execute over the MapReduce framework. The MapReduce framework running over the Hadoop distributed file system is used for distributed processing. A horizontally scalable PPM model is built and evaluated for route prediction from a huge corpus of historical GPS traces. Data sets used are GPS traces and road networks. Both of these used in this work are taken from an openly available corpus. Distributed construction of PPM was proposed and evaluated on Hadoop cluster using MapReduce and the detailed results are presented.
21 schema:genre research_article
22 schema:inLanguage en
23 schema:isAccessibleForFree false
24 schema:isPartOf Nae88744b6bde4d60b6026f3401211454
25 Nde31e0036af64f0c99a1c4ad4ce9981c
26 sg:journal.1053269
27 schema:name Scalable prediction by partial match (PPM) and its application to route prediction
28 schema:pagination 4
29 schema:productId N77662f4a692046faa40e154b3fb9c720
30 Nbc4bd632f98b4936aad6d731002f39d5
31 Necbec370c0b84dfd858f1e1e8b19d2bd
32 schema:sameAs https://app.dimensions.ai/details/publication/pub.1106407195
33 https://doi.org/10.1186/s40535-018-0051-z
34 schema:sdDatePublished 2019-04-10T21:30
35 schema:sdLicense https://scigraph.springernature.com/explorer/license/
36 schema:sdPublisher N29895ab70193467fa1be9dd2356e0b71
37 schema:url http://link.springer.com/10.1186/s40535-018-0051-z
38 sgo:license sg:explorer/license/
39 sgo:sdDataset articles
40 rdf:type schema:ScholarlyArticle
41 N29895ab70193467fa1be9dd2356e0b71 schema:name Springer Nature - SN SciGraph project
42 rdf:type schema:Organization
43 N77662f4a692046faa40e154b3fb9c720 schema:name readcube_id
44 schema:value 0db91ad273240c8a99d5204c09d7bd25bb43262f7a077680183393612fefadb5
45 rdf:type schema:PropertyValue
46 N85a875c11d0b4e8ea2e98bd7391e8c5e rdf:first sg:person.010415531645.24
47 rdf:rest rdf:nil
48 Na49f51958b18455898a383faca0a9154 rdf:first sg:person.014730261445.58
49 rdf:rest Nd196588ca38441e388e4c811dbcb706b
50 Nae88744b6bde4d60b6026f3401211454 schema:volumeNumber 5
51 rdf:type schema:PublicationVolume
52 Nbc4bd632f98b4936aad6d731002f39d5 schema:name doi
53 schema:value 10.1186/s40535-018-0051-z
54 rdf:type schema:PropertyValue
55 Nd196588ca38441e388e4c811dbcb706b rdf:first sg:person.016323222445.47
56 rdf:rest N85a875c11d0b4e8ea2e98bd7391e8c5e
57 Nde31e0036af64f0c99a1c4ad4ce9981c schema:issueNumber 1
58 rdf:type schema:PublicationIssue
59 Necbec370c0b84dfd858f1e1e8b19d2bd schema:name dimensions_id
60 schema:value pub.1106407195
61 rdf:type schema:PropertyValue
62 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
63 schema:name Information and Computing Sciences
64 rdf:type schema:DefinedTerm
65 anzsrc-for:0806 schema:inDefinedTermSet anzsrc-for:
66 schema:name Information Systems
67 rdf:type schema:DefinedTerm
68 sg:journal.1053269 schema:issn 2196-0089
69 schema:name Applied Informatics
70 rdf:type schema:Periodical
71 sg:person.010415531645.24 schema:affiliation https://www.grid.ac/institutes/grid.444321.4
72 schema:familyName Chaturvedi
73 schema:givenName Sudha
74 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010415531645.24
75 rdf:type schema:Person
76 sg:person.014730261445.58 schema:affiliation https://www.grid.ac/institutes/grid.444321.4
77 schema:familyName Tiwari
78 schema:givenName Vishnu Shankar
79 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014730261445.58
80 rdf:type schema:Person
81 sg:person.016323222445.47 schema:affiliation https://www.grid.ac/institutes/grid.444321.4
82 schema:familyName Arya
83 schema:givenName Arti
84 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016323222445.47
85 rdf:type schema:Person
86 https://doi.org/10.1016/j.scico.2007.07.001 schema:sameAs https://app.dimensions.ai/details/publication/pub.1051864156
87 rdf:type schema:CreativeWork
88 https://doi.org/10.1063/1.166191 schema:sameAs https://app.dimensions.ai/details/publication/pub.1041420640
89 rdf:type schema:CreativeWork
90 https://doi.org/10.1080/15472450600793560 schema:sameAs https://app.dimensions.ai/details/publication/pub.1004178650
91 rdf:type schema:CreativeWork
92 https://doi.org/10.1109/26.61469 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061137722
93 rdf:type schema:CreativeWork
94 https://doi.org/10.1109/dcc.1995.515495 schema:sameAs https://app.dimensions.ai/details/publication/pub.1093432767
95 rdf:type schema:CreativeWork
96 https://doi.org/10.1109/dcc.2000.838160 schema:sameAs https://app.dimensions.ai/details/publication/pub.1093957065
97 rdf:type schema:CreativeWork
98 https://doi.org/10.1109/iadcc.2013.6514292 schema:sameAs https://app.dimensions.ai/details/publication/pub.1093384458
99 rdf:type schema:CreativeWork
100 https://doi.org/10.1109/icit.2014.70 schema:sameAs https://app.dimensions.ai/details/publication/pub.1095451067
101 rdf:type schema:CreativeWork
102 https://doi.org/10.1109/tcom.1984.1096090 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061553897
103 rdf:type schema:CreativeWork
104 https://doi.org/10.1145/1365815.1365816 schema:sameAs https://app.dimensions.ai/details/publication/pub.1005702119
105 rdf:type schema:CreativeWork
106 https://doi.org/10.1145/1409635.1409677 schema:sameAs https://app.dimensions.ai/details/publication/pub.1039968496
107 rdf:type schema:CreativeWork
108 https://doi.org/10.1145/1526709.1526816 schema:sameAs https://app.dimensions.ai/details/publication/pub.1043251722
109 rdf:type schema:CreativeWork
110 https://doi.org/10.1613/jair.1491 schema:sameAs https://app.dimensions.ai/details/publication/pub.1105579319
111 rdf:type schema:CreativeWork
112 https://doi.org/10.4271/2008-01-0201 schema:sameAs https://app.dimensions.ai/details/publication/pub.1096546100
113 rdf:type schema:CreativeWork
114 https://www.grid.ac/institutes/grid.444321.4 schema:alternateName Visvesvaraya Technological University
115 schema:name Visvesvaraya Technological University, Bangalore, Karnataka, India
116 rdf:type schema:Organization
 




Preview window. Press ESC to close (or click here)


...