Search Results

Documents authored by Golenberg, Konstantin


Document
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}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail