The Web was designed as a decentralized collection of data. In recent years, this Web has become increasingly centralized by large companies, which are causing significant political and social problems. As such, many efforts are going on to re-decentralize the Web, which requires new technologies to maintain the applications that currently depend on this centralization. As applications currently require data to be centralized in a few large data sources for querying, decentralization leads many small data sources, which can not be queried efficiently by current algorithms. My objective is to investigate ways to query data on the Web without having to centralize data into a few large query endpoints. I will do this by investigating link-traversal-based query processing, which exploits the linked nature of data on the Web, and gives clients control over querying instead of servers. I will improve upon the performance of existing link-traversal technologies by allowing query engines to be guided towards query-relevant documents in a more intelligent manner. Furthermore, I will design hybrid algorithms that combine this link-traversal with querying using existing centralized query endpoints, which will offer trade-offs to achieve the best of both approaches. I will evaluate my algorithms by simulating realistic Web environments, and comparing to existing approaches. With this research, applications over decentralized environments can be built, based on efficient query execution.