Naturalistic Driving Study: Linking the Study Data to the Roadway Information Database (2015)

Below is the uncorrected machine-read text of this chapter, intended to provide our own search engines and external engines with highly rich, chapter-representative searchable text of each book. Because it is UNCORRECTED material, please consider the following text as a useful but insufficient proxy for the authoritative book pages.

4Research Approach Matching Process Methods The method used in the present effort was developed to accu- rately associate large numbers of GPS latitude/longitude pairs (approximately 3.7 billion) with roadway links using feasible computing demands. At a high level, the approach used for matching was to process vehicle location data relative to digi- tal map data to identify when vehicles were traveling on a spe- cific link. Figure 2.1 shows a schematic of the process. Position-related data collected in the SHRP 2 NDS were processed through an algorithm that connects the GPS points to the digital map links representing the traveled roadway. Using a digital map database, the Matching Algorithm assem- bled a network of the road system surrounding a trip, includ- ing permitted travel directions and node geospatial locations. This network can be thought of as a swatch of the digital map data, surrounding the extents of the vehicle’s GPS data. The algorithm then processed the GPS points from each trip to identify the sequence of traversed intersections (nodes) and, as a result, the links traveled by the vehicle. The results of this algorithm are stored in a table that researchers can use to iden- tify links as well as the timestamps between which the vehicle was on the link. The researcher can also assemble sequences of links into a longer section of road that is of interest. Further detail on this process and the various data sets are described in more detail in the File Processing section of this chapter. Source Data Sets The Matching Process relied on data from three sources: vehi- cle location data, digital map data, and trip metadata. Vehicle Location Data Vehicle location data were collected using a GPS receiver inte- grated into the data acquisition system (DAS). The GPS receiver in the DAS was a Fastrax UP500. This receiver is of a similar quality to that found in other in-vehicle, consumer- grade navigation devices. It provided location-related mea- sures one time per second (1 Hz). The antenna for the GPS was mounted in the SHRP 2 head unit facing forward out the front windshield. The GPS receiver provides various position- and trajectory- related measures that were recorded using the WGS84 coordi- nate system. The variables used in the Matching Process were timestamp, position (recorded as latitude/longitude pairs), speed, number of satellites, and position dilution of precision (PDOP). Both number of satellites and PDOP are indicative of the extent to which the GPS receiver could compute precise location. At least four satellites are needed to compute a posi- tion. PDOP is computed on the basis of the angles to the sat- ellites. Broader angles between the satellites and the receiver, and having them lower on the horizon, will improve preci- sion (i.e., make PDOP lower). The measures were extracted from the DAS into various tables in the SHRP 2 vehicle data database in columnar for- mat using a file_id, variable_id, timestamp recorded, and the data value. For example, Table 2.1 represents a 3-second series of latitude (variable ID -317), longitude (variable ID -318), and GPS speed data (variable ID -330). The number of satellites and PDOP data are stored in sepa- rate relational tables, in the same table organization (i.e., time- stamps, variable IDs, and values). These five variables can be joined together using file_id and timestamp. Digital Maps The road network, which for this application can be consid- ered the geospatial location of roads, connectivity of roads, and allowable direction of travel, was provided for use in the Matching Process by HERE North America, LLC. What we could consider a roadway is composed digitally as a set of links and nodes, which when portrayed in a GIS application appears as shown in Figure 2.2. C h a P t e r 2

5 The dense patches of roads in the center of the state are the areas where most of the participant driving occurred, and indi- cate where the NAVTEQ links are fully included. Beyond these patches, NAVTEQ links representing smaller roads are not included in the RID (see Figure 2.3). Note also that not all NAVTEQ links in the RID will be linkable to detailed roadway inventory data. The extent of the available inventory data is included in a separate report. The process of matching all of the SHRP 2 NDS GPS records to roads required a different data architecture from the digital map format used for the SHRP 2 RID. The Matching Process used a relational data architecture. NAVTEQ’s relational data format of this type precedes the ESRI product release number by one quarter (ESRI e-mail technical support, 6/24/14). Thus, the NAVTEQ 2012Q2 data was obtained from HERE for use within the Matching Process. These digital map data were stored as relational database tables that could be accessed through standard database queries. The output of the Matching Process was inspected for continuity of routes and for agreement in road names between the two data architectures, further con- firming their agreement. In addition to spatial location information, the digital map data provide other attributes of the links and nodes. Node attributes describing what links are connected at a given node were used in the Matching Process. The digital map data could be queried to determine what other nodes could be reached from a given node. For example, at Node A in Figure 2.2, a query of the digital map data would indicate that five links were connected at that node. The two highway ramps to the west (AB and AC) would be coded as only allowing travel either onto the highway (AB) or off the highway (AC). The other three links (AD, AE, AF) would be coded as allowing travel in both directions. Thus, in this example, four nodes could be reached from the indicated node. Further, it is helpful to note that a vehicle known to be traveling on the link emanating to the south (AF) from Node A cannot directly access the two parallel east-to-west oriented Figure 2.1. Inputs and outputs of the Matching Algorithm. Table 2.1. Illustration of How GPS Data Is Stored in the SHRP 2 Database (Speed Values in m/s, Latitude/Longitude in Decimal Degrees) Timestamp (ms) Variable ID Data Value 2023327 -330 30.19528 2023327 -318 -75.86013 2023327 -317 37.472706 2024327 -330 30.318735 2024327 -318 -75.86028 2024327 -317 37.472466 2025327 -330 30.102688 2025327 -318 -75.86044 2025327 -317 37.47222 Figure 2.2. Illustration of roads in a digital map made up of links and nodes. The digital maps used in the SHRP 2 project are all based on NAVTEQ source data. The RID is based on the ESRI Street- Map Premium 2012Q3 product based on NAVTEQ data. ESRI 2012Q3 documentation defines LINK_ID as, “The NAVTEQ permanent Link ID: Unique IDs for the features” (StreetMap Premium for ArcGIS North America NAVTEQ data diction- ary). NAVTEQ’s 2012 data includes more than 40 million links making up the North American road system (newer releases have more links). The Matching Process used all the links in the NAVTEQ data. The RID includes 1.8 million of the NAVTEQ links stored in a geospatial database format. Within a state, the RID includes all the links in the areas where most of the participant driving occurred. Links in parts of each state that are farther from the central participant area are not included in the RID. This sam- pling is illustrated in Figure 2.3 for the state of North Carolina.

6highway sections because the Link AF does not share a node with the east-west highway links. Trip Metadata At the same time that the matching processing was being done, participant data associated with each trip were being stored in SHRP 2 database tables as part of the SHRP 2 driver identifica- tion activities, and trips by unconsented drivers were being identified. To permit these two activities to be conducted in parallel, the Matching Process was executed on all data, and an intermediate output table was purged of trips by unconsented drivers before generation of final output. Computing Infrastructure The computing infrastructure used in the Matching Process was composed generally of the storage architecture, a compu- tational architecture, and the network. The vehicle data, digital map data, and trip metadata were stored in an IBM DB2 data- base that was configured with one head node and four cluster nodes. The code used in the Matching Process was written in MATLAB language and executed on an IBM Platform LSF cluster with 96 nodes. These computational nodes work simul- taneously to read map and vehicle data from the databases, process the data to develop a solution describing the links on which the participant traveled, and then write the solution to another database table that will become the final deliverable for the matching task. These processes are described in more detail in the following section. File Processing Creating a File Processing Order The first step in processing the trip data was to identify file_ids for the trips driven by consented participants and then to ran- domize these trips before submitting them for processing. The trip metadata were queried to locate files for the trips driven by the participants. The file_ids for these files (approximately 5.5 million files) were then stored in MATLAB native data for- mat. A random number was assigned to each of the files, and the files were then sorted by this random number. Random- izing file selection during code testing and final processing ensures that adjustments to the code (e.g., correcting logic errors, changing GPS accuracy thresholds) were made with- out bias from factors that could be indirectly included in the file_id numerical order, such as date of trip collection or data collection site. This file order was then divided up and sub- mitted to the computational cluster in different batch sizes (e.g., 400,000 files per batch in the beginning, 1,200,000 files per batch in the end) until the entire set of files had been submitted for processing. Processing an Individual File All processing of trips was done in MATLAB on computa- tional cluster nodes. When a MATLAB computational node was assigned a file to process, it first retrieved the latitude, longitude, timestamp, and PDOP for the trip. These values were stored in the format shown in Table 2.1. An average trip would have approximately 3,600 records describing approxi- mately 720 GPS locations during a file. After the GPS data were retrieved, the number of satellites and PDOP values were processed to locate the first point in a file at which the number of satellites was greater than five and the PDOP was less than or equal to 17. GPS data recorded before this point in time were omitted from consideration because of their imprecision. Both the number of satellites and the PDOP thresholds were established by reviewing many trips to see where the Matching Process failed and then con- sidering the levels in these two variables coincident with the solution failure. Generally, once the thresholds were met in a file, the solution was reliable. Infrequently, a trip might meet these criteria for a time, and then position quality would decrease for a time and then recover. This might happen, for Figure 2.3. Illustration of RID link inclusion.

7 example, when the vehicle was under dense foliage for a period of time. These periods of reduced accuracy later in a file were not omitted from consideration because the pre- vious accuracy would often permit obtaining a good solution even during the period of reduced accuracy. After determining the reliable GPS points, map data were retrieved for a rectangular area bounding the trip coordi- nates. The data included the links, the nodes where the links connect, and the allowable direction of travel along the link. Once the GPS data and the digital map data were available within the computational nodes MATLAB workspace, the distances were computed from each latitude/longitude pair to all of the nodes on the map, and the nodes closest to the start and end of the file were identified. The core Matching Process then was applied. The file was processed sequentially, both from the beginning of the file to the end and from the end of the trip to the beginning. The sequential processing through the file used a relational database that defines the road system as records in database tables. The relational tables can be queried to determine what links connect at a node of interest. The simplified road net- work presented in Figure 1.3 is repeated in Figure 2.4 to fur- ther describe the Matching Process. The connectivity of the road network in Figure 2.4 is cast in table form in Table 2.2. In this example, letters are used to identify nodes. In the digital map database, the nodes are nine- and 10-digit integers. Nodes connected by roads appear on the same row. (See Table 2.2.) To determine what nodes can be reached from Node D in Figure 1.3, a query such as SELECT node_2, latitude, longitude FROM table WHERE node_1=D will return only nodes C, V, and E (see Table 2.3). Continuing with the example portrayed in Figure 1.3, notice that the results do not return Nodes W or X because they are not accessible from Node D. A query of this type can be executed, and results set returned, in hundredths of a second using an appropriately designed and tuned database system. With this awareness of the connectivity Figure 2.4. Illustration of a road network. Table 2.2. Simplified Example of Table Defining Roadway Network Connectivity Node_1 Node_2 Node_2 Latitude Node_2 Longitude C D 37.1891515 -80.399365 C U 37.2198035 -80.418025 C B 37.1893088 -80.396527 D C 37.2198035 -80.396527 D V 37.1893088 -80.418025 D E 37.1891515 -80.399365 Table 2.3. Simplified Results Set Identifying Nodes Accessible from Node D Node_1 Node_2 Node_2 Latitude Node_2 Longitude D C 37.2198035 -80.396527 D V 37.1893088 -80.418025 D E 37.1891515 -80.399365

8of the roadway network, the algorithm logic needs only to follow the feasible sequence of links to which the GPS points track closest. Further, only distances from the GPS points to the nodes need to be evaluated, which greatly reduces the com- putational demands compared with spatial joins and buffers. In addition to reducing the computational demands, the expo- sure to errors where GPS points land on side roads (e.g., Links CU and EZ in Figure 1.3) or where roads cross each other (e.g., Links DE and WX in Figure 1.3) are eliminated. Using this network-aware technique, in its simplest form, the algorithm can iterate through nodes, identifying a small set of accessible nodes ahead (e.g., two to five nodes) and picking the one that the GPS path tracks closest to as the next node in the sequence. The following additions to the logic were used to further improve performance. In addition to ignoring nodes that could not be reached by a link, the allowable direction of travel on a link was also que- ried from the database table. In this way, nodes that are only accessible by traveling the wrong way are eliminated from con- sideration. This assists, for example, in divided highway situa- tions where the GPS is displaced toward an oncoming lane. It also can be used to eliminate consideration of special purpose roads, such as those that only allow emergency vehicle traffic. Rather than considering only one node forward in time as described in the simplified logic above, the actual logic assem- bles candidate routes to every node reachable, traveling the cor- rect direction on the link, up to three nodes ahead. It then selects the candidate route with the fewest errors between the three nodes and the nearest GPS points, and then chooses the first node on that candidate route as the next node in the solution. In each iteration, this is essentially building a branching net- work three steps ahead in all feasible directions, but then back- ing up two nodes to the best candidate route to identify the next node in the solution. This technique helps avoid routing errors based on transient GPS errors, avoid accidentally select- ing a path where GPS points wander at intersections where roads diverge at narrow angles (e.g., interstate deceleration ramps), and avoid cases in which a digital map node is located slightly ahead of or behind the actual location where roads split. The road network is also processed in this way, both for- ward and backward through a trip. Generally, the accuracy of the GPS was lower at the beginning of the trip, while the GPS receiver acquired signals from satellites for use in the compu- tation of position. Based on this, the logic located the first nodes in the trip that had vehicle-to-node distances of less than 52.8 ft (1/100th of a mile, selected based on data review during testing). This value was selected by reviewing a num- ber of algorithm solutions for a straightforward cut-off below which matching appeared reliable. Any nodes selected before this were eliminated from the solution because the accuracy was suspect. Processing the trip in two directions created two separate solutions, one of which needed to be selected as the best. The reverse solution often had better chance of success because it started at the end of the file, where the GPS had been on and working longer, and so was more accurate. This was not the case 100% of the time, so both solutions were evaluated on two factors to determine which appeared to be best. The first and most heavily weighted factor in this evaluation was the amount of time of the trip that was matched to the digital map. This value was computed as a percentage (in time) for both the forward and reverse solutions. If the forward solu- tion could not obtain a good solution based on vehicle-to- node distances until a timestamp 25% into the trip and then solved all the way to the end of a trip, but the reverse solution solved from the end of the trip all the way back to a timestamp 10% from the beginning, then the reverse solution would have solved for 90% and the forward solution for only 75%. The second factor was a percentage of vehicle-to-node outli- ers found internal to a solution. If a file solution located 100 links, but two of them had vehicle-to-node distances greater than 105.6 ft (1/50th of a mile, selected on the basis of data review during testing), then 2% of its points were considered outliers. An example of this is a solution that got off on the incorrect road, possibly a parallel service road, and then recov- ered. The points where it was off-track would have a greater vehicle-to-node distance. This was a less common failure mode and also considered a less serious failure, in that it was for a short portion of the trip. The percentage of time solved was weighted as 80% and the percentage of outliers was weighted as 20%. The two solu- tions were then compared and the one with the higher total score was retained as the final route solution and written to the table collecting the results. Process Monitoring As files were processed, a separate set of database tables was used to track the processing of the work. These tables tracked whether or not a file was successfully processed, and if it was processed, the number of links that were identified in the solution. These tracking tables were used to identify the number of files that were not processed completely and the reason they were not processed. In some cases, files might have sufficiently poor GPS accuracy that a solution cannot be established in either the for- ward or reverse directions. A file might not be processed fully if it was an exceptionally long trip that exceeded the memory space of a computational node. When large numbers of failures of the same kind were found, the tables were used to guide revi- sions to handle special cases. Additional details on file process- ing outcomes are provided later in this document. Quality Assurance Accuracy and Error Estimates To evaluate the quality of the results, a three-step process was used to establish a “correct solution” against which the Match- ing Algorithm could be evaluated.

9 Manual Route Reduction First, data reductionists visually translated GPS point paths from files into a list of road names, similar to a set of turn-by- turn directions defining the route. Reductionists were pro- vided a list of files by consented drivers in a random order. In this task, reductionists opened a file in the Virginia Tech Transportation Institute’s (VTTI) data reduction software (Hawkeye) and selected the Map Dashboard. This function overlays the GPS points (shown in yellow) on aerial imagery (see Figure 2.5). Reductionists visually inspected the map and GPS points to determine the road the vehicle was on. Reductionists moved the map using mouse click-and-drag and/or referenced the vehicle yaw values to slew the map to where turns were made. In addition to identifying the street names, the reductionists approximated the timestamps at which transitions occurred between one road and another. While identifying the route of travel, reductionists also coded the accuracy of GPS. Levels of accuracy were approximated into five levels: no displacement, slightly displaced, moderately displaced, extremely displaced, and poor geometry (the example in Figure 2.5 was considered moderately displaced). Each level was operationally defined using visual examples provided in the protocol. Additional detail on this method can be found in Appendix A. While not the same trip shown in Figure 2.5, Table 2.4 provides an exam- ple output of the reductionists’ work. Comparison of Manual Solution to Matching Algorithm Solution Once the data reductionist completed review of a file, another researcher checked the manual solution against the output of the Matching Algorithm. This task was a check of both the manual results and the algorithm. To accomplish this check, code was used to create an Excel file in which each tab described a trip, and it included the manual solution (Table 2.4) and the algorithm solution (Table 2.5). The results of the manual solution are provided in Table 2.4. In this example, the reductionist identified five roads by name (road order 2–6). Travel on these roads was preceded and fol- lowed by some time not on a named road. In Table 2.5, the output of the algorithm is presented. The algorithm reports every link traveled on, whereas the manual reductionist only identifies where road names change, such as at a turn. To make the algorithm output comparable to the manual output, code was used to reduce repetition of a road name over many LINK_ IDs into a single time span. For example, Southwestern Blvd read manually off the map is identified as one road but is actu- ally made up of 117 LINK_IDs (the 5th link in the file to the 121st link in the file). It is also stored in the database as “South- western Blvd” and “US-20.” The researcher manually compared the road names, sequence, and timestamps between the reductionist’s version and the algorithm version. When disagreements were identi- fied, the researcher opened the file and confirmed whether the reductionist had made a mistake or the algorithm had made a mistake. Corrections were made as necessary to the reductionist’s manual output (Table 2.4). To validate the algorithm results, the second researcher generated a random number from one to the number of links reported by the reductionist. In the example in Table 2.4, this Figure 2.5. Portrayal of GPS points from a trip overlaid on aerial imagery as seen by video reductionists. Table 2.4. Example Results from Visual Inspection of GPS Points on Aerial Imagery Manual Road Order Road Name Read from Map Start (ms) End (ms) GPS Rating 1 None 0 334943 Poor geometry 2 Shadagee Rd 334944 391149 None 3 Southwestern Blvd 391150 1541418 None 4 Angle Rd 1541419 1630939 None 5 East and West Rd 1630939 1670095 None 6 Main Dr 1670096 1784703 None 7 None 1796368 1841680 None

10 would be a random number from 1 to 7. The researcher then checked this row for algorithm accuracy. For example, if the random number 2 was generated, the researcher looked at the road name provided by the reductionist and saw “Shadagee Rd.” In the algorithm solution (Table 2.5), “Shadagee Rd” is placed there through an automated process. The researcher then checked the timestamps at the start and the end of the road to make sure they were in agreement. In this example, the manually identified start of “Shadagee Rd” is about 4 sec- onds earlier than when the algorithm identified the start. The end of the road has a similar difference. This agreement indicates that the algorithm agreed with the manual method for links 1 through 4, which accounts for the time between timestamps 338922 and 395923, or 57 seconds. This time span would be classified as a true positive. Only one row was checked in each trip. However, reusing the trip shown in Table 2.4 and Table 2.5 for illustration, if the random number picked had been 7, the manual method indicated the participant was not on a road, but the algo- rithm incorrectly indicated the vehicle was on Honeysuckle Dr after timestamp 1787946. This 30 seconds would be classified as a false positive. If the random number picked had been 1, the manual method indicated the vehicle was not on a road or not on a named road. The algorithm (Table 2.5) did not assign a link to this timespan, so this is classified as a true negative. This process was conducted for 100 files, providing a check of 100 manually identified roads. Recall, because a manually identified road is generally made up of many links in the database, this represents checking of many links. See Fig- ure 2.6 for the results of this analysis presented in a confusion matrix. In this matrix, the actual (i.e., manually identified) situation is presented in the rows, and how the algorithm defined the situation is presented in the columns. If the Matching Algorithm agrees with what was found through the manual process, then it is correct. As shown in Figure 2.6, the algorithm correctly assigns the driving data to the correct link 91% of the time. In 86% of the time the algorithm does not assign the data to a link, the GPS data is actually not on a link. In 2% of the time when the vehicle is not on a link, the algorithm assigns the data to a link. Table 2.5. Example Results from Algorithm Algorithm Link Order (n) Start (ms) End (ms) Road Name 1 from Database Road Name 2 from Database Road Name 3 from Database 1 338922 395923 S Creek Rd Shadagee Rd CR-476 5 395923 1543942 Southwestern Blvd US-20 122 1543942 1631943 Angle Rd 130 1631943 1671944 East and West Rd CR-363 East and West Rd 134 1671944 1787946 Main Dr 137 1787946 1817946 Honeysuckle Dr Link N Not on Link Link N 6,470,066 True Positive 620,613 False Negative 91% Sensitivity Method finds x% of link time correctly. Not on Link 131,012 False Positive 774,447 True Negative 86% Specificity x% correct ignoring time that is not on a link. 98% 56% PPV NPV Driving Seconds Algorithm Ac tu al Figure 2.6. Algorithm validation confusion matrix.

11 Masking Personally Identifying Information The Matching Algorithm attempted to identify every link on which the vehicle traveled. Various approaches have been explored for removing or masking locations, such as where the participant lived or worked. The current best approach is con- sidered to be removing links leading up to an inter section that has many (e.g., three or more) approach options. In this way, from the data included in the file, many possible travel paths might have been taken by the vehicle and thus the actual des- tination would not be apparent. However, further work and review of this approach is required. The Linking Table will continue to be treated as personally identifying information (PII) until a masking solution can be identified and approved.