Fingerprinting.

Everything about you that isn't identical to everyone else can be combined to guess who you likely are. Your exact browser version, OS, supported APIs, your IP address, your latency to Google servers... Anything that isn't a complete match to everyone else.

You may have a new install, but your IP and latency match your old install. What are the odds you're not the same person?

It's all probabilistic. But Google has a lot of incentive to get really good at making those guesses.