Show simple item record

2006-01-01Buch DOI: 10.18452/2469
GRIPP
dc.contributor.authorTrißl, Silke
dc.contributor.authorLeser, Ulf
dc.date.accessioned2017-06-15T17:11:28Z
dc.date.available2017-06-15T17:11:28Z
dc.date.created2006-12-07
dc.date.issued2006-01-01
dc.identifier.issn0863-095X
dc.identifier.urihttp://edoc.hu-berlin.de/18452/3121
dc.description.abstractMany applications require querying graph-structured data. As graphs grow in size, indexing becomes essential to ensure sufficient query performance. We present the GRIPP index structure (GRaph Indexing based on Pre- and Postorder numbering) for answering reachability and distance queries in graphs. GRIPP requires only linear space and can be computed very efficiently. Using GRIPP, we can answer reachability queries on graphs with 5,000,000 nodes on average in less than 5 milliseconds, which is unrivaled by previous methods. We can also answer distance queries on large graphs more efficiently using the GRIPP index strucutre. We evaluate the performance and scalability of our approach on real, random, and scale-free networks using an implementation of GRIPP inside a relational database management system. Thus, GRIPP can be integrated very easily into existing graph-oriented applications.eng
dc.language.isoeng
dc.publisherHumboldt-Universität zu Berlin, Mathematisch-Naturwissenschaftliche Fakultät II, Institut für Informatik
dc.rights.urihttp://rightsstatements.org/vocab/InC/1.0/
dc.subject.ddc004 Informatik
dc.titleGRIPP
dc.typebook
dc.identifier.urnurn:nbn:de:kobv:11-10071473
dc.identifier.doihttp://dx.doi.org/10.18452/2469
dc.subject.dnb28 Informatik, Datenverarbeitung
local.edoc.pages55
local.edoc.type-nameBuch
local.edoc.container-typeseries
local.edoc.container-type-nameSchriftenreihe
local.edoc.container-year2006
dc.title.subtitleIndexing and Querying Graphs based on Pre- and Postorder Numbering
dc.identifier.zdb2942054-4
bua.series.nameInformatik-Berichte
bua.series.issuenumber2006,207

Show simple item record