Vi studerar problemet med att uppskatta värdet av summor av formen S p x i p när man har förmågan att prov x i ≥ 0 med sannolikhet proportionell mot dess storlek. När p = 2, detta problem är likvärdigt med att uppskatta selektiviteten av en själv-join fråga i databassystem när man kan ta prover rader slumpmässigt. Vi studerar också specialfallet när {x i} är gradsekvensen av en graf, vilket motsvarar att räkna antalet p-stjärnor i en graf när man har möjlighet att prova kanter slumpmässigt. Vår algoritm för en (1 ± ε)-multiplikativ approximation av S p har fråge- och tidskomplexitet O m log log n 2 S nästan alla fall, även när {x i } är en examen sekvens och man får använda strukturen i grafen för att försöka få en bättre uppskattning. Vi känner inte till några tidigare lägre gränser för problemet med att förena selektivitetsberäkning. För grafproblemet, tidigare arbete som antog förmågan att ta prov endast hörn enhetligt gav algoritmer med matchande nedre gränser (Gonen et al. I SIAM J Comput 25:1365-1411. Med förmågan att prov kanter slumpmässigt, visar vi att man kan uppnå snabbare algoritmer för att approximera antalet star subgraphs, förbi de nedre gränserna i detta föregående arbete. Till exempel, i den regim där S p ≤ n, och p = 2, vår övre gräns är Õ(n/S 1/2 p ), i motsats till deras (n/S 1/3 p ) nedre gräns när inga slumpmässiga kantfrågor är tillgängliga. Dessutom överväger vi problemet med att räkna antalet riktade vägar av längd två när grafen är riktad. Detta problem är detsamma som att uppskatta selektiviteten hos en kopplingsfråga mellan två olika tabeller. Vi bevisar att den allmänna versionen av detta problem inte kan lösas på sublinjär tid. När förhållandet mellan in-grad och utgrad begränsas-eller motsvarande, när förhållandet mellan antalet förekomster av värden i de två kolumner som sammanfogas avgränsas-vi ger en sublinjär tidsalgoritm via en minskning till det oriktade fallet.
Nyligen, Aliakbarpour et al. Ref använde slumpmässig kantprovtagning för att uppskatta antalet stjärnor i en graf.
Sublinear-Time Algorithms for Counting Star Subgraphs via Edge Sampling
{'venue': 'Algorithmica', 'journal': 'Algorithmica', 'mag_field_of_study': ['Mathematics', 'Computer Science']}