Abstract-Core nedbrytning är ett grundläggande graf problem med ett stort antal tillämpningar. De flesta befintliga metoder för core nedbrytning antar att grafen hålls till minne av en maskin. Ändå är många verkliga grafer stora och kanske inte finns i minnet. I litteraturen finns det bara ett verk för I/O effektiv kärndekomposition som undviker att ladda hela grafen i minnet. Detta tillvägagångssätt är dock inte skalbart för att hantera stora grafer eftersom det inte kan begränsa minnesstorleken och kan ladda de flesta delar av grafen i minnet. Dessutom kan detta tillvägagångssätt knappast hantera grafuppdateringar. I detta dokument studerar vi I/O-effektiv kärndekomposition efter en semiextern modell, som endast gör det möjligt att ladda nodinformation i minnet. Denna modell fungerar bra i många webbscale grafer. Vi föreslår en semiextern algoritm och två optimerade algoritmer för I/O effektiv kärnnedbrytning med hjälp av mycket enkla strukturer och dataåtkomstmodell. För att hantera dynamiska grafuppdateringar visar vi att vår algoritm naturligt kan utökas för att hantera kantradering. Vi föreslår också en I/O-effektiv kärnunderhållsalgoritm för att hantera kantinsättning och en förbättrad algoritm för att ytterligare minska I/O- och CPU-kostnader genom att undersöka några nya grafegenskaper. Vi utför omfattande experiment på 12 riktigt stora grafer. Vår optimala algoritm överträffar avsevärt den befintliga I/O-effektiva algoritmen både vad gäller bearbetningstid och minnesförbrukning. I många minnesbaserade grafer kan våra algoritmer för både kärndekomposition och underhåll överträffa den in-minnesalgoritm som används på grund av de enkla strukturer och dataåtkomstmodell som används. Våra algoritmer är mycket skalbara för att hantera grafer i webbskala. Som exempel är vi de första att hantera en webbgraf med 978,5 miljoner noder och 42,6 miljarder kanter med mindre än 4,2 GB minne.
I/O-effektiva algoritmer REF föreslogs för kärnnedbrytning på grafer som inte får plats i huvudminnet.
I/O efficient Core Graph Decomposition at web scale
{'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']}