The ability to extract or retrieve useful knowledge has become one of the most important challenges in government, industry, and scientific communities. Much success has been achieved when the data to be mined / retrieved and their relationships are modeled as graphs. Over the past few years, research on efficient mining and querying graph data has steadily increased. Among many graph-based applications, there are special interests on two types of applications: graph reachability query and approximate graph matching query. To efficiently process the aforementioned querying and mining tasks, indexing is widely adopted. However, the performance of an indexing technique is often influenced by the structural- and attribution- properties of the graph to be indexed. Unfortunately, there has not been much work on applying suitable indexes to a graph or subgraph with a specific structure. In addition, utilizing both structures and attributes to do indexing has not been well studied.