Abstract-Ett ökande antal tillämpningar inom fysik och samhällsvetenskap kräver analys av stora grafer. Effektiviteten av dessa program beror starkt på deras minnesanvändning, särskilt lokaliseringen av grafdataåtkomst. Intuitivt bör lokaliseringen i beräkningen återspegla lokaliseringen i graftopologin. Befintliga lokala modeller fungerar dock antingen på programnivå för regelbundna slingor och matriser eller på spårnivå för godtyckliga åtkomstströmmar. De är inte tillräckliga för att karakterisera förhållandet mellan lokalitet och konnektivitet. Detta papper presenterar ett nytt mått som kallas vertex avstånd och använder det för att modellera lokaliteten i bredd-första graf traversal (BFS). Den visar tre modeller som använder den genomsnittliga nodgraden och kanten fördelning för att förutsäga antalet BFS-nivåer och återanvändning avstånd distribution av BFS. Slutligen utvärderas de nya modellerna med hjälp av slumpmässiga och icke-slumpmässiga grafer.
Analytiska modeller för BFS kan exakt förutsäga återanvändningsavståndet för BFS på vissa slumpmässiga grafer REF.
Modeling the Locality in Graph Traversals
{'venue': '2012 41st International Conference on Parallel Processing', 'journal': '2012 41st International Conference on Parallel Processing', 'mag_field_of_study': ['Computer Science']}