Logo der Humboldt-Universität zu BerlinLogo der Humboldt-Universität zu Berlin
edoc-Server
Open-Access-Publikationsserver der Humboldt-Universität
de|en
Banner: Fassade der Humboldt-Universität zu Berlin
Publikation anzeigen 
  • edoc-Server Startseite
  • Schriftenreihen und Sammelbände
  • Fakultäten und Institute der HU
  • Institut für Informatik
  • Informatik-Berichte
  • Publikation anzeigen
  • edoc-Server Startseite
  • Schriftenreihen und Sammelbände
  • Fakultäten und Institute der HU
  • Institut für Informatik
  • Informatik-Berichte
  • Publikation anzeigen
JavaScript is disabled for your browser. Some features of this site may not work without it.
Gesamter edoc-ServerBereiche & SammlungenTitelAutorSchlagwortDiese SammlungTitelAutorSchlagwort
PublizierenEinloggenRegistrierenHilfe
StatistikNutzungsstatistik
Gesamter edoc-ServerBereiche & SammlungenTitelAutorSchlagwortDiese SammlungTitelAutorSchlagwort
PublizierenEinloggenRegistrierenHilfe
StatistikNutzungsstatistik
Publikation anzeigen 
  • edoc-Server Startseite
  • Schriftenreihen und Sammelbände
  • Fakultäten und Institute der HU
  • Institut für Informatik
  • Informatik-Berichte
  • Publikation anzeigen
  • edoc-Server Startseite
  • Schriftenreihen und Sammelbände
  • Fakultäten und Institute der HU
  • Institut für Informatik
  • Informatik-Berichte
  • Publikation anzeigen
2006-01-01Buch DOI: 10.18452/2469
GRIPP
Indexing and Querying Graphs based on Pre- and Postorder Numbering
Trißl, Silke
Leser, Ulf
Many 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.
Dateien zu dieser Publikation
Thumbnail
207.pdf — PDF — 643.9 Kb
MD5: 9d7f07b15e0544c9ac2446f0a6bbb146
Referenzen
Is Part Of Series: Informatik-Berichte - 207, ISSN:0863-095X
Zitieren
BibTeX
EndNote
RIS
Keine Lizenzangabe
Zur Langanzeige
ImpressumLeitlinienKontakt
Ein Service der Universitätsbibliothek und des Computer- und Medienservice
© Humboldt-Universität zu Berlin
 
DOI
10.18452/2469
Permanent URL
http://dx.doi.org/10.18452/2469
HTML
<a href="http://dx.doi.org/10.18452/2469">http://dx.doi.org/10.18452/2469</a>