A comparative analysis of routes generated by Web Mapping APIs.

Author:Socharoentum, Monsak
 
FREE EXCERPT
  1. Introduction

    Some Web mapping providers (such as Bing Maps and Google Maps) provide mapping data and functionalities via Web Mapping APIs (WMAs) to allow development of specific geospatial Web applications and services. Such geospatial Web applications, also known as "Map Mashups" (Batty et al. 2010) and "Web Mapping 2.0" (Haklay, Singleton, and Parker 2008), reflect the emergent era of geospatial Web applications. WMAs allow researchers to access map data and map functionalities of which routes and directions, among other features, are prominent and commonly available. Currently, there are at least five publically available WMAs that provide access to geographic locations in which maps can be supported at no cost. These WMAs are Bing Maps REST Services (Microsoft Corp., n.d.), Google Maps API (Google Inc., n.d.), HERE Maps API (HERE n.d.), MapQuest Open Data API (MapQuest n.d.), and Yahoo Maps API (Yahoo! Inc., n.d.). Researchers in various fields employ WMAs to develop geospatial Web applications. Example usages of these WMAs are development of a web-based tool to provide tourism information for tourists in Charleston, South Carolina (Pan, Crotts, and Muller 2007); development of a decision-support tool to help analyze optimal locations for depots such that location and distribution costs are minimized (Lopes et al. 2008); development of a Web map for route and direction guidance to referral hospitals (Kobayashi et al. 2010); analysis of an origin-destination travel time matrix (Wang and Xu 2011); and development of a Web map that provides personalized optimal routes to people with physical disabilities (Karimi, Zhang, and Benner 2013). However, despite such projects, currently there is no study that compares the routes WMAs generate.

    While WMAs generate different routes based on the same criterion and for the same pair of origin and destination addresses, researchers may not have the requisite knowledge and expertise to compare and analyze the generated routes. Among the features that WMAs differ, quality of data (spatial and non-spatial) and their routing algorithms are focused to address the following research questions:

    * What is the relative positional accuracy among the road maps supported by different WMAs?

    * Using the same route criterion, do different WMAs deliver the same or different routes for the same pairs of origin-destination addresses?

    * For the same routes, are the route attributes (such as distance, direction, and estimated driving duration) also the same? In case of different routes, what are the differences between route attributes?

    The paper's contribution is an understanding of routes generated by common WMAs. The results of this work can benefit researchers as they will gain an insight into WMAs and the routes they generate. The process of conducting the analysis in this paper can also be used as a guideline to help researchers perform empirical evaluation on routes generated by WMAs. The structure of the paper is as follows. Section 2 provides the background and related work. Section 3 discusses the data and experiment preparation. Sections 4, 5, and 6 discuss the different parameters for route comparisons. In Section 7, the results of the comparisons are discussed. In Section 8, conclusions and future research are discussed.

  2. Background and related work

    2.1. Web Mapping API

    WMA is designed to work in the Web environment in which a server provides both map data and functionalities to geospatial applications running on a client. The benefits of WMAs to researchers are that: (a) they can save development time in setting up and managing Web Mapping Servers (WMSs) and (b) they can author specific content without concerns about base maps and related Web mapping functionalities. Table 1 shows a comparison between some WMA capabilities provided by Bing Maps, Google Maps, HERE, and MapQuest. Bing Maps, HERE, and MapQuest provide routes based on distance (shortest) and time (fastest) criteria. Google Maps does not allow request for shortest or fastest routes, but it provides a few alternative routes together with distance and travel time so that by analyzing alternative routes, shortest or fastest routes can be selected. The last row in Table 1 shows sources of road databases used by these WMAs. Note that only capabilities relevant to routes are summarized in Table 1; for other capabilities, refer to Haklay, Singleton, and Parker (2008) and Chow (2008).

    2.2. Hausdorff distance

    In this paper, Hausdorff distance (Hausdorff 1914), which is used to identify similar shapes, for example, see Huttenlocher, Klanderman, and Rucklidge (1993), Dubuisson and Jain (1994), Rucklidge (1997), and Peteri, Couloigner, and Ranchin (2004), is adopted to identify same route geometries retrieved from different WMAs. A brief description of Hausdorff is the following. Considering two sets of points in A and B, Hausdorff distance, dn(A,B), is defined as follows:

    [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (1)

    where a and b are the points in set A and B, respectively, and d(a, b) is the distance between point a and b, in a space of interest such as Euclidian space. If the points in A and B represent two different lines, then [d.sub.H](A,B) [not equal to] 0. If [d.sub.H](A,B) = 0, then it can be concluded that A and B are identical. Figure 1 shows four examples, all with the same value of Hausdorff distance ([d.sub.H]). Lines L5 and L6 in Example C, despite a large overlap, still have Hausdorff distance at the value of [d.sub.H]. This example shows that there is no correlation between the Hausdorff distance value and the overlap proportion between the two lines. However, [d.sub.H] [right arrow] 0 implies that the two lines are very similar, such that the geometric deviation between the two lines is small. When compared to the minimum (perpendicular) distance, Hausdorff distance is better for similarity measure because it takes into account the whole shape of the objects rather than considering only the two closest points.

    To take into account the variations of route geometry, the condition for identical shape is relaxed such that the new condition is [d.sub.H](A,B) [less than or equal to][beta], where [beta] is a predefined threshold. To determine a suitable threshold ([beta], the upper bound), a number of trials based on randomly selected samples from the population (routes of interest) were performed. The detailed discussion about this process and the value of [beta] are provided in the "Experiment" section.

    2.3. Route computation factors and relative positional accuracy

    The factors that impact route computation are: (a) node-link connection in road networks; (b) accuracy and resolution of road geometries; and (c) algorithms for computing routes. Node-link connection in road networks significantly contributes to differences in route computation. A road network is composed of nodes (representing road intersections) and links (representing road segments). Links contain traffic flow directions (two-way or one-way) information and properties affecting traversing such as speed limit, road width, distance, and road type. Nodes connect adjacent links and also contain traversing rules among the connected links such as "no right turn," "no through traffic," and "one way". A small difference in node-link connection in two distinct road networks may cause differences for traversing from one node to another in the network. Sources of differences in node-link connection are data update cycle, blunders in data collection, misrepresentation of links and nodes relations, among other sources. These sources vary by map providers based on the assumptions they make in building map databases, the design on which they implement their services, and the software and tools they use to deliver their services. Since WMAs utilize different road network databases (with such differences as node-link connection, data update cycles, and blunders), different routes would be expected.

    Accuracy and resolution of road geometry also cause inaccurate distance measurement. Since a road segment's distance is calculated directly from its coordinates, lower accuracy and lower resolution could result in less accurate distance. In addition to distance, relative positional accuracy of points (road intersections), retrieved from WMAs, was considered in this work. The vertical accuracy was not considered because the routes and directions provided by WMAs...

To continue reading

FREE SIGN UP