In this paper, we investigate the effects of violating the conditions of hash function uniformity and/or independence on the false positive probability of Bloom Filters (BF). To this end, we focus on hash functions of the H3 family with a partitioned memory organization for fast hardware implementations of BFs. We first introduce a dependence metric that quantifies hash function uniformity and independence. We then state and prove the necessary and sufficient conditions on the BF parameters for constructing uniform and independent hash functions. Finally, we derive an analytical expression for the exact false positive probability of a BF with hash functions that are not necessarily uniform or independent. We verify our expression with a hardware test bench and explore the effects of losing uniformity and independence through an experimental study that systematically sweeps different dependence metric values and numbers of hash functions. We demonstrate the effects of violating hash function uniformity and independence on the stated target false positive probability for selected previous works in the literature. As an important finding, we show that uniformity of individual hash functions is essential, whereas limited dependencies between hash functions can be tolerated without a negative effect on the false positive probability.

Cloud data center workloads have time- dependencies and are hence non-i.i.d (independent and identically distributed). In this paper, we propose a new model-based method for creating synthetic workload traces for cloud data centers that have similar time characteristics and cumulative distributions to those of the actual traces. We evaluate our method using the actual resource request traces of Azure collected in 2019 and the well-known Google cloud trace. Our method enables generating synthetic traces that can be used for a more realistic evaluation of cloud data centers.