Blog
About

69
views
0
recommends
+1 Recommend
0 collections
    0
    shares
      • Record: found
      • Abstract: found
      • Article: found
      Is Open Access

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

      Preprint

      ,

      Read this article at

      Bookmark
          There is no author summary for this article yet. Authors can add summaries to their articles on ScienceOpen to make them more accessible to a non-specialist audience.

          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 needed.

          Related collections

          Author and article information

          Journal
          2015-12-21
          Article
          10.4230/LIPIcs.ICDT.2016.23
          1512.06635

          http://creativecommons.org/licenses/by/4.0/

          Custom metadata
          Full version of ICDT'16 paper
          cs.DB

          Databases

          Comments

          Comment on this article