SPTI: Efficient answering the shortest path query on large graphs

Yifei Zhang, Guoren Wang

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

2 Citations (Scopus)

Abstract

The shortest path distance computing between any two vertices in large scale graphs is an essential problem, e.g., social network analysis, route planning in road map, and has been studied over the past few decades. To answer the query efficiently, the index is widely used. However, when it comes to large scale graphs composed of millions of vertices and edges, they suffer from drawbacks of scalability. To solve these problems, we put forward SPTI, an indexing and query processing framework for the shortest path distance computing. We only select a small part of vertices from the original graph to construct index, instead of all of them. It not only can reduce the construction time and index size dramatically, but also can help speed up the-state-of-the-art approaches significantly. Our experimental results demonstrate that the SPTI can perform on graphs with millions of vertices/edges and offers apparent performance improvement over existing approaches in term of index construction time, index size and query time.

Original languageEnglish
Title of host publicationProceedings - 2013 IEEE International Congress on Big Data, BigData 2013
Pages195-202
Number of pages8
DOIs
Publication statusPublished - 2013
Externally publishedYes
Event2013 IEEE International Congress on Big Data, BigData 2013 - Santa Clara, CA, United States
Duration: 27 Jun 20132 Jul 2013

Publication series

NameProceedings - 2013 IEEE International Congress on Big Data, BigData 2013

Conference

Conference2013 IEEE International Congress on Big Data, BigData 2013
Country/TerritoryUnited States
CitySanta Clara, CA
Period27/06/132/07/13

Keywords

  • community
  • distance query
  • shortest path
  • trunk

Fingerprint

Dive into the research topics of 'SPTI: Efficient answering the shortest path query on large graphs'. Together they form a unique fingerprint.

Cite this