Keyword Search on Temporal Graphs

Archiving graph data over history is demanded in many applications, such as social network studies, collaborative projects, scientific graph databases, and bibliographies. Typically people are interested in querying temporal graphs. Existing keyword search approaches for graph-structured data are insufficient for querying temporal graphs. This paper initiates the study of supporting keyword-based queries on temporal graphs. We propose a search syntax that is a moderate extension of keyword search, which allows casual users to easily search temporal graphs with optional predicates and ranking functions related to timestamps. To generate results efficiently, we first propose a best path iterator, which finds the paths between two data nodes in each snapshot that is the 'best' with respect to three ranking factors. It prunes invalid or inferior paths and maximizes shared processing among different snapshots. Then, we develop algorithms that efficiently generate top-$k$ query results. Extensive experiments verified the efficiency and effectiveness of our approach.