Bounded Pattern Matching Using Views
Paper
Paper/Presentation Title | Bounded Pattern Matching Using Views |
---|---|
Presentation Type | Paper |
Authors | Wang, Xin (Author), Wang, Yang (Author), Zhang, Ji (Author) and Zhu, Yan (Author) |
Editors | Hartmann, Sven, Kung, Josef, Kotsis, Gabriele, Tjoa, A Min and Khalil, Ismail |
Journal or Proceedings Title | Proceedings of 31st International Conference on Database and Expert Systems Applications (DEXA 2020) |
ERA Conference ID | 43308 |
Number of Pages | 19 |
Year | 2020 |
Place of Publication | Cham, Switzerland |
ISBN | 9783030590024 |
9783030590031 | |
Digital Object Identifier (DOI) | https://doi.org/10.1007/978-3-030-59003-1_19 |
Web Address (URL) of Paper | https://link.springer.com/chapter/10.1007%2F978-3-030-59003-1_19 |
Conference/Event | 31st International Conference on Database and Expert Systems Applications (DEXA 2020) |
International Conference on Database and Expert Systems Applications | |
Event Details | International Conference on Database and Expert Systems Applications DEXA Rank B B B B B B B |
Event Details | 31st International Conference on Database and Expert Systems Applications (DEXA 2020) Event Date 14 to end of 17 Sep 2020 Event Location Bratislava, Slovakia |
Abstract | Bounded evaluation using views is to compute the answers Q(D) to a query Q in a dataset D by accessing only cached views and a small fraction DQ of D such that the size |DQ| of DQ and the time to identify DQ are independent of |D|, no matter how big D is. Though proven effective for relational data, it has yet been investigated for graph data. In light of this, we study the problem of bounded pattern matching using views. We first introduce access schema C for graphs and propose a notion of joint containment to characterize bounded pattern matching using views. We show that a pattern query Q can be boundedly evaluated using views V(G) and a fraction GQ of G if and only if the query Q is jointly contained by V and C. Based on the characterization, we develop an efficient algorithm as well as an optimization strategy to compute matches by using V(G) and GQ. Using real-life and synthetic data, we experimentally verify the performance of these algorithms, and show that (a) our algorithm for joint containment determination is not only effective but also efficient; and (b) our matching algorithm significantly outperforms its counterpart, and the optimization technique can further improve performance by eliminating unnecessary input. |
Keywords | Graph data; Improve performance; Matching algorithm; Optimization strategy; Optimization techniques; Pattern query; Relational data; Synthetic data |
ANZSRC Field of Research 2020 | 460503. Data models, storage and indexing |
460505. Database systems | |
Byline Affiliations | Southwest Petroleum University, China |
University of Southern Queensland | |
Southwest Jiaotong University, China | |
Institution of Origin | University of Southern Queensland |
https://research.usq.edu.au/item/q63x3/bounded-pattern-matching-using-views
165
total views11
total downloads6
views this month0
downloads this month