Storage efficient graph search by composite dynamic-and-static indexing of a single network

Nowadays, the surge of complex structured data in the form of single information network puts new challenges for advanced searching and indexing mechanisms. Traditional feature-based indexing no longer works in the new scenario, because the mining deficiency and pattern recurrence curse on the excessive and complicated internal structure prevent index construction and storage from being handled efficiently. In this paper, we propose an integrated dynamic-and-static indexing (DS-Index) scheme which can build a best-of-breed feature-based index on a single network and let it dynamically adapt to the query requirement. To achieve this, an r-enhanced partitioning strategy is employed to transform the network into a database of small graphs. Therefore we can efficiently extract indexing features and bypass the storage difficulty of pattern recurrence curse. Then a corresponding r-decomposition strategy of queries into features is further proposed to process queries in a decompose-and-recombine manner so that each feature can be dynamically indexed on the fly. The integrated framework will guarantee that recombining all look-up results returns complete query answers on the original network. This key property, i.e., r-preservation principle of features, cannot be achieved by brute-force partitioning and querying due to the loss of structures. We refer to the proposed two-stage approach as DS (dynamic-and-static) index, as different from traditional offline index construction, the indexing information of query features here is “dynamically created on-the-fly” by looking up the static database index.