L4g: Two-Hop Label Management for Group Steiner Tree Search on Graphs

Finding group Steiner trees (GSTs) is widely utilized for keyword search in relational databases. Current methods often build GSTs by querying and merging shortest paths. Some recent work explores the possibility of employing shortest path indexes, i.e., 2-hop labels, to speed up GST search, but fails to achieve a constant and effective GST search acceleration. We present a new GST-customized label management scheme to address this issue. First, to speed up GST search more effectively, we propose a novel label generation algorithm, which avoids producing unused labels in GST scenarios when indexing the graph with mock vertices that represent candidate groups in possible GST search tasks. Second, to maintain labels at a higher speed in dynamic cases, we develop an original batch-friendly label maintenance framework, which contains a unique integrated label update process that is carefully designed to reduce redundant operations. We conduct experiments on various real datasets to demonstrate the usefulness of this work: (i) different from the current approach that usually fails to accelerate GST search, our techniques support a constant GST search speedup of more than 3 orders of magnitude; and (ii) in comparison with the state-of-the-art methods that could be inefficient to repair labels when users change data frequently, our techniques are usually an order of magnitude faster to maintain labels in GST cases, by often reducing more than 90% of redundant operations.