KeyLabel Algorithms for Keyword Search in Large Graphs

Graph keyword search is the process of extracting small subgraphs that contain a set of query keywords from a graph. This problem is challenging because there are many constraints, including distance constraint, keyword constraint, search time constraint, index size constraint, and memory constraint, while the size of data is inflating at a very high speed nowadays. Existing greedy algorithms guarantee good performance by sacrificing accuracy to generate approximate answers, and exact algorithms promise exact answers but require huge memory consumption for loading indices and advanced knowledge about the maximum distance constraint. We propose a new keyword search algorithm that finds exact answers with low memory consumption and without pre-defined maximum distance constraint. This algorithm builds a compact index structure offline based on a recent labeling index for shortest path queries. At the query time, it finds answers efficiently by examining a small portion of the index related to a query.