GPUs aren't limited to 1GB of memory, many have closer to 6 - 10GB now.
Yes - it's not about the amount of memory, GPU's can compare there with the current implementation.
The salient issue (unless I've misunderstood the algorithm) is that he asserts a CPU can use a hash table but a GPU can't, thus he asserts the GPU needs N ^ 2 memory. I don't see why the GPU can't use the same amount of memory as the CPU?
I think hashtables are a distraction from the point - which is . . .
The GPU can compute 1000s of lookups on that memory in parallel, thus obviating the random memory latency to be bound at the superior memory bandwidth of the GPU.
I'm not an expert in this area, but as far as I know the GPU has a wider bus, so can do more memory access (x4), but is slower so can do less (x0.25). So I think you could get comparable speeds out of a high end GPU as for a high end processor.