De senaste åren har bevittnat ett ökande intresse för att utforma algoritmer för att fråga och analysera strömmande data (dvs. data som endast ses en gång i en fast ordning) med endast begränsat minne. Att ge (kanske ungefärliga) svar på frågor över sådana kontinuerliga dataströmmar är ett avgörande krav för många applikationsmiljöer; exempel inkluderar stora telekom- och IP-nätverksinstallationer där prestandadata från olika delar av nätverket måste samlas in och analyseras kontinuerligt. Randomiserade tekniker, baserade på att beräkna små "sketch" synops för varje ström, har nyligen visat sig vara ett mycket effektivt verktyg för att approximera resultatet av en enda SQL fråga över strömmande data tuples. I detta dokument undersöker vi de problem som uppstår när data-stream skisser används för att behandla flera sådana frågor samtidigt. Vi visar att i närvaro av flera frågeuttryck kan intelligent dela skisser mellan samtidiga frågeutvärderingar resultera i betydande förbättringar i utnyttjandet av det tillgängliga skissutrymmet och kvaliteten på de resulterande approximativa felgarantierna. Vi tillhandahåller nödvändiga och tillräckliga villkor för multiquery skissdelning som garanterar att resultatet-skattningsprocessen är korrekt. Vi undersöker också det svåra optimeringsproblemet med att bestämma skiss-delning konfigurationer som är optimala (t.ex. under ett visst fel metriska för en given mängd utrymme). Vi visar att optimal skissdelning vanligtvis ger upphov till N P-hårda frågor, och vi föreslår nya heuristiska algoritmer för att hitta bra skissdelningskonfigurationer i praktiken. Resultat från vår experimentella studie med frågor från TPC-H-riktmärket verifierar effektiviteten i vår strategi, vilket tydligt visar fördelarna med vår skissdelningsmetod.
Referensreferensreferensreferensen tar nyligen upp problemet med att dela skisser för ungefärlig gemensam behandling.
Sketch-based multi-query processing over data streams
{'venue': 'In EDBT', 'journal': None, 'mag_field_of_study': ['Computer Science']}