Between Dec 19, 2024 and Jan 2, 2025, datasets can be submitted to DRUM but will not be processed until after the break. Staff will not be available to answer email during this period, and will not be able to provide DOIs until after Jan 2. If you are in need of a DOI during this period, consider Dryad or OpenICPSR. Submission responses to the UDC may also be delayed during this time.

Browsing by Subject "Route finding"

Now showing 1 - 2 of 2
  • Thumbnail Image
    Item
    Techniques for improving routing by exploiting user input and behavior
    (2014-10) Torre, Fernando
    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.
  • Thumbnail Image
    Item
    The value of geographic Wikis.
    (2010-08) Priedhorsky, Reid
    This thesis responds to the dual rising trends of geographic content and open content, where the core value of an information system is derived from the work of users. We define the essential properties of an emerging technology, the geographic wiki or geowiki, as well as two variations we invented: the computational geowiki, where user wiki input feeds an algorithm, and the personalized geowiki, where the system provides a personalized interpretation. We focus on two systems to develop these ideas. First, Cyclopath, a research geowiki we founded, serves the bicycle navigation needs of cyclists. We also present analysis in the context of Wikipedia, the well-known and highly successful wiki encyclopedia, using its size and maturity to draw lessons for smaller, younger systems which are far more numerous but hope to grow. We ask three questions with respect to this new technology. First, can it be built? Yes. This thesis describes the design and implementation of Cyclopath, which has grown to be a production system with thousands of users. Second, is it useful? Yes. We identified a representative geographic community, bicyclists, and they both tell us that the information in the Cyclopath geowiki is useful and show us by using the system in great numbers. We also present new ways to measure value in wikis, introducing new techniques for doing so from the perspective of information consumers. In particular, user work in Cyclopath has shortened the average route by 1 km. Also, we present techniques for obtaining more contributions (familiarity matters -- sometimes -- and users do work beyond what they are asked to) and algorithms for increasing the value of geowiki content by personalizing it, showing that traditional rating prediction algorithms (collaborative filtering) are not effective but simple algorithms based on clustering are. Finally, who cares? Many people. There are numerous communities with great interest in geographic information but limited, incomplete, or awkward access because the relevant knowledge is distributed among members of the community and otherwise unavailable. As our results demonstrate, geowikis are an effective way of gathering and disseminating geographic information, more so than previous techniques. Thus, this research has broad value.