Hong Kong Baptist University (HKBU) Research Cluster on Data Analytics and Artificial Intelligence in X

Semantic Indexing for Keyword Search on Graphs
Principal Investigatgor: Dr. Byron CHOI ( Department of Computer Science )

Tremendous effort is spent on creating knowledge networks, such as the open source knowledge base (e.g., YAGO), structured data of Wikipedia (e.g., DBpedia), collaborative knowledge bases (e.g., Freebase) and Google knowledge networks. Ontology information is often associated with those networks that encode the definitions of and semantic relationships between entities and the like. Many emerging applications have been recently built on top of ontologies. In this project, we investigate a novel, generic approach that exploits ontology information to index data graphs themselves to improve query efficiency. We call it semantic indexing.

While semantic indexing is a general concept, to illustrate its potentials, this project focuses on keyword search on graphs, which is fundamental to many applications of knowledge networks and easy-to-use. We show that, first, some semantically relevant entities can be generalized to their same supertypes/superclasses, and that generalization makes the entities and their relationships less heterogeneous for indexing. Second, we summarize the generalized graph into a smaller graph. These two steps are repeated alternately until the summary graph is small enough. Our semantic index is then the hierarchy of these summary graphs. We integrate the current state-of-the-art of algorithms into semantic indexing. We investigate efficient algorithms for exploratory data analysis (EDA) via keyword searches. We expect this project offers a new indexing approach. It improves the efficiency of the current state-of-the-art methods, and subsequently, their applications.


  • To define the semantic index structure;
  • To develop the indexed versions of the core keyword search algorithms on graphs;
  • To study exploratory data analysis via keywords with semantic indexing; and
  • To study the search on multiple graphs and ontologies

Grant Support:

This project is supported by the General Research Fund (GRF), Research Grants Council (RGC), Hong Kong SAR, China (Project 12201119).

For further information on this research topic, please contact Dr. Byron CHOI.