JSONSki: streaming semi-structured data with bit-parallel fast-forwarding
JSONSki: streaming semi-structured data with bit-parallel fast-forwarding
复制标题
JSONSki：具有位并行快进的流式半结构化数据
DOI：
10.1145/3503222.3507719
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Zhao, Zhijia
中科院分区：
文献类型：
--
作者：
Jiang, Lin;Zhao, Zhijia
半结构化数据，如JSON，是Web和文档数据存储的基础。对半结构化数据的流分析将解析和查询评估结合到一个遍中，以避免生成解析树。它的传统设计需要逐个字符地对数据流进行详细的解析，这限制了流分析的效率。这项工作揭示了在某些与查询评估无关的数据子结构上快速转发流的机会。然而，识别这些子结构本身可能需要详细的解析。为了解决这一困境，本工作设计了一种高度比特并行的解决方案，该方案密集地利用逐位和SIMD操作来识别流过程中不相关的子结构。它包括一个新的流模型-递归下降流，以便于采用快进优化，一个概念-结构间隔，用于划分数据流，以及一组实现各种快进情况的位并行算法。该解决方案以JSON流框架的形式实现，称为JSONSki。它提供了一组API，可以在流传输过程中调用这些API，以便在不相关的子结构的不同情况下动态快进。使用真实数据集和标准路径查询进行的评估表明，JSONSki可以在占用最少内存的情况下实现比最先进的JSON处理工具显著的加速。
Semi-structured data, such as JSON, are fundamental to the Web and document data stores. Streaming analytics on semi-structured data combines parsing and query evaluation into one pass to avoid generating parse trees. Though promising, its conventional design requires to parse the data stream in detail character by character, which limits the efficiency of streaming analytics.This work reveals a wide range ofopportunities to fast-forwardthe streaming over certain data substructures irrelevant to the query evaluation. However, identifying these substructures itself may need detailed parsing. To resolve this dilemma, this work designsa highly bit-parallel solutionthat intensively utilizes bitwise and SIMD operations to identify the irrelevant substructures during the streaming. It includes a new streaming model—recursive-descent streaming, for an easy adoption of fast-forward optimizations, a concept—structural intervals, for partitioning the data stream, and a group of bit-parallel algorithms implementing various fast-forward cases. The solution is implemented as a JSON streaming framework, called JSONSki. It offers a set of APIs that can be invoked during the streaming to dynamically fast-forward over different cases of irrelevant substructures. Evaluation using real-world datasets and standard path queries shows that JSONSki can achieve significant speedups over the state-of-the-art JSON processing tools while taking a minimum memory footprint.
登录
查看更多内容
商品并行处理器上当代半结构化数据的可扩展处理 - 基于编译的方法
DOI：
10.1145/3297858.3304008
发表时间：
2019
期刊：
Proceedings of the Twenty-Fourth International Conference on Architectural Support for Programming Languages and Operating Systems - ASPLOS '19
影响因子：
--
作者：
Jiang, Lin;Sun, Xiaofan;Farooq, Umar;Zhao, Zhijia
通讯作者：
Zhao, Zhijia
MicroSpec：用于 FSM 计算的以推测为中心的细粒度并行化
DOI：
10.1145/2967938.2967965
发表时间：
2016
期刊：
2016 International Conference on Parallel Architecture and Compilation Techniques (PACT)
影响因子：
--
作者：
Junqiao Qiu;Zhijia Zhao;Bin Ren
通讯作者：
Bin Ren
使用 XHints 跳过流
DOI：
--
发表时间：
2004
期刊：
影响因子：
--
作者：
Akhil Gupta;S. Chawathe
通讯作者：
S. Chawathe
通过有原则的按位推测挑战顺序比特流处理
DOI：
10.1145/3373376.3378461
发表时间：
2020
期刊：
Proceedings of the Twenty-Fifth International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS'20
影响因子：
--
作者：
Qiu, Junqiao;Jiang, Lin;Zhao, Zhijia
通讯作者：
Zhao, Zhijia
可扩展 XPath 查询的语法感知并行化
DOI：
--
发表时间：
2017
期刊：
ACM SIGPLAN Symposium on Principles & Practice of Parallel Programming
影响因子：
--
作者：
Lin Jiang;Zhijia Zhao
通讯作者：
Zhijia Zhao