de.mpg.escidoc.pubman.appbase.FacesBean
Deutsch
 
Hilfe Wegweiser Impressum Kontakt Einloggen
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT

Freigegeben

Zeitschriftenartikel

High-performance Reachability Query Processing under Index Size Restrictions

MPG-Autoren
http://pubman.mpdl.mpg.de/cone/persons/resource/persons45462

Seufert,  Stephan
Databases and Information Systems, MPI for Informatics, Max Planck Society;
International Max Planck Research School, MPI for Informatics, Max Planck Society;

http://pubman.mpdl.mpg.de/cone/persons/resource/persons44012

Anand,  Avishek
Databases and Information Systems, MPI for Informatics, Max Planck Society;
International Max Planck Research School, MPI for Informatics, Max Planck Society;

http://pubman.mpdl.mpg.de/cone/persons/resource/persons44104

Bedathur,  Srikanta
Databases and Information Systems, MPI for Informatics, Max Planck Society;

http://pubman.mpdl.mpg.de/cone/persons/resource/persons45720

Weikum,  Gerhard
Databases and Information Systems, MPI for Informatics, Max Planck Society;

Externe Ressourcen
Es sind keine Externen Ressourcen verfügbar
Volltexte (frei zugänglich)
Es sind keine frei zugänglichen Volltexte verfügbar
Ergänzendes Material (frei zugänglich)
Es sind keine frei zugänglichen Ergänzenden Materialien verfügbar
Zitation

Seufert, S., Anand, A., Bedathur, S., & Weikum, G. (2012). High-performance Reachability Query Processing under Index Size Restrictions. arXiv, abs/1211.3375, 1-30. Retrieved from http://arxiv.org/abs/1211.3375.


Zitierlink: http://hdl.handle.net/11858/00-001M-0000-0014-59DC-7
Zusammenfassung
In this paper, we propose a scalable and highly efficient index structure for the reachability problem over graphs. We build on the well-known node interval labeling scheme where the set of vertices reachable from a particular node is compactly encoded as a collection of node identifier ranges. We impose an explicit bound on the size of the index and flexibly assign approximate reachability ranges to nodes of the graph such that the number of index probes to answer a query is minimized. The resulting tunable index structure generates a better range labeling if the space budget is increased, thus providing a direct control over the trade off between index size and the query processing performance. By using a fast recursive querying method in conjunction with our index structure, we show that web-scale graphs comprising hundreds of millions of nodes and billions of edges can be efficiently processed such that the resulting size-constrained index allows answering reachability queries in the order of a few microseconds, using an off-the-shelf computer. Our claims are supported by an extensive set of experimental results using a multitude of benchmark and real-world web-scale graph datasets.