Max-Planck-Institut für Informatik
max planck institut
mpii logo Minerva of the Max Planck Society


STAR: Steiner tree approximation in relationship-graphs

Kasneci, Gjergji and Ramanath, Maya and Sozio, Mauro and Suchanek, Fabian M. and Weikum, Gerhard

MPI-I-2008-5-001. June 2008, 37 pages. | Status: available - back from printing | Next --> Entry | Previous <-- Entry

Abstract in LaTeX format:
Large-scale graphs and networks are abundant in modern information systems:
entity-relationship graphs over relational data or Web-extracted entities,
biological networks, social online communities, knowledge bases, and
many more. Often such data comes with expressive node and edge labels that
allow an interpretation as a semantic graph, and edge weights that reflect
the strengths of semantic relations between entities. Finding close
relationships between a given set of two, three, or more entities is an
important building block for many search, ranking, and analysis tasks.
From an algorithmic point of view, this translates into computing the best
Steiner trees between the given nodes, a classical NP-hard problem. In
this paper, we present a new approximation algorithm, coined STAR, for
relationship queries over large graphs that do not fit into memory. We
prove that for n query entities, STAR yields an O(log(n))-approximation of
the optimal Steiner tree, and show that in practical cases the results
returned by STAR are qualitatively better than the results returned by a
classical 2-approximation algorithm. We then describe an extension to our
algorithm to return the top-k Steiner trees. Finally, we evaluate our
algorithm over both main-memory as well as completely disk-resident graphs
containing millions of nodes. Our experiments show that STAR outperforms
the best state-of-the returns qualitatively better results.
References to related material:

To download this research report, please select the type of document that fits best your needs.Attachement Size(s):
MPI-I-2008-5-001.pdf497 KBytes
Please note: If you don't have a viewer for PostScript on your platform, try to install GhostScript and GhostView
URL to this document:
Hide details for BibTeXBibTeX
  AUTHOR = {Kasneci, Gjergji and Ramanath, Maya and Sozio, Mauro and Suchanek, Fabian M. and Weikum, Gerhard},
  TITLE = {{STAR}: Steiner tree approximation in relationship-graphs},
  TYPE = {Research Report},
  INSTITUTION = {Max-Planck-Institut f{\"u}r Informatik},
  ADDRESS = {Stuhlsatzenhausweg 85, 66123 Saarbr{\"u}cken, Germany},
  NUMBER = {MPI-I-2008-5-001},
  MONTH = {June},
  YEAR = {2008},
  ISSN = {0946-011X},