Please use this identifier to cite or link to this item:
http://hdl.handle.net/1942/40357
Full metadata record
DC Field | Value | Language |
---|---|---|
dc.contributor.author | MARTENS, Wim | - |
dc.contributor.author | Niewerth, Matthias | - |
dc.contributor.author | Popp, Tina | - |
dc.contributor.author | Rojas, Carlos | - |
dc.contributor.author | VANSUMMEREN, Stijn | - |
dc.contributor.author | Vrgoc, Domagoj | - |
dc.date.accessioned | 2023-06-12T07:28:28Z | - |
dc.date.available | 2023-06-12T07:28:28Z | - |
dc.date.issued | 2023 | - |
dc.date.submitted | 2023-06-08T14:41:14Z | - |
dc.identifier.citation | Proceedings of the VLDB Endowment, 16 (7), p. 1790 -1803 | - |
dc.identifier.issn | 2150-8097 | - |
dc.identifier.uri | http://hdl.handle.net/1942/40357 | - |
dc.description.abstract | Modern graph database query languages such as GQL, SQL/PGQ, and their academic predecessor G-Core promote paths to first-class citizens in the sense that their pattern matching facility can return paths, as opposed to only nodes and edges. This is challenging for database engines, since graphs can have a large number of paths between a given node pair, which can cause huge intermediate results in query evaluation. We introduce the concept of path multiset representations (PMRs), which can represent multisets of paths exponentially succinctly and therefore bring significant advantages for representing intermediate results. We give a detailed theoretical analysis that shows that they are especially well-suited for representing results of regular path queries and extensions thereof involving counting, random sampling, and unions. Our experiments show that they drastically improve scalability for regular path query evaluation, with speedups of several orders of magnitude. | - |
dc.description.sponsorship | We are grateful to Matthias Hofer for valuable discussions and to Wojciech Czerwiński for pointing us to [58]. This work was supported by the ANR project EQUUS ANR-19-CE48-0019; funded by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) – project number 431183758. Vansummeren was supported by the Bijzonder Onderzoeksfonds (BOF) of Hasselt University (Belgium) under Grant No. BOF20ZAP02. Vrgoč and Rojas were supported by ANID – Millennium Science Initiative Program – Code ICN17_002. Vrgoč was also supported by ANID Fondecyt Regular grant nr. 1221799. | - |
dc.language.iso | en | - |
dc.publisher | ASSOC COMPUTING MACHINERY | - |
dc.rights | This work is licensed under the Creative Commons BY-NC-ND 4.0 International License. Visit https://creativecommons.org/licenses/by-nc-nd/4.0/ to view a copy of this license. For any use beyond those covered by this license, obtain permission by emailing info@vldb.org. Copyright is held by the owner/author(s). Publication rights licensed to the VLDB Endowment. | - |
dc.title | Representing Paths in Graph Database Pattern Matching | - |
dc.type | Journal Contribution | - |
local.bibliographicCitation.conferencedate | 2023 | - |
local.bibliographicCitation.conferencename | 49th International Conference on Very Large Data Bases (VLDB) | - |
local.bibliographicCitation.conferenceplace | CANADA | - |
dc.identifier.epage | 1803 | - |
dc.identifier.issue | 7 | - |
dc.identifier.spage | 1790 | - |
dc.identifier.volume | 16 | - |
local.format.pages | 14 | - |
local.bibliographicCitation.jcat | A1 | - |
dc.description.notes | Martens, W (corresponding author), Univ Bayreuth, Bayreuth, Germany. | - |
dc.description.notes | wim.martens@uni-bayreuth.de; matthias.niewerth@uni-bayreuth.de; | - |
dc.description.notes | tina.popp@uni-bayreuth.de; c.rojasvictoriano@gmail.com; | - |
dc.description.notes | stijn.vansummeren@uhasselt.be; dvrgoc@ing.puc.cl | - |
local.publisher.place | 1601 Broadway, 10th Floor, NEW YORK, NY USA | - |
local.type.refereed | Refereed | - |
local.type.specified | Article | - |
dc.identifier.doi | 10.14778/3587136.3587151 | - |
dc.identifier.isi | 000992411400016 | - |
dc.identifier.eissn | 2150-8097 | - |
local.provider.type | wosris | - |
local.description.affiliation | [Martens, Wim; Niewerth, Matthias; Popp, Tina] Univ Bayreuth, Bayreuth, Germany. | - |
local.description.affiliation | [Rojas, Carlos; Vrgoc, Domagoj] IMFD Chile, Santiago, Chile. | - |
local.description.affiliation | [Vansummeren, Stijn] UHasselt, Data Sci Inst, Hasselt, Belgium. | - |
local.description.affiliation | [Vrgoc, Domagoj] PUC Chile, Santiago, Chile. | - |
local.uhasselt.international | yes | - |
item.fullcitation | MARTENS, Wim; Niewerth, Matthias; Popp, Tina; Rojas, Carlos; VANSUMMEREN, Stijn & Vrgoc, Domagoj (2023) Representing Paths in Graph Database Pattern Matching. In: Proceedings of the VLDB Endowment, 16 (7), p. 1790 -1803. | - |
item.fulltext | With Fulltext | - |
item.contributor | MARTENS, Wim | - |
item.contributor | Niewerth, Matthias | - |
item.contributor | Popp, Tina | - |
item.contributor | Rojas, Carlos | - |
item.contributor | VANSUMMEREN, Stijn | - |
item.contributor | Vrgoc, Domagoj | - |
item.accessRights | Open Access | - |
crisitem.journal.issn | 2150-8097 | - |
crisitem.journal.eissn | 2150-8097 | - |
Appears in Collections: | Research publications |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
Representing Paths in Graph Database Pattern Matching.pdf | Published version | 960.42 kB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.