Massiva dataströmmar är nu grundläggande för många databehandlingstillämpningar. Internetroutrar producerar till exempel storskaliga diagnostiska dataströmmar. Sådana strömmar lagras sällan i traditionella databaser och måste istället bearbetas "i farten" som de produceras. På samma sätt producerar sensornätverk flera dataströmmar av observationer från sina sensorer. Det finns ett växande fokus på att manipulera dataströmmar, och därför finns det ett behov av att identifiera grundläggande verksamheter av intresse för att hantera dataströmmar, och att stödja dem effektivt. Vi föreslår beräkning av hammingnormen som en grundläggande verksamhet av intresse. Hamming-normen formaliserar idéer som används under hela databehandlingen. När den appliceras på en enda ström, ger hamming normen antalet distinkta objekt som finns i den dataströmmen, vilket är en statistik av stort intresse för databaser. När den appliceras på ett par strömmar, ger hamming normen ett viktigt mått på (olika) likhet: antalet ojämlika objekt räknas i de två strömmarna. Hammingnormer har många användningsområden för att jämföra dataströmmar. Vi presenterar en ny approximationsteknik för att uppskatta hammingnormen för massiva dataströmmar; detta bygger på vad vi kallar "l 0 skissen" och vi bevisar dess riktighet. Vi testar vår approximationsmetod på en stor mängd syntetiska och verkliga stream data, och visar att uppskattningen är korrekt till inom några procentenheter.
Ämnet effektiv likhetsutförande mellan strömmar, har också varit av intresse för forskarsamhället; Cormode et al. I Ref studera användningen av likhetsåtgärder för jämförelse av vattendrag och fokusera på skisserade approximationer av hammingnormen.
Comparing Data Streams Using Hamming Norms (How to Zero In)
{'venue': 'VLDB', 'journal': None, 'mag_field_of_study': ['Computer Science']}