Hamming Filter: A Dynamic Signature File Organization for Parallel Stores

摘要

Partitioning, in general, has become the basic strategy for organizing data files to avoid an exhaustive search when executing queries. However, hardware limitations that constrain the performance of query execution mainly become a problem for partial-match queries, where the size of the result can equal the size of the data file. In such situations, a proper application of parallelism can bring the required breakthrough in performance. Hamming Filter is a parallel, partitioned organization of signature files that are stored in fixed size buckets with a guaranteed load and is based on the idea of linear code decomposition. It can efficiently manage dynamic data files by means of a partitioned structure that always grows and shrinks linearly and is appropriate to multidimensional partitioning and searching. This paper proves that the organization yields no expected execution skew for partial-match queries, provided the data is not skewed and the degree of parallelism is a power of two.