Graph Clustering for Keyword Search

Abstract

Keyword search on data represented as graphs, is re- ceiving lot of attention in recent years. Initial versions of keyword search systems assumed that the graph is memory resident. However, there are applications where the graph can be much larger than the avail- able memory. This led to the development of search algorithms which search on a smaller memory resident summary graph (supernode graph), and fetch parts of the original graph from the disk, only when required. In this scenario, good clustering of nodes into supern- odes, when constructing the summary graph, is a key to ecient search. In this paper, we address the issue of graph clustering for keyword search, using a technique based on ran- dom walks. We propose an algorithm, which we call Modied Nibble clustering algorithm, that improves upon the Nibble algorithm proposed earlier. We out- line several policies that can improve its performance. Then, we compare our algorithm with two graph clus- tering algorithms proposed earlier, EBFS and kMetis. Our performance metrics include edge compression, keyword search performance, and the time and space overheads for clustering. Our results show that Modi- ed Nibble outperforms EBFS uniformly, and outper- forms kMetis in some settings. Further, the memory requirements of our algorithm are much lower than that of kMetis, making it practical even with a very large number of nodes, unlike kMetis.