> What's your proposed basis, historic or constitutionally, granting the state the power to aggregate people's location history?

Is the executive empowered to enforce laws? Is recording observations a function of law enforcement? Society recognizes things like "plain view" in that if an officer is legally in a place and can see illegal activity they may act on it. So it would follow that they can record their observations about suspected illegal activity and legal activity alike (because suspected illegal activity might actually be legal in fact).

So if police can observe things freely and they can record their observations, well can't police departments store and search through police records?

The state will take for itself power that the people have but do not wield.