4
$\begingroup$

In this problem, I'm first given n number of values which I have to store in a space efficient manner. Then I'm given m number of values which I have to check if they were added to the data structure before (such that after the operation, I know which value was a member, and which weren't).

I could use a Bloom Filter and simply iterate through m, but because m is considerably large, I wanted to see if there are more efficient ways. One potentially exploitable property of the data is that most values will not be present. I'm thinking I could construct an "aggregated query" which tells me if any of the value is present or not in one operation, and do something like a binary search, but wanted to see if there is already something out there.

Some additional details:

  • I can tolerate both false positives and false negatives (with predictable error rate)
  • n is very large (trillions)
  • m is considerably large (millions)
  • Only very few values in m will be members (ca. 1 in 100K)
  • The data structure can be immutable (no need for frequent writes)
$\endgroup$
  • $\begingroup$ If the data structure is allowed to be immutable, you might want to consider exact member query data structures instead, such as the Okanohara & Sadakane sdarray data structure, or succinct Cuckoo hashing. $\endgroup$ – Pseudonym Feb 15 '16 at 6:07
  • $\begingroup$ @Pseudonym: Do you know of a practical succinct Cuckoo hash table? The "Backyard" construction is pretty complex. I don't think the authors implemented it. $\endgroup$ – jbapple Feb 15 '16 at 6:16
  • $\begingroup$ The point of the Backyard paper is that all operations are constant-time worst-case. You don't actually need constant-time worst-case insertion, so the succinct hashing construction (invertible hash function, store only the bits which don't denote the hash slot) is the only bit you really need. The benefit of using a Cuckoo hash table is that you don't need a collision resolution scheme which uses extra space (e.g. separate chaining uses at least a pointer per item). $\endgroup$ – Pseudonym Feb 15 '16 at 6:19
  • $\begingroup$ @Pseudonym Somewhat like Cuckoo filters or Quotient filters? $\endgroup$ – jbapple Feb 15 '16 at 6:31
  • $\begingroup$ @jbapple I haven't really looked into them in detail, so I can't say for sure. $\endgroup$ – Pseudonym Feb 15 '16 at 6:32
3
$\begingroup$

If the query results are mostly false, the answer will be returned in $O(1)$ on average. (In traditional Bloom filters, negative results are faster than positive ones.)

This might be slow, however, since the lookups are random and have bad cache behavior. There are a few ways to fix this.

I'd suggest:

  1. Use a blocked bloom filter (from Cache-, Hash- and Space-Efficient Bloom Filters) in which each item is mapped to a single cache-line-sized Bloom filter.

  2. With the hash function that is used to map each item to a cache-line-sized Bloom filter, sort your queries in hash-value order.

  3. Do the queries as usual, but in order.

Another approach is:

  1. Use a split bloom filter, in which instead of setting $k$ values from a single array on each insert, set one value from each of $k$ arrays on insert.

  2. After doing the inserts, use your first hash function to sort the values you wish to query in hash value order.

  3. Query the first of your $k$ arrays for these values. Only a constant fraction will remain - $O(m)$ will be eliminated.

  4. Take the remainder and repeat the last two steps, but using the second hash function, and the second bit array. Repeat $k$ times.

Sorting is expensive in internal memory, but it might be cheaper than all the random accesses. It depends on your machine and your data sizes.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.