Efficiently Estimating Joining Cost of Subqueries in Regular Path Queries
Evaluating Regular Path Queries (RPQs) have been of interest since they were used as a powerful way to explore paths and patterns in graph databases. Traditional automata-based approaches are restricted in the graph size and/or highly complex queries, which causes a high evaluation cost (e.g., memor...
| Main Authors: | , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2021-04-01
|
| Series: | Electronics |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2079-9292/10/9/990 |
| _version_ | 1797536915514195968 |
|---|---|
| author | Van-Quyet Nguyen Van-Hau Nguyen Minh-Quy Nguyen Quyet-Thang Huynh Kyungbaek Kim |
| author_facet | Van-Quyet Nguyen Van-Hau Nguyen Minh-Quy Nguyen Quyet-Thang Huynh Kyungbaek Kim |
| author_sort | Van-Quyet Nguyen |
| collection | DOAJ |
| description | Evaluating Regular Path Queries (RPQs) have been of interest since they were used as a powerful way to explore paths and patterns in graph databases. Traditional automata-based approaches are restricted in the graph size and/or highly complex queries, which causes a high evaluation cost (e.g., memory space and response time) on large graphs. Recently, although using the approach based on the threshold rare label for large graphs has been achieving some success, they could not often guarantee the minimum searching cost. Alternatively, the Unit-Subquery Cost Matrix (USCM) has been studied and obtained the viability of the usage of subqueries. Nevertheless, this method has an issue, which is, it does not cumulate the cost among subqueries that causes the long response time on a large graph. In order to overcome this issue, this paper proposes a method for estimating joining cost of subqueries to accelerate the USCM based parallel evaluation of RPQs on a large graph, namely USCM-Join. Through real-world datasets, we experimentally show that the USCM-Join outperforms others and estimating the joining cost enhances the USCM based approach up to around 20% in terms of response time. |
| first_indexed | 2024-03-10T12:07:39Z |
| format | Article |
| id | doaj.art-76c8d580c5a44919835b95d2b719251e |
| institution | Directory Open Access Journal |
| issn | 2079-9292 |
| language | English |
| last_indexed | 2024-03-10T12:07:39Z |
| publishDate | 2021-04-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Electronics |
| spelling | doaj.art-76c8d580c5a44919835b95d2b719251e2023-11-21T16:29:07ZengMDPI AGElectronics2079-92922021-04-0110999010.3390/electronics10090990Efficiently Estimating Joining Cost of Subqueries in Regular Path QueriesVan-Quyet Nguyen0Van-Hau Nguyen1Minh-Quy Nguyen2Quyet-Thang Huynh3Kyungbaek Kim4Faculty of Information Technology, Hung Yen University of Technology and Education, Hung Yen 160000, VietnamFaculty of Information Technology, Hung Yen University of Technology and Education, Hung Yen 160000, VietnamFaculty of Information Technology, Hung Yen University of Technology and Education, Hung Yen 160000, VietnamSchool of Information and Communication Technology, Hanoi University of Science and Technology, Hanoi 100000, VietnamDepartment of Artificial Intelligence Convergence, Chonnam National University, Gwangju 61186, KoreaEvaluating Regular Path Queries (RPQs) have been of interest since they were used as a powerful way to explore paths and patterns in graph databases. Traditional automata-based approaches are restricted in the graph size and/or highly complex queries, which causes a high evaluation cost (e.g., memory space and response time) on large graphs. Recently, although using the approach based on the threshold rare label for large graphs has been achieving some success, they could not often guarantee the minimum searching cost. Alternatively, the Unit-Subquery Cost Matrix (USCM) has been studied and obtained the viability of the usage of subqueries. Nevertheless, this method has an issue, which is, it does not cumulate the cost among subqueries that causes the long response time on a large graph. In order to overcome this issue, this paper proposes a method for estimating joining cost of subqueries to accelerate the USCM based parallel evaluation of RPQs on a large graph, namely USCM-Join. Through real-world datasets, we experimentally show that the USCM-Join outperforms others and estimating the joining cost enhances the USCM based approach up to around 20% in terms of response time.https://www.mdpi.com/2079-9292/10/9/990graph queriesUSCMparallel evaluationestimating joining cost |
| spellingShingle | Van-Quyet Nguyen Van-Hau Nguyen Minh-Quy Nguyen Quyet-Thang Huynh Kyungbaek Kim Efficiently Estimating Joining Cost of Subqueries in Regular Path Queries Electronics graph queries USCM parallel evaluation estimating joining cost |
| title | Efficiently Estimating Joining Cost of Subqueries in Regular Path Queries |
| title_full | Efficiently Estimating Joining Cost of Subqueries in Regular Path Queries |
| title_fullStr | Efficiently Estimating Joining Cost of Subqueries in Regular Path Queries |
| title_full_unstemmed | Efficiently Estimating Joining Cost of Subqueries in Regular Path Queries |
| title_short | Efficiently Estimating Joining Cost of Subqueries in Regular Path Queries |
| title_sort | efficiently estimating joining cost of subqueries in regular path queries |
| topic | graph queries USCM parallel evaluation estimating joining cost |
| url | https://www.mdpi.com/2079-9292/10/9/990 |
| work_keys_str_mv | AT vanquyetnguyen efficientlyestimatingjoiningcostofsubqueriesinregularpathqueries AT vanhaunguyen efficientlyestimatingjoiningcostofsubqueriesinregularpathqueries AT minhquynguyen efficientlyestimatingjoiningcostofsubqueriesinregularpathqueries AT quyetthanghuynh efficientlyestimatingjoiningcostofsubqueriesinregularpathqueries AT kyungbaekkim efficientlyestimatingjoiningcostofsubqueriesinregularpathqueries |