I den verkliga världen är en graf ofta fragmenterad och fördelad på olika platser. Detta belyser behovet av att utvärdera frågor på distribuerade grafer. I detta dokument föreslås distribuerade utvärderingsalgoritmer för tre kategorier av frågor: nåbarhet för att avgöra om en nod kan nå en annan, begränsad räckvidd för att avgöra om det finns en väg av en avgränsad längd mellan ett par noder, och regelbunden räckvidd för att kontrollera om det finns en väg som förbinder två noder så att nodetiketterna på sökvägen bildar en sträng i ett givet reguljärt uttryck. Vi utvecklar dessa algoritmer baserat på partiell utvärdering, för att utforska parallell beräkning. Vid utvärdering av en fråga Q på en distribuerad graf G, visar vi att dessa algoritmer har följande prestandagarantier, oavsett hur G fragmenteras och distribueras: (1) varje webbplats besöks endast en gång; (2) den totala nätverkstrafiken bestäms av storleken på Q och fragmenteringen av G, oberoende av storleken på G; och (3) svarstiden bestäms av det största fragmentet av G snarare än hela G. Dessutom visar vi att dessa algoritmer kan enkelt genomföras i MapReduce ramverket. Med hjälp av syntetiska och verkliga data verifierar vi experimentellt att dessa algoritmer är skalbara på stora grafer, oavsett hur graferna distribueras.
Nyligen, Wenfei Fan et al. I REF föreslogs effektiva algoritmer för att besvara tre klasser av frågor om tillgänglighet på distribuerade grafer baserat på partiell utvärdering.
Performance Guarantees for Distributed Reachability Queries
{'venue': 'PVLDB', 'journal': 'PVLDB', 'mag_field_of_study': ['Computer Science']}