@inproceedings{c7cffbaae7104f3db387e19992759948,
title = "Keyword search on temporal graphs",
abstract = "Archiving graph data over history is demanded in many applications, such as social network 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 an extension of keyword search, which allows casual users to easily search temporal graphs with temporal predicates and ranking functions. To generate results efficiently, we propose a best path iterator, which finds the 'best' paths between two data nodes in each snapshot regarding to three ranking factors. We develop algorithms that efficiently generate top-k query results. Extensive experiments verified the efficiency and effectiveness of our approach.",
keywords = "Algorithm, Graph theory, Information retrieval, Keyword search",
author = "Ziyang Liu and Chong Wang and Yi Chen",
note = "Funding Information: This work is partially supported by NSF CAREER Award IIS-1322406 Funding Information: Fig. 3. Efficiency wrt Different Predicates (DBLP) results on DBLP for space reasons. Since there is no existing work on keyword search on temporal graphs, we use two baselines that adapt existing work of keyword search on regular graphs, BANKS [4], to search temporal graphs. The first baseline runs BANKS on graph snapshot at distinct time instant, referred to as BANKS (I), the first approach described in Section I. The second baseline runs BANKS on the entire temporal graph, and then perform post-processing to filter out invalid results, referred to as BANKS (W), the second approach described in Section I. As shown in Figure 1, 3, and 3, our method (labeled as “Temporal”)can efficientlygenerate better search results compared to the baselines. VI. CONCLUSIONS We initiate the study of searching temporal graphs. We propose a keyword based query syntax that allows temporal information to be specified as predicates or ranking factors. We propose a best path iterator, which finds the “best” paths in each time instant wrt. ranking functions. We propose algorithms to efficiently evaluate queries on a temporal graph to generate top-k results. The efficiency and effectiveness of our method are verified through extensive empirical studies. ACKNOWLEDGMENT This work is partially supported by NSF CAREER Award IIS-1322406, a Google Research Award, and an endowment from the Leir Charitable Foundations.; 34th IEEE International Conference on Data Engineering, ICDE 2018 ; Conference date: 16-04-2018 Through 19-04-2018",
year = "2018",
month = oct,
day = "24",
doi = "10.1109/ICDE.2018.00261",
language = "English (US)",
series = "Proceedings - IEEE 34th International Conference on Data Engineering, ICDE 2018",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
pages = "1807--1808",
booktitle = "Proceedings - IEEE 34th International Conference on Data Engineering, ICDE 2018",
address = "United States",
}