Developing 3-in-1 Index Structures on Complex Structure Similarity Search

Abstract

In traditional relational databases, data are modeled as tables. However, most real life data cannot be simply modeled as tables, but as complex structures like sequences, trees and graphs. Existing systems typically cater to the storage of complex structures separately. Therefore, each application domain may need to redesign the storage system for a specific complex structure. Obviously, this can result in a waste of resources. Moreover, many applications may require the storage of various complex structures, and it is not easy to adapt existing systems to support such applications. In this dissertation, we aim to develop a unified framework, denoted by 3-in-1, that can support the efficient storage and retrieval of various complex structures (i.e., sequences, trees, and graphs).

In our work, the inverted index has been shown to be effective to support efficient complex structure similarity search, such as sequence KNN search and graph similarity search. Consequently, we use it as the basic index structure to develop a unified retrieval framework for supporting various complex structures. In this work, we implement the 3-in-1 system with three layers: the storage layer, the index layer, and the application layer. In the storage layer, various types of original data is stored in the file system. In the index layer, we implement a unified inverted index for various complex structures. The application layer is the processing layer where each type of complex structure can build specific processor to communicate with the other two layers. This system can be very useful as it can support many complex applications that involve a variety of complex structures. For instance, we apply it to a real ebook reading system for solving several real problems, and present the initial demo from http://readpeer.com.