Cold storage access filters are an important part of Main Memory Database Systems. Bloom filters are commonly used and very effective for filtering point queries, but relatively inefficient for range queries. Adaptive Range Filters (ARFs) were specifically designed to test if no key of a given range is contained in a set of keys, just like Bloom filters test whether a single key is not in a set of keys. This thesis gives an overview of the concepts and algorithms that are used to make ARFs work efficiently and correctly as a filter for cold data. Furthermore, this thesis discusses and compares several different implementation methods. Lastly, it presents the results of several experiments conducted to evaluate the influence of a variety of factors on an ARF’s performance and compare different variants of ARFs.
«
Cold storage access filters are an important part of Main Memory Database Systems. Bloom filters are commonly used and very effective for filtering point queries, but relatively inefficient for range queries. Adaptive Range Filters (ARFs) were specifically designed to test if no key of a given range is contained in a set of keys, just like Bloom filters test whether a single key is not in a set of keys. This thesis gives an overview of the concepts and algorithms that are used to make ARFs work...
»
übersetzter Abstract:
Filterstrukturen für den Zugriff auf kalte Daten sind ein wichtiger Bestandteil eines Hauptspeicherdatenbanksystems. Bloomfilter sind weitverbreitet und sehr effektiv für das filtern von Punktanfragen, aber relativ ineffizient für Bereichsanfragen. Adaptive Range Filters (ARFs) wurden entworfen, um überprüfen zu können, ob kein einziger Schlüssel aus einem gegebenen Bereich in einer gegebenen Menge an Schlüsseln enthalten ist, so wie Bloomfilter prüfen ob ein einzelner Schlüssel nicht in einer Menge enthalten ist. Diese Arbeit gibt einen Überblick über Konzepte und Algorithmen die verwendet werden um ARFs effizient und korrekt als Filter für kalte Daten zu implementieren. Des Weiteren werden verschiedene Methoden der Implementierung beschrieben und verglichen. Zuletzt werden die Ergebnisse mehrerer Experimente präsentiert, die durchgeführt wurden um den Einfluss verschiedener Faktoren auf die Leistung eines ARF zu evaluieren und verschiedene ARF Varianten zu vergleichen.
«
Filterstrukturen für den Zugriff auf kalte Daten sind ein wichtiger Bestandteil eines Hauptspeicherdatenbanksystems. Bloomfilter sind weitverbreitet und sehr effektiv für das filtern von Punktanfragen, aber relativ ineffizient für Bereichsanfragen. Adaptive Range Filters (ARFs) wurden entworfen, um überprüfen zu können, ob kein einziger Schlüssel aus einem gegebenen Bereich in einer gegebenen Menge an Schlüsseln enthalten ist, so wie Bloomfilter prüfen ob ein einzelner Schlüssel nicht in einer M...
»
Stichworte:
Data processing, Database management systems, Data filtering