Stor skala grafbehandling utgör en intressant utmaning på grund av bristen på lokalitet. Detta papper presenterar PathGraph för att förbättra iterativ graf beräkning på grafer med miljarder kanter. Vår systemdesign har tre unika funktioner: Först modellerar vi en stor graf med hjälp av en samling trädbaserade partitioner och använder en väg-centrerad beräkning snarare än vertex-centrisk eller kant-centrisk beräkning. Vår parallella beräkningsmodell förbättrar avsevärt minnet och diskplatsen för att utföra iterativa beräkningsalgoritmer. För det andra utformar vi en kompakt lagring som ytterligare maximerar sekventiell åtkomst och minimerar slumpmässig åtkomst på lagringsmedia. För det tredje implementerar vi den vägcentrerade beräkningsmodellen med hjälp av en spridnings-/samlarprogrammeringsmodell, som parallellerar den iterativa beräkningen på partitioneringsträdsnivå och utför sekventiella uppdateringar för hörn i varje partitionsträd. De experimentella resultaten visar att den path-centric approach överträffar vertexcentriska och edge-centriska system på ett antal grafalgoritmer för både in-memory och out-of-core grafer.
PathGraph REF föreslår en vägcentrerad modell för att förbättra minnet och diskåtkomsten.
Fast iterative graph computation: a path centric approach
{'venue': 'SC14: International Conference for High Performance Computing, Networking, Storage and Analysis', 'journal': 'SC14: International Conference for High Performance Computing, Networking, Storage and Analysis', 'mag_field_of_study': ['Computer Science']}