Representationen av stora undergrupper av World Wide Web i form av en riktad graf har i stor utsträckning använts för att analysera struktur, beteende och utveckling av dessa så kallade webbgrafer. Intressanta webbgrafer är dock mycket stora och deras klassiska representationer passar inte in i huvudminnet hos typiska datorer, medan de nödvändiga grafalgoritmerna fungerar ineffektivt på sekundärminnet. Komprimerade graf representationer drastiskt minska sina rymdbehov samtidigt som deras effektiva navigering i komprimerad form. Även om den mest grundläggande navigeringen är att hämta efterträdare till en nod, flera viktiga Web graf algoritmer kräver stöd för utökade frågor, såsom att hitta föregångare till en nod, kontrollera förekomsten av en länk, eller hämta länkar mellan intervall av noder. Dessa stöds sällan av komprimerade graf representationer. Denna artikel presenterar k 2 - tree, en ny webb graf representation baserad på en kompakt träd struktur som drar nytta av stora tomma områden av adjacency matrisen av grafen. Representationen inte bara hämtar efterträdare och föregångare på symmetriskt sätt, men också det är särskilt effektivt att kontrollera om det finns specifika kopplingar mellan noder, eller mellan olika noder, eller att lista länkarna mellan intervall. Jämfört med de bästa representationerna i litteraturen som stöder efterföljare och föregångare frågor, erbjuder vår teknik minst utrymme användning (1-3 bitar per länk) samtidigt som den stöder snabb navigering till föregångare och efterträdare (2-8 mikrosekunder per granne hämtas) och kraftigt överträffar de andra på de utvidgade frågor. Representationen är också av allmänt intresse och kan användas för att komprimera andra typer av grafer och datastrukturer.
K 2-tree REF är en kompakt representation av glesa binära matriser som ursprungligen utformats för webbgrafer.
Compact Representation of Web Graphs with Extended Functionality ✩
{'venue': 'Inf. Syst.', 'journal': 'Inf. Syst.', 'mag_field_of_study': ['Computer Science']}