ConnectionLens is a Java-based project developed by the Cedar research team at Inria which, given a set of heterogeneous data sources, consolidates them into a single graph. The graph is stored into a relational database (i.e. PostgreSQL). Furthermore, a keyword search query algorithm has been developed in Java, consulting ConnectionLens nodes and edges from the PostgreSQL back-end. In the present work, we seek to improve the performance of the query algorithm by: (i) migrating graphs built by ConnectionLens into a new graph store, developed in C++ and memory-resident; (ii) developing a novel query algorithm that accesses the graph from such an in-memory store and takes advantage of multi-thread parallelism.