Technology surrounds us with many daily Search tasks. However, there is a fundamental difference---one of user familiarity and control---that differentiates between search tasks in impersonal and personal search spaces. The World Wide Web itself is largely unknown, unfamiliar and impersonal to a user. In contrast, users regularly search in more `personal' spaces, such as their own files, their web history, bookmarks, downloads, and so on. These spaces are personal because the user has more knowledge, familiarity and control over their content. A byproduct of these qualities is that search in personal spaces is typically navigational: to navigate through or to recover familiar information. This differs from web search, where very often a user is trying to discover new or unknown information. This important difference in search intent means that there are often few `correct' results for a query in personal spaces, which is something we must keep in mind when implementing search algorithms. This thesis leverages structure and metadata to build novel algorithms for improving search in several important personal search spaces: finding a file in a file hierarchy, website navigation on a mobile phone browser, tag-based search in an online bookmarking system, and sponsoring content on mobiles. The proposed methods are highly practical and applicable to current real-life search problems that affect millions of users.