Charla: Data Structures for Path Queries

Meng He
1 Septiembre, 2016 - 10:30
Auditorio Ramón Picarte, Piso 3, Edificio Norte
Gonzalo Navarro y Jérémy Barbay

Meng He is currently an assistant professor at the Faculty of Computer Science in Dalhousie University in Canada. He obtained his PhD from the University of Waterloo in 2008. Prior to joining Dalhousie University, he had held postdoctoral and research positions in Carleton University and the University of Waterloo.  Meng He's research areas are algorithms, data structures and computational geometry, and his research has been focused on the design of fast and space-efficient data structures for large data sets. He has authored over forty peer-reviewed publications on this subject. Dr. He is presently serving as a steering committee member of the Canadian Conference on Computational Geometry, has co-chaired the 26th Canadian Conference on Computational Geometry (CCCG 2014), and has served in the program committees of CPM, CCCG and EuroCG.


This talk presents new results on several path queries in trees in which each node is assigned a weight value. This is motivated by the needs of the manipulation of tree-structured data such as XML trees and tree network topology. One such query is path counting, in which we are given an arbitrary query path defined by two nodes and a query weight range, and the goal is to count the number of nodes along this path whose weights are within the given range. We designed succinct data structures that can answer path counting in optimal time. More precisely, our structure occupies nH(W_T) + o(n lg sigma) bits, where n denotes the number of nodes in the tree, H(W_T) denotes the entropy of the node weights, and sigma is the distinct number of weights, and answers queries in O(lg sigma / lg lg n + 1) time. Several other path queries can be defined in a similar way, including path median, path minimum and path reporting. We also achieved new results for these problems, including an optimal solution to path median, a lower bound on path minimum in the encoding model, an upper bound for path minimum in the indexing model, and results for path reporting matching the state of the art of solutions to 2D orthogonal range reporting. In addition, we designed efficient dynamic data structures for path counting and reporting.  All these results generalize queries in 2D point sets and arrays to trees.