Grant: Discovery Grants Program - Individual

The problem of efficiently storing and retrieving information is an essential topic in computer science. During the past decades, many techniques have been developed to index data so that useful information can be retrieved almost instantaneously by performing queries for keywords or phrases. In recent years, as the size of the data has grown rapidly, many techniques that were useful for small, older systems have become infeasible for large, modern applications, because they occupy too much space to fit into faster levels of memory hierarchy. Most of this space is not raw data, but structural information added to improve search efficiency. Succinct data structures were proposed to address this problem, so that the information in large systems can be retrieved quickly, but the space requirement is little more than that of the raw data. To provide solutions to modern systems that process large data sets such as web search engines, geographic information systems, social network platforms and bioinformatics applications, this program will extend the research on succinct data structures and start new research directions on the design of efficient data structures in general. One research direction is to add more complex search functionalities to succinct data structures for many classes of graphs, in addition to the support of basic navigational operations. One complex query to consider is the computation of distance between two nodes in a graph, which is often used to determine how closely the two entities they represent are related to each other in data analytics applications. Another research direction is on the design of efficient data structures for dynamic graphs, as graphs in many real-world applications are updated constantly. Specifically, we plan to extend a new approach we are currently developing for dynamic interval graphs to design dynamic data structures for computational problems over geometric intersection graphs which model the intersection between geometric objects and have natural applications in wireless communication. For this work, we also intend to apply an additional strategy which is to use succinct data structures as building blocks to store more information in data structure solutions to speed up queries without using more space asymptotically. Finally, during our recent research, we encountered several data structure problems that have fine-grained complexity results, which, based on reductions from well-known problems such as Boolean matrix multiplication, give evidence on the difficulty on further improving existing combinatorial solutions. To improve the throughput of the information systems that need solutions to these query problems, we intend to use methods based on algebraic approaches of matrix multiplication to design solutions that can process a batch of these queries more quickly.