Latency-Optimal Walks in Replicated and Partitioned Graphs

Autor:	Maik Jorra, Stefan Plantikow
Rok vydání:	2011
Předmět:	Graph database Theoretical computer science Computer science Replica Speculative execution Latency (engineering) Centrality computer.software_genre computer Graph product Graph
Zdroj:	Database Systems for Adanced Applications ISBN: 9783642202438 DASFAA Workshops
DOI:	10.1007/978-3-642-20244-5_3
Popis:	Executing walks in partitioned, distributed graphs with minimal latency requires reducing the number of network hops taken. This is especially important for graph databases that specialize on executing fast graph traversals. We present fast-forward-search, an algorithm that uses overlapping graph partitionings, i.e. replication, and parallel speculative execution to minimize the number of required network hops. We proof optimality of the algorithm, analyze storage, message, and computational overhead caused by the parallelism of fast-forward, and introduce escapicity, a metric for replica selection that helps reducing that parallelism at the price of lost optimality. Experiments for a set of smaller graphs indicate that fast-forward-search saves between 20-90% of network hops depending on graph and replication factor and that escapicity outperforms classic measures of network centrality as a metric for replica selection in our scheme.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::8152705c56af52647542a9f6878a74a4 https://doi.org/10.1007/978-3-642-20244-5_3 Zobrazit plný text záznamu