  Graph similarity search has received considerable attention in many
applications, such as bioinformatics, data mining, pattern recognition, and
social networks. Existing methods for this problem have limited scalability
because of the huge amount of memory they consume when handling very large
graph databases with millions or billions of graphs.
  In this paper, we study the problem of graph similarity search under the
graph edit distance constraint. We present a space-efficient index structure
based upon the q-gram tree that incorporates succinct data structures and
hybrid encoding to achieve improved query time performance with minimal space
usage. Specifically, the space usage of our index requires only 5%-15% of the
previous state-of-the-art indexing size on the tested data while at the same
time achieving 2-3 times acceleration in query time with small data sets. We
also boost the query performance by augmenting the global filter with range
search, which allows us to perform a query in a reduced region. In addition, we
propose two effective filters that combine degree structures and label
structures. Extensive experiments demonstrate that our proposed approach is
superior in space and competitive in filtering to the state-of-the-art
approaches. To the best of our knowledge, our index is the first in-memory
index for this problem that successfully scales to cope with the large dataset
of 25 million chemical structure graphs from the PubChem dataset.
