Scholarlink

<p>Leapfrog Triejoin (LTJ) is arguably the most practical and popular worst-case-optimal (wco) algorithm for solving basic graph patterns in graph databases. Its main drawback is that it needs the database triples (subject, predicate, object) represented as paths in a trie, for each of the six orders of subject, predicate, and object. The resulting blowup in space makes most systems disregard LTJ or implement it only partially, which makes their corresponding algorithms non-wco. In this paper we show that, by using compact data structures, it is possible to build an index that at the same time matches the query time performance of the fastest classic wco index, and uses a fraction of the space of non-wco indices (which are much slower). Concretely, we make use of compact tree representations to store functional tries using one bit per trie edge, instead of one pointer, and further reduce the space by storing partial tries. Our most compact variant uses 5–6 times less space than classic wco implementations and 2–3 times less than classic non-wco systems. At solving queries, it is on par with the fastest classic wco system, and 30–40 times faster than non-wco systems. We further incorporate improved query resolution strategies into <i>CompactLTJ</i> variants, which makes it considerably faster than classic wco systems as well, on queries that do not output too many results. Finally, we show how <i>CompactLTJ</i> can incorporate dynamism without altering its performance, even under very demanding update regimes. We leave a public fully-functional implementation of <i>CompactLTJ</i> that can be directly used by practitioners.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

CompactLTJ: Space & Time Efficient Leapfrog Triejoin on Graph Databases

  • 期刊论文

  • 出版模式：

    开放获取

  • 发表日期：

    2025年9月25日

查看全文
  • Diego Arroyuelo,
  • Daniela Campos,
  • Adrián Gómez-Brandón,
  • Yuval Linker,
  • Gonzalo Navarro,
  • Carlos Rojas,
  • Domagoj Vrgoč

摘要

Leapfrog Triejoin (LTJ) is arguably the most practical and popular worst-case-optimal (wco) algorithm for solving basic graph patterns in graph databases. Its main drawback is that it needs the database triples (subject, predicate, object) represented as paths in a trie, for each of the six orders of subject, predicate, and object. The resulting blowup in space makes most systems disregard LTJ or implement it only partially, which makes their corresponding algorithms non-wco. In this paper we show that, by using compact data structures, it is possible to build an index that at the same time matches the query time performance of the fastest classic wco index, and uses a fraction of the space of non-wco indices (which are much slower). Concretely, we make use of compact tree representations to store functional tries using one bit per trie edge, instead of one pointer, and further reduce the space by storing partial tries. Our most compact variant uses 5–6 times less space than classic wco implementations and 2–3 times less than classic non-wco systems. At solving queries, it is on par with the fastest classic wco system, and 30–40 times faster than non-wco systems. We further incorporate improved query resolution strategies into CompactLTJ variants, which makes it considerably faster than classic wco systems as well, on queries that do not output too many results. Finally, we show how CompactLTJ can incorporate dynamism without altering its performance, even under very demanding update regimes. We leave a public fully-functional implementation of CompactLTJ that can be directly used by practitioners.