A Generic Ontology Framework for Indexing Keyword Search on Massive Graphs

Jiaxin Jiang*, Koon Kau Choi, Jianliang Xu, Sourav S. Bhowmick

*Corresponding author for this work

Research output: Contribution to journalJournal articlepeer-review

5 Citations (Scopus)


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 paper, we propose a generic ontology-based indexing framework for keyword search, called Bisimulation of Generalized Graph Index (BiG-index BiG-index), to enhance the search performance. The novelties of BiG-index BiG-index reside in using an ontology graph G Ont GOnt to summarize and index a data graph G G iteratively, to form a hierarchical index structure G. BiG-index BiG-index is generic since it only requires keyword search algorithms to generate query answers from summary graphs having two simple properties. Regarding query evaluation, we transform a keyword search q q into Q according to G Ont GOnt in runtime. The transformed query is searched on the summary graphs in G. The efficiency is due to the small sizes of the summary graphs and the early pruning of semantically irrelevant subgraphs. To illustrate BiG-index BiG-index's applicability, we show popular indexing techniques for keyword search (e.g., Blinks Blinks and r-clique r-clique) can be easily implemented on top of BiG-index BiG-index. Our extensive experiments show that BiG-index BiG-index reduced the runtimes of popular keyword search work Blinks Blinks by 50.5 percent and r-clique r-clique by 29.5 percent.
Original languageEnglish
Pages (from-to)2322-2336
Number of pages15
JournalIEEE Transactions on Knowledge and Data Engineering
Issue number6
Early online date28 Nov 2019
Publication statusPublished - 1 Jun 2021

Scopus Subject Areas

  • Information Systems
  • Computer Science Applications
  • Computational Theory and Mathematics

User-Defined Keywords

  • Keyword search
  • graphs
  • indexing
  • ontology graphs


Dive into the research topics of 'A Generic Ontology Framework for Indexing Keyword Search on Massive Graphs'. Together they form a unique fingerprint.

Cite this