A Generic Ontology Framework for Indexing Keyword Search on Massive Graphs (Extended Abstract)

Due to the unstructuredness and the lack of schema information of knowledge graphs, social networks and RDF graphs, keyword search has been proposed for querying such graphs/networks. Recently, various keyword search semantics have been designed. In this work, we propose a generic ontology-based indexing framework for keyword search, called Bisimulation of Generalized Graph Index (BiG-index), to enhance the search performance. Novelties of BiG-index reside in using an ontology graph G Ont to summarize and index a data graph G iteratively, to form a hierarchical index structure ${\mathbb{G}}$. BiG-index is generic since it is applicable to keyword search algorithms that have two properties. BiG-index reduced the runtimes of popular keyword search work Blinks by 50.5% and r-clique by 29.5%.