DROPS

Document

DOI: 10.4230/LIPIcs.ICDT.2016.23

A Practically Efficient Algorithm for Generating Answers to Keyword Search Over Data Graphs

Authors: Konstantin Golenberg and Yehoshua Sagiv

Published in: LIPIcs, Volume 48, 19th International Conference on Database Theory (ICDT 2016)

Abstract

In keyword search over a data graph, an answer is a non-redundant subtree that contains all the keywords of the query. A naive approach to producing all the answers by increasing height is to generalize Dijkstra's algorithm to enumerating all acyclic paths by increasing weight. The idea of freezing is introduced so that (most) non-shortest paths are generated only if they are actually needed for producing answers. The resulting algorithm for generating subtrees, called GTF, is subtle and its proof of correctness is intricate. Extensive experiments show that GTF outperforms existing systems, even ones that for efficiency's sake are incomplete (i.e., cannot produce all the answers). In particular, GTF is scalable and performs well even on large data graphs and when many answers are neede

Cite as

Konstantin Golenberg and Yehoshua Sagiv. A Practically Efficient Algorithm for Generating Answers to Keyword Search Over Data Graphs. In 19th International Conference on Database Theory (ICDT 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 48, pp. 23:1-23:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{golenberg_et_al:LIPIcs.ICDT.2016.23,
  author =	{Golenberg, Konstantin and Sagiv, Yehoshua},
  title =	{{A Practically Efficient Algorithm for Generating Answers to Keyword Search Over Data Graphs}},
  booktitle =	{19th International Conference on Database Theory (ICDT 2016)},
  pages =	{23:1--23:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-002-6},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{48},
  editor =	{Martens, Wim and Zeume, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2016.23},
  URN =		{urn:nbn:de:0030-drops-57923},
  doi =		{10.4230/LIPIcs.ICDT.2016.23},
  annote =	{Keywords: Keyword search over data graphs, subtree enumeration by height, top-k answers, efficiency}
}

Search Results

Documents authored by Sagiv, Yehoshua

A Practically Efficient Algorithm for Generating Answers to Keyword Search Over Data Graphs

Abstract

Cite as

Thanks for your feedback!

Could not send message