# 5.5. Index construction

Given a data multigraph *G*, we build the following three different indices: (i) an inverted list *A* for storing the set of data vertex for each attribute in *a _{i}* ∈

*A*; (ii) a trie index structure

*S*to store features of all the data vertices

*V*and (iii) a set of trie index structures

*N*to store the neighborhood information of each data vertex

*v*∈

*V*. For brevity of representation, we ensemble all the three index structures into

*I*:= {

*A,S,N*}. During the query matching procedure (the online step), we access these indexing structures to obtain the candidate solutions for a query vertex

*u*. Formally, for a query vertex

*u*, the

*candidate solutions*are a set of data vertices

*C*= {

_{u}*v*|

*v*∈

*V*} obtained by accessing

*A*,

*S*or

*N*, denoted as respectively.

## 5.5.1. *Attribute index*

The set of vertex attributes is given by *A* = {*a*_{0}, …, *a _{n}*} (section 5.3), where a data vertex

*v*∈

*V*might have a subset of

*A*assigned to it. We now build the vertex attribute index...