To decentralize private search, we'll build protocols for publishing your private data to cloud services that represent your interests. For some purposes, you'll publish data to services that keep your data isolated. You might even publish that data to your own machines. This works for email and cloud storage like Dropbox. Other purposes require data to be combined to add value, like recommendation systems and AI doctors. Services will compete with each other for your trust so you'll pick them. The bigger they are, the more useful they will be, so they're vulnerable to collapsing back into a monopoly. Anti-monopolists will give their business to competitors to keep them alive.
That is nice in theory, but not how it works in practice. Searching public data generally involves a significant amount of investment, both financially and effort-wise, to have anything approaching a usable search engine, even for relatively small sets of data.