Techniques for improving routing by exploiting user input and behavior
2014-10
Title
Techniques for improving routing by exploiting user input and behavior
Authors
Published Date
2014-10
Publisher
Type
Thesis or Dissertation
Abstract
This dissertation explores innovative techniques for improving the route finding process. Instead of focusing on improving the algorithm itself, I aim to improve the other factors that make the route finding experience better: personalization, map data, and presentation. I do so by making extensive use of user input (both explicit and implicit) and crowdsourcing strategies. This research uses Cyclopath, a geowiki for cyclists in the Twin Cities, MN, as a case study for the various techniques explored.The first challenge is the lack of personalization in route finding algorithms. Aside from start and end points, algorithms usually know very little about users. However, user preferences can greatly affect their ideal routes. I studied the use of community-shared tags that allow users to specify preferences for those tags instead of doing so for each individual road segment, allowing them to easily express preference for a large number of roads with little effort. Correlation between individual road segment ratings and ratings deduced from tag preferences was evidence of the utility of this technique for making personalization easier.The second challenge is missing data. The best routing algorithm is only as good as the map data underneath it. Unfortunately, maps are often incomplete. They might not have updates on the latest construction, might be missing roads in rural areas or might not include detailed information such as lanes, trails, and even shortcuts. I present an HMM-based map matching algorithm that uses GPS traces recorded by users to generate potential new road segments. Tests within Cyclopath confirmed the abundance of missing roads and the ability of this algorithm to detect them.Finally, I look at the issue of unnatural presentation of routes. The way computers relay route directions is very different from humans, who use landmarks most of the time. However, gathering useful landmarks can be difficult and is often limited to points of interest. In this research, I tested methods for crowdsourcing different types of landmarks. I show that POIs are not sufficient to represent landmarks and that there is no objective truth regarding which landmarks are more useful to users.
Description
University of Minnesota Ph.D. dissertation. October 2014. Major: Computer Science. Advisor: Loren Terveen. 1 computer file (PDF); xiii, 106 pages.
Related to
Replaces
License
Collections
Series/Report Number
Funding information
Isbn identifier
Doi identifier
Previously Published Citation
Suggested citation
Torre, Fernando. (2014). Techniques for improving routing by exploiting user input and behavior. Retrieved from the University Digital Conservancy, https://hdl.handle.net/11299/168317.
Content distributed via the University Digital Conservancy may be subject to additional license and use restrictions applied by the depositor. By using these files, users agree to the Terms of Use. Materials in the UDC may contain content that is disturbing and/or harmful. For more information, please see our statement on harmful content in digital repositories.