论文标题
路径查询数据结构实践
Path Query Data Structures in Practice
论文作者
论文摘要
我们对回答路径中值，路径计数和加权树中路径报告查询的数据结构进行实验研究。这些查询问题概括了阵列中众所周知的范围中位数查询问题，以及$ 2D $正交范围的计数和平面点集中的报告问题，即树结构化数据。我们提出了有关路径查询的最新理论结果的实际实现。我们的数据结构以简洁和基于指针的形式实现了使用树提取，重径分解和小波树的使用。我们的简洁数据结构进一步专门化，可以是普通或熵压缩的。通过大型集合的实验，我们表明，在实际场景中，简洁的数据查询数据结构可能是基于标准指针的实现的可行替代方案。与通过显式遍历查询路径计算答案的NA {} VE方法相比，我们简洁的数据结构在路径中间查询中的几倍更快，并且在路径计数和路径报告查询中的表现相当，同时多次效率。基于简单的指针的实现我们的数据结构，需要比Na {{{ve ve的空间多倍的空间，而对它们产生了高达$ 100 $的速度。
We perform experimental studies on data structures that answer path median, path counting, and path reporting queries in weighted trees. These query problems generalize the well-known range median query problem in arrays, as well as the $2d$ orthogonal range counting and reporting problems in planar point sets, to tree structured data. We propose practical realizations of the latest theoretical results on path queries. Our data structures, which use tree extraction, heavy-path decomposition and wavelet trees, are implemented in both succinct and pointer-based form. Our succinct data structures are further specialized to be plain or entropy-compressed. Through experiments on large sets, we show that succinct data structures for path queries may present a viable alternative to standard pointer-based realizations, in practical scenarios. Compared to na{ï}ve approaches that compute the answer by explicit traversal of the query path, our succinct data structures are several times faster in path median queries and perform comparably in path counting and path reporting queries, while being several times more space-efficient. Plain pointer-based realizations of our data structures, requiring a few times more space than the na{ï}ve ones, yield up to $100$-times speed-up over them.
