Nya studier visar att grafbearbetningssystem på en enda maskin kan uppnå konkurrenskraftig prestanda jämfört med klusterbaserade grafbearbetningssystem. I detta papper presenterar vi NXgraph, ett effektivt grafbehandlingssystem på en enda maskin. Vi föreslår strukturen Destination-Sorted Sub-Shard (DSSS) för att lagra en graf. För att se till att grafdata kommer åt plats och möjliggöra finkornig schemaläggning delar NXgraph in hörn och kanter i intervall och delskärvor. För att minska skriva konflikter mellan olika trådar och uppnå en hög grad av parallellism, NXgraph sorterar kanter inom varje sub-hård enligt deras destination hörn. Därefter, tre uppdateringsstrategier, dvs., Single-Phase Update (SPU), Double-Phase Update (DPU) och Mixed-Phase Update (MPU), föreslås i detta dokument. NXgraph kan adaptivt välja den snabbaste strategin för olika grafproblem beroende på grafstorlek och tillgängliga minnesresurser för att fullt ut utnyttja minnesutrymmet och minska mängden dataöverföring. Alla dessa tre strategier utnyttjar strömlinjeformade diskåtkomstmönster. Omfattande experiment på tre verkliga grafer och fem syntetiska grafer visar att NXgraph överträffar GraphChi, TurboGraph, VENUS och GridGraph i olika situationer. Dessutom kan NXgraph, som körs på en enda produkt PC, avsluta en iteration av PageRank på Twitter [1] grafen med 1,5 miljarder kanter på 2,05 sekunder; medan PowerGraph, en distribuerad graf bearbetningssystem, behöver 3.6 för att avsluta samma uppgift på en 64-node kluster.
NXgraph REF föreslår strukturen Destination-Sorted Sub-Shard (DSSS) för att lagra grafen med tre uppdateringsstrategier: SPU, DPU och MPU.
NXgraph: An efficient graph processing system on a single machine
{'venue': '2016 IEEE 32nd International Conference on Data Engineering (ICDE)', 'journal': '2016 IEEE 32nd International Conference on Data Engineering (ICDE)', 'mag_field_of_study': ['Computer Science']}