The Library
GraphCache : a caching system for graph queries
Tools
Wang, J., Ntarmos, N. and Triantafillou, Peter (2017) GraphCache : a caching system for graph queries. In: 20th International Conference on Extending Database Technology, Venice, 21-24 Mar 2017. Published in: 20th International Conference on Extending Database Technology pp. 13-24. ISBN 9783893180738 .
An open access version can be found in:
Official URL: http://doi.org/10.5441/002/edbt.2017.03
Abstract
Graph datasets and NoSQL graph databases are becoming
increasingly popular for a large variety of applications, de-
pendent on modelling entities and their relationships and
interactions. In such systems, graph queries are essential for
graph analytics. However, they can be very time-consuming,
as graph query processing entails the subgraph isomorphism
problem, which is NP-Complete. In general, caching sys-
tems constitute a key component in software systems, in-
cluding database systems, where they play a key role in ex-
pediting query processing. In this context, we put forth
GraphCache, the �rst caching system for graph query pro-
cessing. We report on the design issues and goals that
GraphCache must meet, its overall system architecture and
implementation, coupled with novel cache replacement and
admission control policies. We also report on results from
extensive performance evaluations which showcase and quan-
tify its bene�ts and overheads, highlighting lessons learned.
GraphCache can be used as a front end, complementing
any graph query processing method, which is viewed as a
pluggable component. The design and implementation of
GraphCache started in mid 2014 and in its current imple-
mentation it can signi�cantly improve the performance of
methods from di�erent categories of graph-query processing
research { including �lter-then-verify (FTV) methods and
direct subgraph-isomorphism (SI) algorithms, and across
workloads and datasets of di�erent characteristics. Cur-
rently, GraphCache comprises more than 6,000 lines of Java
code, excluding the pluggable FTV/SI query-processing al-
gorithms. It is available bundled with 3 top-performing FTV
methods and 3 top-performing SI algorithms.
Item Type: | Conference Item (Paper) | ||||
---|---|---|---|---|---|
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||
Journal or Publication Title: | 20th International Conference on Extending Database Technology | ||||
Publisher: | EDBT | ||||
ISBN: | 9783893180738 | ||||
Official Date: | 21 March 2017 | ||||
Dates: |
|
||||
Page Range: | pp. 13-24 | ||||
Status: | Peer Reviewed | ||||
Publication Status: | Published | ||||
Access rights to Published version: | Open Access (Creative Commons) | ||||
Conference Paper Type: | Paper | ||||
Title of Event: | 20th International Conference on Extending Database Technology | ||||
Type of Event: | Conference | ||||
Location of Event: | Venice | ||||
Date(s) of Event: | 21-24 Mar 2017 | ||||
Related URLs: | |||||
Open Access Version: |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |