Adaptive Filtering for Efficient Subgraph Isomorphism in Graph Databases


(GRF HKBU 210510, 2011-2012)



PI: Byron Choi

Students: Yun Peng




Graph/Network data model has been a powerful tool to model complicated structures such as social networks, network traffic, biological databases and XML documents, among many others. A typical task on graph data is to retrieve substructures embedded. Formally speaking, given a query graph and a graph database, we want to find the subgraph(s), in the data graphs, that is/are isomorphic to the query graph. The current state-of-the-art technique for subgraph isomorphism almost always comprise two phases -- the filtering and verification phases. The filtering phase is often performed by specialized or feature-based indexes. The pruning power of indexes is evidently crucial to the overall performance. Data graphs are often changing or evolving, which may affect the indexes' pruning powers. In this project, we propose to adjust the indexes adaptively, in response to query workloads.


Start date: 01-01-2011

Complete date: 31-12-2012


Under construction.