Keyword Search on Temporal Graphs

Ziyang Liu, Chong Wang, Yi Chen

Research output: Contribution to journalArticlepeer-review

6 Scopus citations

Abstract

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.

Original languageEnglish (US)
Article number7891889
Pages (from-to)1667-1680
Number of pages14
JournalIEEE Transactions on Knowledge and Data Engineering
Volume29
Issue number8
DOIs
StatePublished - Aug 2017

All Science Journal Classification (ASJC) codes

  • Information Systems
  • Computer Science Applications
  • Computational Theory and Mathematics

Keywords

  • Temporal graph
  • keyword search
  • versioned graph

Fingerprint

Dive into the research topics of 'Keyword Search on Temporal Graphs'. Together they form a unique fingerprint.

Cite this