Keyword-based search in general is particularly applicable if the searcher really knows what she is looking for and how to find it, i.e. to know the appropriate keywords to obtain the desired results. But in many cases either the objectives of the searcher are intrinsically fuzzy or she is not aware of the appropriate keywords. One way to solve this problem is to navigate and explore the search space along guided routes. In this paper we show, how Linked Open Data can be adopted to facilitate an exploratory semantic search for video data. We present a prototype implementation of exploratory video search and show how traditional keyword-based search can be augmented by the use of Linked Open Data.