.png){kind=icon}
返回
CompactLTJ: Space & Time Efficient Leapfrog Triejoin on Graph Databases
.png){kind=icon}
OA
AI
DOI：10.1007/s00778-025-00945-5.png)
.png){kind=icon}
.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
跳跃式Trie连接（LTJ）可能是解决图数据库中基本图模式的最实用且流行的最坏情况最优（wco）算法。其主要缺点是需要将数据库三元组（主体、谓词、客体）以六种主体、谓词和客体的顺序表示为Trie中的路径。由此产生的空间膨胀使得大多数系统忽略LTJ或仅部分实现它，从而使其对应算法不再是最坏情况最优。在本文中，我们证明通过使用紧凑数据结构，可以构建一个索引，同时匹配最快经典wco索引的查询时间性能，并使用非wco索引（这些索引慢得多）所需空间的几分之一。具体而言，我们利用紧凑的树表示方法，使用每条Trie边一个比特而非一个指针来存储函数Trie，并通过存储部分Trie进一步减少空间。我们最紧凑的变体比经典wco实现少用5～6倍空间，比经典非wco系统少用2～3倍空间。在解决查询时，其性能与最快经典wco系统相当，且比非wco系统快30～40倍。我们进一步将改进的查询解析策略纳入CompactLTJ变体中，使其在输出结果不太多的情况下，比经典wco系统快得多。最后，我们展示了CompactLTJ如何在不影响性能的情况下引入动态性，即使在非常苛刻的更新模式下也是如此。我们提供了一个公开的、功能完整的CompactLTJ实现，可直接供实践者使用。
Keyword:
Worst-case optimal joins
Leapfrog Triejoin
compact data structures
graph patterns
graph databases
AI总结
对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。
期刊
T
IF:
0
论文数:
36
被引数:
0
查看更多机构
.png){kind=icon}
