Abstrakt. Dataflödesbehandling har nyligen fått ökad uppmärksamhet som ett beräkningsparadigm för hantering av massiva datamängder. Förvånansvärt nog är ingen algoritm med både sublinjärt utrymme och passager känd för naturliga grafproblem i klassisk lässkyddad streaming. Motiverad av tekniska faktorer i moderna lagringssystem har en del författare nyligen börjat undersöka beräkningskraften hos mindre restriktiva modeller där skrivströmmar är tillåtna. I den här artikeln, visar vi att användningen av mellanliggande tillfälliga strömmar är tillräckligt kraftfull för att ge effektiva rymdpass kompromisser för naturliga graf problem. I synnerhet, för varje utrymme begränsning av s bitar, visar vi att en källa kortaste vägar i riktade grafer med små positiva heltal egg vikter kan lösas i O (n log 3/2 n) / Ă s) passerar. Resultatet kan generaliseras för att hantera flera källor inom samma gränser. Detta är den första kända streaming algoritm för kortaste vägar i riktade grafer. För oriktad anslutning, vi utforma en O (n log n) / s) passerar algoritm. Båda problemen kräver (n/s) passerar under de begränsningar vi anser. Vi visar också att modellen där mellanliggande temporära strömmar tillåts kan vara strikt mer kraftfull än klassisk streaming för vissa problem, samtidigt som alla dess hårdhet för andra.
REF visar kompromisser mellan mellanslag för kortaste stigproblem i grafströmmar.
Trading off space for passes in graph streaming problems
{'venue': 'TALG', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}