Problemet med konnektivitet är oerhört viktigt i samband med massiva grafer. I många stora kommunikationsnät, sociala nätverk och andra grafer är det önskvärt att bestämma det minsta snittet mellan varje par av noder. Problemet är väl löst i den klassiska litteraturen, eftersom det är relaterat till det maximala flödet problem, som effektivt kan lösas. Stora grafer kan dock ofta ha diskplats, och sådana grafer kan inte behandlas effektivt för anslutningsfrågor. Detta beror på att det minsta skär problemet är typiskt löst med användning av en mängd olika kombinatoriska och flödesbaserade tekniker som kräver slumpmässig tillgång till de underliggande kanterna i grafen. I detta dokument föreslår vi att man utvecklar ett konnektivitetsindex för grafer med massiv-disk hemvist. Vi kommer att använda en kantampling baserad strategi för att skapa komprimerade representationer av de underliggande graferna. Eftersom dessa komprimerade representationer kan hållas i huvudminnet, kan de användas för att härleda effektiva approximationer för det minsta skär problemet. Dessa komprimerade representationer är sedan organiserade i en disk-bostad indexstruktur. Vi presenterar experimentella resultat som visar att den resulterande metoden ger mellan två och tre storleksordningar effektivare frågebehandling än en disk-bofast metod på bekostnad av en liten mängd noggrannhet.
Aggarwal m.fl. I REF föreslås ett tillvägagångssätt för att erhålla minimiskär på provade kanter med hjälp av ett konnektivitetsindex.
GConnect: A Connectivity Index for Massive Disk-resident Graphs
{'venue': 'PVLDB', 'journal': 'PVLDB', 'mag_field_of_study': ['Computer Science']}