Path Queries in Weighted Trees

Data Structures;Path Queries;Path Counting;Path Reporting;Path Median;Path Selection;Tree Extraction;Computer Science

Zhou, Gelin

University of Waterloo

关键词: Data Structures;    Path Queries;    Path Counting;    Path Reporting;    Path Median;    Path Selection;    Tree Extraction;    Computer Science;   

Others  :  https://uwspace.uwaterloo.ca/bitstream/10012/6883/1/Zhou_Gelin.pdf

瑞士|英语

来源: UWSPACE Waterloo Institutional Repository

【 摘 要 】

Trees are fundamental structures in computer science, being widely used in modeling and representing different types of data in numerous computer applications. In many cases,properties of objects being modeled are stored as weights or labels on the nodes of trees.Thus researchers have studied the preprocessing of weighted trees in which each node isassigned a weight, in order to support various path queries, for which a certain functionover the weights of the nodes along a given query path in the tree is computed [3, 14, 22, 26].In this thesis, we consider the problem of supporting several various path queries overa tree on n weighted nodes, where the weights are drawn from a set of σ distinct values.One query we support is the path median query, which asks for the median weight on apath between two given nodes. For this and the more general path selection query, wepresent a linear space data structure that answers queries in O(lg σ) time under the wordRAM model. This greatly improves previous results on the same problem, as previous datastructures achieving O(lg n) query time use O(n lg^2 n) space, and previous linear space datastructures require O(n^ε) time to answer a query for any positive constant ε [26].We also consider the path counting query and the path reporting query, where a pathcounting query asks for the number of nodes on a query path whose weights are in aquery range, and a path reporting query requires to report these nodes. Our linear spacedata structure supports path counting queries with O(lg σ) query time. This matchesthe result of Chazelle [14] when σ is close to n, and has better performance when σ issignificantly smaller than n. The same data structure can also support path reportingqueries in O(lg σ + occ lg σ) time, where occ is the size of output. In addition, we presenta data structure that answers path reporting queries in O(lg σ + occ lg lg σ) time, usingO(n lg lg σ) words of space. These are the first data structures that answer path reportingqueries.