Path Query Data Structures in Practice
share
Let us be given an ordinal tree, such that each node of it has a certain associated weight. We design, implement, and evaluate space- and time-performance of data structures to answer online path queries on such a tree: path counting, path reporting, and path median queries. These query problems generalize the problems of 2d orthogonal range counting and reporting in planar point sets, as well as the range median query problem in arrays, to tree structured data. We propose practical realizations of the latest theoretical results in path queries. Our data structures, whose components include tree extraction, heavy-path decomposition, and wavelet trees, are implemented in both succinct and plain pointer-based form. Our succinct data structures are further specialized into entropy-compressed and plain forms. Through a set of experiments on large datasets, we show that succinct data structures for path queries present a viable alternative to standard pointer-based realizations in practical scenarios. We compare the performance of our data structures to naive approaches that encode the tree in plain pointer-based form and do not preprocess it to speedup the queries, but rather compute the answer by explicitly traversing the query path and checking the nodes. 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, than such naive approaches. Plain pointer-based realizations of our data structures, requiring a few times more space than the naive structures, yield a 30-100-times speedup over them. In addition, our succinct data structures provide more functionality within the little space they use than their plain pointer-based counterparts.
READ FULL TEXT