The Smallest Hash Table
orlp.net
orlp.net
The paper goes into quite many details about the probability to find a minimal perfect hash function for small sets. I hope it is somewhat readable... the section for small sets is 5.2 "Searching for bijections": the average number of trials is (m^m / m!), with m being the size of the set. The rest of the paper is to extend this idea to larger sets, by splitting the sets recursively until they are small enough to be mapped in this way.
If papers are rejected purely on prestige rather than merit that would be quite sad.
It is extremely hard to believe that the submission was not accepted BECAUSE of the lack of university affiliation.
But what is indeed true is that different conferences/journals have different expectations from a submission. Some prefer more theoretical analysis, others more computational work and benchmarking. And this is where a seasoned Professor offers value. They can judge where to submit a paper and have a high probability of success.
You know, looking at figure 2 and 3 I was thinking so sure it is a mapping structure but really looks like a tiny tiny database! I had no idea phfs were so involved structurally. Reminds me of delicate tiny clockworks.
The idea would be to use the expected phrasings and idioms, format, etc. Of course, all content would have to be checked, as LLMs are prone to BS. But if the problems were mostly that it didn't follow the conventions of that academic subgenre, this seems exactly what an LLM could do. If the problem was more about e.g. not citing previous work, the LLM probably wouldn't do a good job there.
> as LLMs are prone to BS
I agree. The output sounds very convincing, and on a high-level it might make sense. If there are 3 layers: (a) high-level idea, (b) more detailed ideas, and (c) choosing the right words, tone, syntax, grammar, then LLMs seem to be very good in (a) and (c), but quite bad at (b). For somebody not familiar with the topic, it's hard to detect this.
Consider feeding your outline through the LLM alongside prompts like:
- "What's missing from this draft that a reader would expect to find in a top-tier conference paper?"
- "Do you see any problems with the {experiments,discussion,background,related work} section?"
- "What previous work should this paper cite that an expert would find relevant in this field?" (be sure to double-check the sources, LLMs tend to hallucinate with prompts like this)
- "What points is an expert in the field likely to raise during peer review?"
- "Which parts should be rephrased to make the paper sound more natural to a native English speaker?"
As an occasional peer reviewer, I could imagine conferences having a problem with GPT-generated paper submissions clogging up an already highly competitive acceptance pipeline. In case conferences start using detection tools to filter such manuscripts (and I'm torn on whether they should tbh), you can still use ChatGPT like a "friendly, expert colleague" who offers suggestions that you then draft yourself.
I think the application of ChatGPT that I like the most is where ChatGPT is a "friendly, expert editor that always has time to give you suggestions and offer advice," tightening the feedback loop between author and editor to help the author improve their writing. Think of it like a "human-learner-in-the-loop" AI system rather than a "replaces-a-human" AI system.
https://docs.rs/compressed_map/latest/compressed_map/
This isn't quite an MPHF in that it doesn't map keys to a unique bucket, but instead maps them directly to an output. So unlike an MPHF, it's only suitable for when you are sure for some other reason that the input really is a key to the map (or don't care about if you get a garbage answer when it isn't). However, for this reason the output can be smaller than an MPHF. The motivating use case is checking whether certificates are still valid, but I'm sure there are others (chess endgames??).
I think you can also use it to build an MPHF with a similar space usage to yours, with constant expected lookup time but slower (and superlinear) construction time.
The compressed_map crate isn't properly optimized for compressing small maps, because it stores a bunch of padding and metadata that's negligible for huge maps.
Note that also an MPHF, as a static function, does not store the keys. A static function assigning a different output (e.g., rank) to every key will always use more space than a MPHF because you can choose the order.
I've releaed a set of fast hash functions[1] to help gain an understanding of speed vs. quality. My biggest takeaway is that most generic hash functions can be specialized for integer inputs[2], which often reduce latency by quite a lot, making MPFH more attractive over simple iteration on small sets, as the overhead of hashing is considerably smaller.
[1] https://github.com/Genbox/FastHash
[2] https://github.com/Genbox/FastHash/blob/master/src/FastHash/...
Absurd amounts of actual run-time optimization (as opposed to golfing the source size) are informative and cool and I guess more people should engage in that kind of activity. :)
that said, rust indeed should work on fixing numeric conversion, not just for these small word sized but for everybody.
Of course nobody prevents you from using Float, Long_Float, Integer everywhere, but it is actually discouraged. Define a specific type. Is it a count, a speed, a quantity of apples, a modular value (i.e. you actually want wraparound semantics), what is its minimal value, its maximum value... The actual binary representation is more of an implementation detail (and can be coerced to do many, many things through 'aspects' or pragmas or just representation clauses.
If I could change one thing there, it's the operator visibility rules, which a perennial compaibt of the Ada developer. But, to dissent from my Adaist brethren I'd ask the standard to go to more explicit operator choice. Make it explicit in the code and for those with RSI make the IDE do the inference and print it in the darned code. Please?
https://www.microsoft.com/en-us/research/publication/relatio...
This seems superior to the GNAT solution. And support for dimensionality is somewhat orthogonal to the ergonomics of converting e.g. a u32 to a u64 that comes up in systems programming.
To be slightly pedantic, this solution uses a lookup table too, but it's small enough that it fits in a machine integer (and thus can be loaded as an immediate value).
In general, there is an information-theoretic lower bound on the size of the auxiliary data you need to build a perfect hash function, and it's Omega(n) bits for n keys. The constant depends on the load factor, when that is 1 it means that the hashes are in [0, n) and the perfect hash function is called minimal, and the space lower bound is log(e)*n bits
For very small n, brute-forcing like this generally yields good functions. In fact, it is one of the strategies used by gperf.
pub fn phf_shift64(x: u32) {
((0x714258693u64 >> (x*4)) & 0b1111) as u8
}Just as a tidbit, to dig deeper into Rust.
How can I provide some quick evidence for this? Well there's a method called u64::unchecked_shr that acts as contrasting evidence.
pub fn phf_noshift(x: u32) -> u8 {
(x.wrapping_mul(0x9e4c340a)%13) as u8 // Not a hash table
}many constants work with 13 : 0x93f0687f, 0x8c38599e, 0x8f5e14c2, 0x932d2c11 some with 71 : 0xd9526a52, ... couldn't find mod 923