Ask HN: Order preserving hashes for learned Indexes

2 points

4 years ago

https://github.com/rodgarrison/PGM-index was previously posted to HN. However, to leverage PGM for keys that are strings or blobs (arrays of unsigned bytes) one needs a map from the key as an array of bytes to some integral type. What are the options here?

An order preserving hash is such that if keys k0<=k1 then hash(k0)<=hash(k1).

As far as I can tell the broad outline of options include:

* naive options like put all strings in a std map and give the index to the entry as the hash value

* Some variation of converting the key into a bitstream, maybe with compression hoping to get into a 64-256 bit range.

* Putting the keys into a trie or BST and converting the path through the structure to the key into a bitstream which becomes an int.

* An actual order preserving hash e.g. something like this: https://github.com/DominikHorn/exotic-hashing/tree/main/include/omphf

Does anybody know better? An important property (and relaxation) is that all the strings need may not be known ahead of time. So the hash need not be minimal.