Keyword Search over Knowledge Graphs via Static and Dynamic Hub Labelings

Yuxuan Shi, Gong Cheng, Evgeny Kharlamov

Abstract

Keyword search is a prominent approach to querying Web data. For graph-structured data, a widely accepted semantics for keywords is based on group Steiner trees. For this NP-hard problem, existing algorithms with provable quality guarantees have prohibitive run time on large graphs. In this paper, we propose practical approximation algorithms with a guaranteed quality of computed answers and very low run time. Our algorithms rely on Hub Labeling (HL), a structure that labels each vertex in a graph with a list of vertices reachable from it, which we use to compute distances and shortest paths. We devise two HLs: a conventional static HL that uses a new heuristic to improve pruned landmark labeling, and a novel dynamic HL that inverts and aggregates query-relevant static labels to more efficiently process vertex sets. Our approach allows to compute a reasonably good approximation of answers to keyword queries in milliseconds on million-scale knowledge graphs.
BibTeX
@inproceedings{shi2020keyword,
  author = {Yuxuan Shi and Gong Cheng and Evgeny Kharlamov},
  title = {{Keyword Search over Knowledge Graphs via Static and Dynamic Hub Labelings}},
  booktitle = {The Web Conference},
  year = {2020},
  doi = {10.1145/3366423.3380110},
}

Loading related content...

Figure