## 2 Pms6
### The Data Structure \(Q\)  
We now describe the data structure \(Q\) that is used by PMS6. This is a reasonably simple data structure that has efficient mechanisms for storing and intersection. In the PMS6 implementation of [23], there are three arrays in \(Q\); a character array, \(strs[]\), for storing all \(l\)-mers, an array of pointers, \(bucketPoints[]\),which points to locations in the character array and a bit array, \(markBuffer[]\), used for intersection. There is also a parameter \(bucketIndex\) which determines how many characters of \(l\)-mers are used for indexing into \(bucketPoints[]\) array. As there are 4 possibilities for a character, for \(p\) characters \(bucketIndex\) can vary from \(0\) to (\(4^{p}-1\)). The number of characters, \(p\), to be used for indexing into \(bucketPoints[]\), is set when \(Q\) is initialized. During the first iteration of PMS6, for \(k=1\), \(l\)-mers in \(B_{d}(C)\) are stored in \(strs[]\). After all \(B_{d}(C)\)s are computed, \(strs[]\) is sorted in-place using Most Significant Digit radix sort. After sorting, duplicate \(l\)-mers are adjacent to each other. Also, \(l\)-mers that have the same first \(p\) characters and hence are in the same bucket are adjacent to each other as well in \(strs[]\). By a single scan through \(strs[]\), duplicates are removed and the pointers in \(bucketPoints[]\) are set to point to different buckets in \(strs[]\). During the remaining iterations, for \(k\geq 2\), all \(B_{d}(C)\)s generated are to be intersected with \(Q\). This is done by using the bit array \(markBuffer\). First, while computing \(B_{d}(C)\), each \(l\)-mer is searched for in \(Q\). The search proceeds by first mapping the first \(p\) characters of the \(l\)-mer to the corresponding bucket and then doing a binary search inside \(strs[]\) within the region pointed to by the bucket pointer. If the \(l\)-mer is found, its position is set in \(markBuffer[]\). Once all \(l\)-mers are marked in the \(markBuffer[]\), \(strs[]\) is compacted by removing the unmarked \(l\)-mers by a single scan through the array. The bucket pointers are also updated during this scan.  
For larger instances, the size of \(B_{d}(C)\) is such that we don't have sufficient memory to store \(B_{d}(C)\) in \(Q\). For these larger instances, in the \(k=1\) iteration, we initialize a Bloom filter using the \(l\)-mers in \(B_{d}(C)\) rather than storing these \(l\)-mers in \(Q\). During the next iteration (\(k\) = 2), we store, in \(Q\), only those \(l\)-mers that pass the Bloom filter test (_i.e._, the Bloom filter's response is \"Maybe\"). For the remaining iterations, we do the intersection as for the case of small instances. Using a Bloom filter in this way reduces the number of \(l\)-mers to be stored in \(Q\) at the expense of not doing intersection for the second iteration. Hence at the end of the second iteration, we have a superset of \(Q^{\prime}\) (Algorithm 1) of the set we would have had using the strategy for small instances. Experimentally, it was determined that the Bloom filter strategy improves performance for challenging instances of size (19,7) and larger. As in [22], PMS6 uses a partitioned Bloom filter of total size 1 GB. From Bloom filter theory [26] we can determine the number of hash functions to use to minimize the filter error. However, we need to minimize the run time rather than the filter error. Experimentally, [23] determined that the best performance was achieved using two hash functions with the first one being bytes 0-3 of the key and the second being the product of bytes 0-3 and the remaining bytes (byte 4 for (19,7) instances and bytes 4 and 5 for (21,8) and (23,9)instances).