.png){kind=icon}
返回
Efficient Parallel Boolean Expression Matching
.png){kind=icon}
PRE
AI
DOI：10.1145/3736756.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
布尔表达式匹配在许多应用中扮演着重要角色。然而，现有解决方案仍存在效率与可扩展性限制。例如，现有解决方案在应用于高维和多样化工作负载时通常表现出性能下降，且现有算法很少考虑在多核环境下支持并发匹配和索引更新。为克服这些限制，本文首先设计了PS-Tree数据结构，以高效地为一维布尔表达式建立索引。通过将谓词划分为不相交的谓词空间，PS-Tree实现了高匹配性能和良好的表达能力。基于PS-Tree，我们提出了一种名为PSTDynamic的布尔表达式匹配算法。通过动态调整索引并高效过滤掉大部分不匹配的布尔表达式，PSTDynamic在处理高维和多样化工作负载时实现了高匹配性能。针对多核环境，我们进一步将PSTDynamic算法扩展为PSTParallel，以实现可扩展性，同时降低匹配延迟并提高匹配吞吐量。我们在合成数据集和真实数据集上进行了实验。实验验证了我们提出的算法具有高效率和并行性。此外，它们还实现了快速索引构建和较小的内存占用。全面的实验结果表明，我们的解决方案显著优于当前最先进的方法。
Keyword:
Parallel matching
Boolean expressions
complex event processing
data structure
publish/subscribe
期刊
A
IF:
1.7
论文数:
11
被引数:
0
机构
引用论文
.png){kind=icon}
Lap: A latency‐aware parallelism framework for content‐based publish/subscribe systemsLap：一种面向延迟的内容感知并行框架，用于基于内容的发布/订阅系统
PREAI
分享收藏分享收藏分享收藏分享收藏
查看更多内容