Vi presenterar utrymmeseffektiva dataströmsalgoritmer för att approximera antalet trianglar i en graf upp till en faktor 1 +. Även om det kan visas att bestämma om en graf är triangelfri är inte möjligt i sub-linjärt utrymme, har en stor mängd arbete fokuserat på att minimera det utrymme som krävs i termer av antalet trianglar T (eller en lägre gräns på denna mängd) och andra parametrar inklusive antalet noder n och antalet kanter m. Två modeller är viktiga i litteraturen: den godtyckliga ordning modell där strömmen består av kanterna på grafen i godtycklig ordning och adjacency lista ordning modell där alla kanter incident till samma nod visas i följd. Vi förbättrar över toppmoderna resultat i båda modellerna. För adjacencylistans ordermodell visar vi att Õ( −2 m/ ε T ) utrymme är tillräckligt i ett pass och O( −2 m 3/2 /T ) utrymme är tillräckligt i två pass där Õ(·) notation undertrycker loggfaktorer. För den godtyckliga ordermodellen visar vi att Õ( −2 m/ ε T ) utrymme räcker med två pass och att O( −2 m 3/2 /T ) utrymme räcker med tre pass och orakle tillgång till graderna. Slutligen visar vi hur man effektivt kan genomföra "wedge sampling" metoden för triangeluppskattning i den godtyckliga ordermodellen. För att göra detta utvecklar vi den första algoritmen för p provtagning så att flera oberoende prover kan genereras med O(polylog n) uppdateringstid; denna primitiva är allmänt tillämplig och detta resultat kan vara av oberoende intresse.
McGregor m.fl. REF gav ett-pass O(m/ ❌ T )utrymme och två pass O(m 3/2 /T )-utrymme algoritm för triangelräkning problem i denna modell.
Better Algorithms for Counting Triangles in Data Streams
{'venue': "PODS '16", 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}