Detta papper undersöker två typer av graf frågor: enkel källavstånd (SSD) frågor och en källa kortaste vägen (SSSP) frågor. Eftersom en nod v i en graf G, en SSD fråga från v ber om avståndet från v till någon annan nod i G, medan en SSSP fråga hämtar den kortaste vägen från v till någon annan nod. Dessa två typer av frågor finner viktiga tillämpningar i grafanalys, särskilt vid beräkning av grafmått. De flesta av de befintliga lösningarna för SSD- och SSSP-frågor kräver dock att inmatningsgrafen passar in i huvudminnet, vilket gör dem otillämpliga för de massiva disk-existerande grafer som vanligen används i webb- och sociala applikationer. Det finns flera tekniker som är utformade för att vara I/O-effektiva, men de fokuserar alla på oriktade och/eller oviktade grafer, och de erbjuder endast suboptimal frågeeffektivitet. För att åtgärda bristen på befintligt arbete presenterar detta dokument Highways-on-Disk (HoD), ett diskbaserat index som stöder både SSD- och SSSP-frågor på riktade och viktade grafer. Den viktigaste idén med HoD är att öka indatagrafen med en uppsättning extra kanter, och utnyttja dem under frågebehandling för att minska I/O och beräkningskostnader. Vi utvärderar HoD experimentellt på både riktade och oriktade verkliga grafer med upp till miljarder noder och kanter, och vi visar att HoD avsevärt överträffar alternativa lösningar när det gäller frågeeffektivitet.
Highways-on-Disk (HoD) föreslås också i REF för att stödja SSSP distansfrågor för riktade grafer.
Efficient single-source shortest path and distance queries on large graphs
{'venue': "KDD '13", 'journal': None, 'mag_field_of_study': ['Computer Science']}