MPI-I-2008-5-001
STAR: Steiner tree approximation in relationship-graphs
Kasneci, Gjergji and Ramanath, Maya and Sozio, Mauro and Suchanek, Fabian M. and Weikum, Gerhard
June 2008, 37 pages.
.
Status: available - back from printing
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.
-
- Attachement: MPI-I-2008-5-001.pdf (497 KBytes)
URL to this document: https://domino.mpi-inf.mpg.de/internet/reports.nsf/NumberView/2008-5-001
BibTeX
@TECHREPORT{KasneciRamanathSozioSuchanekWeikum2008,
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},
}