Kortaste sökvägar (SPQ) är viktiga i många grafanalyser och gruvuppgifter. Det är dock dyrt att besvara kortaste sökvägar på stora grafer. För att online svara på kortaste sökvägar, kan vi materialisera och index kortaste vägar. Men ett enkelt index av alla kortaste vägar i en graf av N hörn tar O(N 2 ) utrymme. I det här dokumentet tar vi itu med problemet med att indexera kortaste vägar och online besvara kortast möjliga frågor. Som många stora verkliga grafer visas rikt symmetriska, den centrala idén med vår strategi är att använda graf symmetri för att minska indexstorleken samtidigt behålla korrektheten och effektiviteten av kortaste sökväg svar. Tekniskt, Vi utvecklar ett ramverk för att indexera en stor graf på omloppsnivån i stället för vertex nivå så att antalet bredd-första sökträd materialized minskas från O(N ) till O( för)), där  och ≤ N är antalet banor i grafen. Vi utforskar bana adjacency och lokal symmetri för att få kompakt bredd-första-sök träd (kompact BFS-träd). En omfattande empirisk studie med hjälp av både syntetiska data och verkliga data visar att kompakta BFS-träd kan byggas effektivt och att rymdkostnaden kan minskas avsevärt. Dessutom, online kortaste sökväg svar kan uppnås med hjälp av kompakta BFS-träd.
Symmetri i verkliga nätverk används ytterligare för att effektivt indexera kortaste vägar i ett verkligt nätverk och besvara frågor på stora grafer REF.
Efficiently indexing shortest paths by exploiting symmetry in graphs
{'venue': "EDBT '09", 'journal': None, 'mag_field_of_study': ['Computer Science']}