My duplicate filter decided 166 of 174 job posts were the same post

I'm building GigsPaid, a board for paid coding gigs. It pulls listings from Freelancer, RemoteOK, We Work Remotely, Remotive, HN "Who is hiring" and GitHub bounties every minute. The same job often shows up on two sites, so there's a near-duplicate filter in front of the database.

After launch the board looked dead: 18 listings. Each scan was fetching around 340 posts.

So I replayed one scan into an empty database. 174 tech gigs went in. 8 came out.

The hash

Here's the simhash I shipped. I'll own it:

function simhash(text) {
  const tokens = text.toLowerCase().split(/\s+/);
  const v = new Array(64).fill(0);
  for (const tok of tokens) {
    let h = 0;
    for (let i = 0; i < tok.length; i++) h = (h * 31 + tok.charCodeAt(i)) >>> 0;
    for (let i = 0; i < 64; i++) v[i] += (h & (1 << (i % 31))) ? 1 : -1;
  }
  return v.map((x) => (x >= 0 ? '1' : '0')).join('');
}

A post counted as a duplicate if its hash was within 12 bits (Hamming distance) of anything already stored.

Two bugs, stacked.

1. The 64 bits were really 31. i % 31 makes bit 31 a copy of bit 0, bit 32 a copy of bit 1, and so on. Every real difference got counted twice, so "within 12 bits" actually meant "within 6 of 31".

2. A lot of those 31 never moved. h * 31 + c on short words like "the", "and", "for" and "you" gives small numbers, and small numbers have zeros in their high bits. Feed in a few hundred words of English and those high bits vote 0 for every document. Across my 174 gigs, 11 of the 31 bits were the same for every single one.

Together: the average distance between two unrelated job posts was 11.1 bits. The duplicate threshold was 12. 64% of all pairs looked like duplicates, and inserting them one by one kept 8.

The fix

Real 64 bits from two independent 32-bit FNV-style hashes, and the usual threshold for a 64-bit simhash (3):

let h1 = 0x811c9dc5;
let h2 = 0x01000193 ^ 0x5bd1e995;
for (let i = 0; i < tok.length; i++) {
  const c = tok.charCodeAt(i);
  h1 = Math.imul(h1 ^ c, 0x01000193) >>> 0;
  h2 = Math.imul(h2 ^ c, 0x5bd1e995) >>> 0;
  h2 = (h2 ^ (h2 >>> 15)) >>> 0;
}
for (let i = 0; i < 64; i++) {
  const bit = i < 32 ? (h1 >>> i) & 1 : (h2 >>> (i - 32)) & 1;
  v[i] += bit ? 1 : -1;
}

Same scan, empty database: 174 stored. Production went from 18 listings to over 100 on the next deploy.

Notes to past me

• Test the hash, not only the dedupe. Hash 100 random documents and check the average pairwise distance sits near 32 of 64. Mine was 11.
• h * 31 string hashing is fine for a hash table. It is not 32 random-looking bits.
• Log fetched vs stored per source. That one ratio would have shown this on day one.

GigsPaid itself: a client posts a job with a fixed price, and the first coder to tap Claim gets it. No proposals. It's free for both sides, and right now it has 100+ paid listings and 40+ open GitHub bounties: gigspaid.com