The emergence of Linked Data on the WWW has spawned research interest in an online execution of declarative queries over this data. A particularly interesting approach is traversal-based query execution which fetches data by traversing data links and, thus, is able to make use of up-to-date data from initially unknown data sources. The downside of this approach is the delay before the query engine completes a query execution. This talk presents our work on addressing this problem based on an approach to return as many elements of the result set as soon as possible. The basis of this approach is a traversal strategy that aims to fetch result-relevant data as early as possible. To this end, we introduce a diverse set of heuristics-based traversal strategies, study their impact on response times, and compare them to a baseline that resembles a breadth-first traversal.