4 ms·

Is there any way of being able to store a corresponding value to the elements in the set? I understand that hash tables do that -- however, what I wish to ask i

Is there any way of being able to store a corresponding value to the elements in the set? I understand that hash tables do that -- however, what I wish to ask is that do we have a space efficient data structure for key-value pairs?

dgacmu 10y ago
Yes, many - but it depends how practical you want it to be and what tradeoffs you can accept. Broadly speaking, you're asking about the class of data structures for (almost) minimal perfect hashing. For example: * ECT, or Entropy-Coded Tries, (paper: http://www.cs.cmu.edu/~hl/papers/ect-alenex2013.pdf http://www.cs.cmu.edu/~hl/papers/ect-alenex2013.pdf ) are a static data structure (no insertions after you build it) that are very fast to construct, take about 7 microseconds of CPU time to lookup, and have 2.5 bits of overhead per item inserted. This is the best data structure I know of for external perfect hashing, where you want to store the key/value pair itself on something expensive to access, like an SSD. Implementation available in SILT: https://github.com/silt/silt https://github.com/silt/silt * CMPH (http://cmph.sourceforge.net/concepts.html http://cmph.sourceforge.net/concepts.html) and friends are very fast MPH functions when you want to store the key value pairs in memory. * There was a really cool paper at SEA a few years ago on Retrieval and Perfect Hashing using Fingerprinting (http://link.springer.com/chapter/10.1007%2F978-3-319-07959-2_12 http://link.springer.com/chapter/10.1007%2F978-3-319-07959-2...) that came out of SAP. I don't know if they have code available. It's also internal, but uses the same fingerprint-centric idea as ECT, but in a faster way that doesn't require the expensive huffman coding that ECT uses. There's a ton of very fun research in this area -- this is just the tip of the iceberg (and I haven't really looked at it for two years, so there's probably been more since).
- prashnts 10y ago
  Thanks for these! I haven't given a thorough read yet, will do so later today. Probably off topic, however, in the CMPH link you quote above, what I gather about the MPH functions is that in any practical setting they probably would require a combination of hash functions to avoid collisions -- right?
  - dgacmu 10y ago
    Because they're internal hash functions, they have access to the original key being used, so they can tolerate a few collisions -- in the implementation of CHD, there's a -t parameter for number of collisions in a bin to provide a bit of flexibility. So they don't require a completely collision-free hash function, just one that on the input dataset is not going to produce more than a few.

dgacmu 10y ago

Yes, many - but it depends how practical you want it to be and what tradeoffs you can accept. Broadly speaking, you're asking about the class of data structures for (almost) minimal perfect hashing. For example: * ECT, or Entropy-Coded Tries, (paper: http://www.cs.cmu.edu/~hl/papers/ect-alenex2013.pdf http://www.cs.cmu.edu/~hl/papers/ect-alenex2013.pdf ) are a static data structure (no insertions after you build it) that are very fast to construct, take about 7 microseconds of CPU time to lookup, and have 2.5 bits of overhead per item inserted. This is the best data structure I know of for external perfect hashing, where you want to store the key/value pair itself on something expensive to access, like an SSD. Implementation available in SILT: https://github.com/silt/silt https://github.com/silt/silt * CMPH (http://cmph.sourceforge.net/concepts.html http://cmph.sourceforge.net/concepts.html) and friends are very fast MPH functions when you want to store the key value pairs in memory. * There was a really cool paper at SEA a few years ago on Retrieval and Perfect Hashing using Fingerprinting (http://link.springer.com/chapter/10.1007%2F978-3-319-07959-2_12 http://link.springer.com/chapter/10.1007%2F978-3-319-07959-2...) that came out of SAP. I don't know if they have code available. It's also internal, but uses the same fingerprint-centric idea as ECT, but in a faster way that doesn't require the expensive huffman coding that ECT uses. There's a ton of very fun research in this area -- this is just the tip of the iceberg (and I haven't really looked at it for two years, so there's probably been more since).

prashnts 10y ago
Thanks for these! I haven't given a thorough read yet, will do so later today. Probably off topic, however, in the CMPH link you quote above, what I gather about the MPH functions is that in any practical setting they probably would require a combination of hash functions to avoid collisions -- right?
- dgacmu 10y ago
  Because they're internal hash functions, they have access to the original key being used, so they can tolerate a few collisions -- in the implementation of CHD, there's a -t parameter for number of collisions in a bin to provide a bit of flexibility. So they don't require a completely collision-free hash function, just one that on the input dataset is not going to produce more than a few.