TY - GEN
T1 - SPTI
T2 - 2013 IEEE International Congress on Big Data, BigData 2013
AU - Zhang, Yifei
AU - Wang, Guoren
PY - 2013
Y1 - 2013
N2 - 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.
AB - 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.
KW - community
KW - distance query
KW - shortest path
KW - trunk
UR - http://www.scopus.com/inward/record.url?scp=84886033849&partnerID=8YFLogxK
U2 - 10.1109/BigData.Congress.2013.34
DO - 10.1109/BigData.Congress.2013.34
M3 - Conference contribution
AN - SCOPUS:84886033849
SN - 9780768550060
T3 - Proceedings - 2013 IEEE International Congress on Big Data, BigData 2013
SP - 195
EP - 202
BT - Proceedings - 2013 IEEE International Congress on Big Data, BigData 2013
Y2 - 27 June 2013 through 2 July 2013
ER -