Ji Hye Hong , Yong Koo Han , Young Koo Lee

KIPS Transactions on Software and Data Engineering, Vol. 3, No. 5, pp. 179-186, May. 2014
10.3745/KTSDE.2014.3.5.179,   PDF Download:

Abstract

Current networks such as social network, web page link, traffic network are big data which have the large numbers of nodes andedges. Many applications such as social network services and navigation systems use these networks. Since big networks are not fitinto the memory, existing in-memory based analysis techniques cannot provide high performance. Frontier-Expansion-Merge (FEM)framework for graph search operations using three corresponding operators in the relational database (RDB) context. FEM exploits anindex table that stores pre-computed partial paths for efficient shortest path discovery. However, the index table of FEM has low hitratio because the indices are determined by distances of indices rather than the possibility of containing a shortest path. In this paper,we propose an method that construct index table using high degree nodes having high hit ratio for efficient shortest path discovery.We experimentally verify that our index technique can support shortest path discovery efficiently in real-world datasets.

Statistics
Cite this article