Spatial Big Data and Moving Objects: A Comprehensive Survey <s> 4) BI-DIRECTIONAL ROUTE PLANNING USING TAXI GPS TRACES [10] <s> We propose to extend database systems by a Skyline operation. This operation filters out a set of interesting points from a potentially large set of data points. A point is interesting if it is not dominated by any other point. For example, a hotel might be interesting for somebody traveling to Nassau if no other hotel is both cheaper and closer to the beach. We show how SSL can be extended to pose Skyline queries, present and evaluate alternative algorithms to implement the Skyline operation, and show how this operation can be combined with other database operations, e.g., join. <s> BIB001 </s> Spatial Big Data and Moving Objects: A Comprehensive Survey <s> 4) BI-DIRECTIONAL ROUTE PLANNING USING TAXI GPS TRACES [10] <s> Taxi GPS traces can inform us the human mobility patterns in modern cities. Instead of leveraging the costly and inaccurate human surveys about people's mobility, we intend to explore the night bus route planning issue by using taxi GPS traces. Specifically, we propose a two-phase approach for bidirectional night bus route planning. In the first phase, we develop a process to cluster “hot” areas with dense passenger pick up/drop off and then propose effective methods to split big hot areas into clusters and identify a location in each cluster as a candidate bus stop. In the second phase, given the bus route origin, destination, candidate bus stops, and bus operation time constraints, we derive several effective rules to build the bus route graph and prune invalid stops and edges iteratively. Based on this graph, we further develop a bidirectional probability-based spreading algorithm to generate candidate bus routes automatically. We finally select the best bidirectional bus route, which expects the maximum number of passengers under the given conditions and constraints. To validate the effectiveness of the proposed approach, extensive empirical studies are performed on a real-world taxi GPS data set, which contains more than 1.57 million night passenger delivery trips, generated by 7600 taxis in a month. <s> BIB002
Here we discuss a very interesting case study-based approach presented in BIB002 . The reason we separate this approach from above presented strategies is because; (1) the authors present a very interesting case study for routing the night buses, and (2) the real-time data of various taxies is taken to plan the routes (which was missing in the strategies presented in above subsection). Moreover, buses are considered as one of the cheapest ways of traveling, therefore, providing automated routes to bus drivers as well as real-time information to passengers on their smartphones or similar devices would be a huge benefit to modern society. By considering the above, Chen et al. BIB002 divide the night buses routing problem into two subproblems: the candidate bus stop identification and the best bidirectional bus route selection. To address the former, whole city is divided into equal sized small grids where each cell is 10 X 10 meters. Then, the cells with highest PDR (pick-up and drop-off rate) are combined to form a big cluster which is later divided into small sized clusters each having a principle bus station which is at a walking distance for a user within the specified cluster. A cluster merging algorithm is also presented allowing a big VOLUME 6, 2018 cluster to merge nearby small clusters if their distance is not greater than a certain limit (i.e., if the absorbed cluster is not too far). For bus route selection, the authors propose a graph theory based three-step process as follows: • Build the graph with bus route and remove unnecessary nodes and edges. This process requires certain proposed criteria to be met such as the maximum distance between two stops is not too high (and is adequate), the bus should always move forward (farther) from the origin and close to destination, and the zigzag routes should be avoided ensuring the smoothness of the routes. Heuristics-based mathematical equations are also provided for each criterion. • The information about the bus and its passengers is recorded in two different matrices known as Time and Flow matrices, respectively. Each element in time matrix represents the bus travel time from one stop to • another. Likewise, each entry of Flow matrix corresponds to the number of passengers. • Based on above two factors, the authors propose probability algorithm that generates best/optimal route for the passengers. The algorithm selects routes with large number of passengers and less distance. Similar sort of algorithm can also be found in BIB001 . All the theoretical aspects of BIB002 are supported by extensive set of experimental results conducted in MATLAB on real-time SBD considering thousands of taxis in Hangzhou, China over a period of one month. Interesting graphical illustrations are presented showing the convergence of proposed algorithm, optimal route selection based on less number of stops, direct relationship between number of stops, and the total traveling time for the buses. The results are compared to the algorithm proposed in BIB001 reflecting that the proposed algorithm converges to an optimal value.