# Data Quality Analysis and Improvement: A Case Study of a Bus Transportation System
## 4 Data-Cleaning Methods
### Parallel Implementation Based on RDD  
Figure 3 depicts workflow of noise filtering and map matching for a large-scale GPS trajectory dataset. The input dataset is GPS positioning records stored in HDFS. A dotted box stands for an RDD, and a gray square represents a partition. An arrow denotes the dependency among different RDDs. All of these RDDs form a pipeline to implement noise filtering and map matching for the GPS trajectory dataset. The left side lists the operators being applied to different RDDs, and the right side shows the corresponding RDDs and data structures within  
them. At each stage in this pipeline, it takes an RDD as input and generates a new RDD by applying an operator to the input RDD. The primary steps are as follows:  
Step 1: GPS records input. It loads the GPS record dataset from HDFS into memory and initializes the first RDD. Each element within the RDD represents a GPS record with a set of associated fields.  
Step 2: Data extraction. It extracts a set of fields from the original GPS record, including vehicle identity, timestamp, latitude, and longitude. Each element represents a single GPS point.  
Step 3: Trajectory generation. It employs the _GroupBy_ operator on the RDD generated in Step 2. Specifically, this operator groups and aggregates trajectory points based on their vehicle identities; it then sorts all points within each group by time and generates a complete trajectory for each vehicle.  
Step 4: Data partition. It utilizes the _rePartition_ operator and a User-Defined Function UDF) _partitioner_ on the RDD generated in Step 3, resulting in a new RDD with a varying number of partitions. This data partitioning aims to alleviate data skew among different partitions and enhance the parallelized tasks in subsequent stages. In the newly generated RDD, each element represents a trajectory segment rather than a complete trajectory.  
Step 5: Noise filtering. It employs the _MapValues_ and a UDF operator on the RDD generated in Step 4. This UDF implemented a heuristic noise-filtering method (Algorithm 1) to generate filtered trajectory segments.  
Step 6: Map matching. It employs the _MapValues_ and a UDF operator on the RDD generated in Step 5. This UDF implements the FMM algorithm (Algorithm 2) to conduct map matching, in which it takes a filtered trajectory segment as input and outputs a matched trajectory segment.  
Step 7: Trajectory rebuild. It employs the _GroupBy_ operator on the RDD generated in Step 6. Specifically, this operator groups and aggregates the trajectory segments based on their vehicle identities, sorts all segments by time, merges these sorted segments, and ultimately generates a complete matched trajectory for each vehicle.  
Step 8: Matched trajectory output. It saves the RDD generated in Step 7 to HDFS.  
Figure 3: The pipeline and workflow of noise filtering and map matching in Spark.  
Note that it is worth to further discuss the data partitioning technique used in Step 4. The re-partitioning process consists of the following steps: Firstly, the algorithm divides the geographical space into a set of uniform grids. Subsequently, it carries out a spatial intersection between each trajectory in the original RDD and the aforementioned uniform grids. During this process, a complete trajectory might be divided into distinct trajectory segments, with each segment being assigned a unique grid identity. Thirdly, it organizes all segments into separate partitions based on their grid identities, resulting in the creation of the second RDD. Within this RDD, every partition contains all trajectory segments assigned to the same grid.