Vi föreslår en ny exakt metod för kortast möjliga avståndsförfrågningar på storskaliga nätverk. Vår metod precomputes avstånd etiketter för hörn genom att utföra en bredd-första sökning från varje vertex. Verkar alltför uppenbart och för ineffektivt vid första anblicken, den viktigaste ingrediensen som införs här är beskärning under bredd-första sökningar. Även om vi fortfarande kan svara på rätt avstånd för ett par hörn från etiketterna, minskar det överraskande sökytan och storleken på etiketter. Dessutom visar vi att vi kan utföra 32 eller 64 bredd-första sökningar samtidigt utnyttja bitvis verksamhet. Vi visar experimentellt att kombinationen av dessa två tekniker är effektiv och robust på olika typer av storskaliga verkliga nätverk. I synnerhet kan vår metod hantera sociala nätverk och webbgrafer med hundratals miljoner kanter, som är två storleksordningar större än gränserna för tidigare exakta metoder, med jämförbar frågetid jämfört med tidigare metoder.
Mycket nyligen föreslog Akiba et al. att pre-kompilera 2-hop avstånd etiketter för hörn genom att utföra en bredd-första sökning från varje vertex.
Fast exact shortest-path distance queries on large networks by pruned landmark labeling
{'venue': "SIGMOD '13", 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}