On the other hand, are Google required to store the data? I suspect they aren't, they only need to hand over what they do have when asked. So they could always let you opt out of them tracking your data. Which they don't. Sure, it might slightly reduce the quality of search results those users get to see, but that's a sacrifice I'd be willing to make.