KeyLabel Algorithms for Keyword Search in Large Graphs

Resource type
Thesis type
(Thesis) M.Sc.
Date created
Author: Wang, Yue
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.
Copyright statement
Copyright is held by the author.
This thesis may be printed or downloaded for non-commercial research and scholarly purposes.
Scholarly level
Supervisor or Senior Supervisor
Thesis advisor: Wang, Ke
Attachment Size
etd9175_YWang.pdf 697.77 KB