Vi studerar problemet med att uppskatta antalet trianglar i en grafström. Ingen strömmande algoritm kan få sublinjärt utrymme på alla grafer, så metoder i detta område avgränsade utrymmet i termer av parametrar för inmatningsgrafen såsom det maximala antalet trianglar som delar en enda kant. Vi ger en provtagningsalgoritm som dessutom parameteriseras av det maximala antalet trianglar som delar en enda vertex. Våra bundna matchar de mest kända turstile resultaten i alla grafer, och får bättre prestanda på enkla grafer som G(n, p) eller en uppsättning oberoende trianglar. Vi kompletterar den övre gränsen med en nedre gräns som visar att ingen provtagningsalgoritm kan göra bättre på dessa grafer med mer än en loggfaktor. I synnerhet, varje insättning ström algoritm måste använda ε T utrymme när alla trianglar delar en gemensam vertex, och varje provtagning algoritm måste ta T 1/3 prover när alla trianglar är oberoende. Vi lägger till ytterligare en lägre gräns, som också matchar vår algoritms prestanda, vilket gäller för alla grafklasser. Denna lägre gräns täcker "triangelberoende" samplingsalgoritmer, en underklass som inkluderar vår algoritm och alla tidigare samplingsalgoritmer för problemet. Slutligen visar vi hur vi generaliserar vår algoritm för att räkna godtyckliga subgrafer av konstant storlek.
Specifikt visar REF en lägre gräns på utrymmet komplexiteten av att approximera antalet trianglar i den strömmande modellen; vi tillämpar deras minskning här för att visa hårdheten av att testa triangelfrihet, genom att minska från en annan variant av problemet de använder.
Improved graph sampling for triangle counting
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}