Key points are not available for this paper at this time.
Die Beseitigung von Redundanz in den Daten ist ein wichtiges Problem, da sie die Ressourcen- und Recheneffizienz für die nachgelagerte Verarbeitung massiver Datensätze (10 Millionen bis 100 Millionen Datensätze) verbessert. In Anwendungsbereichen wie IR, Aktienmärkten, Telekommunikation und anderen gibt es einen großen Bedarf an der Echtzeitentfernung von Datenredundanz aus enormen Datenmengen, die mit einer Rate von 1Gb/s oder höher fließen. Wir betrachten das Problem, Reichweiten-Motive (Cluster) über Datensätze in einem großen Datensatz zu finden, sodass Datensätze innerhalb desselben Clusters ungefähr nahe beieinander liegen. Dieses Problem ist eng mit der Suche nach approximativen nächstgelegenen Nachbarn verbunden, ist jedoch rechnerisch aufwendiger. Die skalierbare Echtzeiterkennung approximativer Reichweiten-Motive auf massiven Datensätzen ist ein herausforderndes Problem. Wir präsentieren das Design neuartiger sequenzieller und paralleler Algorithmen zur Entdeckung approximativer Reichweiten-Motive und zur Daten-Deduplizierung unter Verwendung von Bloom-Filtern. Wir legen asymptotische obere Schranken für die Falsch-Positiv- und Falsch-Negativ-Raten unseres Algorithmus fest. Darüber hinaus wird eine Zeitkomplexitätsanalyse unseres parallelen Algorithmus auf Multi-Core-Architekturen präsentiert. Für 10 Millionen Datensätze kann unser paralleler Algorithmus die Entdeckung approximativer Reichweiten-Motive und die Daten-Deduplizierung auf 4 Mengen (Clustern) in 59 Sekunden auf einer 16-Core-Intel-Xeon-5570-Architektur durchführen. Dies ergibt eine Durchsatzrate von etwa 170K Datensätzen/s und etwa 700Mb/s (unter Verwendung von Datensätzen mit einer Größe von 4K Bits). Soweit wir wissen, ist dies der höchste Echtzeit-Durchsatz für die Entdeckung approximativer Reichweiten-Motive und die Entfernung von Datenredundanz bei solch massiven Datensätzen.
Narang et al. (Mon.) haben diese Frage untersucht.