Institute for Web Science and Technologies · Universität Koblenz - Landau
Institute WeST

Implementation and Performance of STAR Algorithm

[go to overview]
Wei Wang

We introduce our implementation of the STAR algorithm and recent experiment results of its performance. The STAR algorithm is used for relationship query over large relationship graphs, which can be considered from algorithmic point of view as a Steiner Tree problem. The algorithm runs in two phases. In the first phase, it tries to quickly build a first tree that interconnects all nodes from a graph. In the second phase it aims to iteratively improve the current tree by scanning and pruning its neighborhood.

Our implementation introduces interesting techniques: 1. Create an underlying container data structure for all vertices and edges instances to save memory space. 2. For the first phase of the algorithm, we artificially add necessary edges to connect the required vertices, so that the first initial steiner tree can be build as soon as possible. We also present recent results of the performance experiment of the algorithm.

28.08.14 - 08:15
B 016