News for hackers. Stuff that matters.
Re:The One Billion Row Challenge by londons_explore on Thursday January 04, 2024 @05:41AM (#38865466)
The next obvious solution is to have something that works fast for non-colliding station names, but then falls back to another (slow) implementation for colliding station names.

It's very cheap to detect station name collisions - just sample ~10,000 points in the file, and hope to find at least one of each station. If you find less stations than the full run, you haven't yet seen them all, keep hunting. If you find two that collide, fall back to the slow method. Checking 0.00001% of the dataset is cheap.

Re:The One Billion Row Challenge by anonymoushn on Thursday January 04, 2024 @07:41AM (#38866269)
It seems like you have to run the slow collision-resistant thing over the whole file.
Re:The One Billion Row Challenge by londons_explore on Thursday January 04, 2024 @08:25AM (#38866701)
Collision detection is far cheaper. One method:

Simply add up all the bytes of all seen placenames while running your fast algorithm. This is effectively a checksum of all bytes of placename data.

Then at the end, calculate the 'correct' name-sum (which can be done cheaply). If it doesn't match, a collision occurred.

Re:The One Billion Row Challenge by anonymoushn on Thursday January 04, 2024 @08:34AM (#38866775)
You can design inputs that defeat this scheme though. I thought the point was to be correct for all valid inputs.
Re:The One Billion Row Challenge by posix86 on Thursday January 04, 2024 @07:01AM (#38865952)
But how would you detect that a station name is colliding or not colliding? With a hash set?
Re:The One Billion Row Challenge by viraptor on Thursday January 04, 2024 @07:20AM (#38866082)
Search for cuckoo hashing. It's a whole thing for data structures.
Re:The One Billion Row Challenge by posix86 on Thursday January 11, 2024 @05:12PM (#38960073)
Cuckoo doesn't aid in detecting collisions, the algorithm is about what happens IF a collision is found. The whole reason we're hashing in the first place is to not have to linearly compare station names when indexing.

In other words: Cuckoo is a strategy to react to the case if two values map to the same hash. But how to know weather you have two different values, or two of the same, if they have an identical hash?