Succinct Data Structures with Applications to Large Data Sets

点击翻译按钮获取中文摘要

As the size of the data has grown rapidly in recent years, many techniques that were useful for small, older systems have become outdated for large, modern applications, since they occupy too much space to fit into faster levels of memory hierarchy. Most of this space is not the 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. My main research interests are in the design of succinct data structures to represent fundamental structures such as strings, binary relations, trees and graphs, as well as the design of space-efficient solutions to geometric query problems, text indexing and classic query problems over trees and arrays. My research also involves other algorithmic techniques that can be applied to large data sets. When data are too big to fit in internal memory, I/O-efficient algorithms can be used to minimize the data transfer between internal memory and secondary storage which often dominates computational cost. The idea of implicit data structures is to encode a data structure as a permutation of its data elements if possible, so that no additional space is required. Adaptive algorithms aim at improving query efficiency for data with more inherent sortedness. Parallel algorithms use multiple processors to achieve speedup. Our work shows that these techniques and succinct structures can be combined to provide more efficient solutions for large data sets, and the advancement in one technique may lead to new results for another. To provide theoretical and practical solutions to modern systems that process large data sets such as web search engines, geographic information systems and bioinformatics applications, this program will extend the research on succinct data structures, and start new research directions on this subject. The proposed research will use succinct data structures to develop new solutions to fundamental problems in algorithms and computational geometry such as text search and range search. Not only will this research yield new data structures that are more space-efficient than those designed in previous work, it will also improve the query and update efficiency of standard data structures; the latter is achieved by exploiting the compactness of succinct data structures to store more structural information to speed up operations without increasing the space cost. We will also start a new line of research by designing succinct data structures for bioinformatics applications.