The Maximum Trajectory Coverage Query in Spatial Databases

Mohammed Eunus Ali, Shadman Saqib Eusuf, Kaysar Abdullah�Bangladesh University of Engineering and Technology (BUET), Bangladesh��Farhana M. Choudhury�RMIT University & University of Melbourne, Australia�J. Shane Culpepper�RMIT University, Australia �Timos Sellis� Swinburne University of Technology, Australia

• Availability of Huge Amount of Trajectory Data
• Bikely users can share their cycling routes from GPS devices ¹
• A user can add points on the route where the course is changed (i.e. waypoints) in GPS-wayPoints²
• In Microsoft GeoLife users can share travel routes GPS trajectories ³
• Using Uber, 15 million trips/day are completed on average ⁴

2

Motivation

¹ http://www.bikely.com ² http://gpswaypoints.net

³ https://research.microsoft.com/en-us/projects/geolife/ ⁴ https://techjury.net/stats-about/uber/

How can we utilize this massive amount of trajectory data??

• Improving Public Transport
• Designing Ad-hoc Transport
• Tour Planning
• Ridesharing

... and many more applications

3

Motivation

Which routes should the vehicles take?

Tour/Transport Operator

We introduce 2 new queries in spatial database, namely kBFT and kBCovFT to support all these applications!!

• Given
• A set of user trajectories, U
• A set of facility trajectories, F
• A positive integer, k
• A service evaluation function
• A kBFT query returns top-k�facilities from F which have�individually higher service�values than the other facilities

4

k-Best Facility Trajectory Search (kBFT)

• Total 3 facilities: 65, 46, 25/34 & 12 user trajectories: u₁… u₁₂
• Facility 46 serves 4 users. Facility 25/34 and 65 serves 3 and 2 users respectively
• For k=1, kBFT will return Facility 46

• Variant of kBFT
• kBCovFT query returns best k�facilities from a set of facilities,�F which combinedly have higher�service value than that of other�such subsets of k facilities
• Multiple facilities may be�needed to serve a user

​

5

k-Best Coverage Facility Trajectory Search (kBCovFT)

• For k=2, kBCovFT will return {Facility 46 , Facility 65}
• Facility {46, 65} serves 8 users (u₅… u₁₂), other pairs can serve 7 and 5 users
• u₁₀, u₁₁ cannot be served by a single facility, but {46, 65} can jointly serve them

• Route/Trip Planning (TP) ¹
• Recommending route based on mobility pattern
• Trajectory Search by Point Location ²
• Finding k nearest trajectories from a set of query points
• Facility Location Selection Problem (FLP) ³
• Reverse kNN Trajectory Queries (RkNN) ⁴
• Selecting one of k nearest facility trajectories wrt given user trajectories

6

Related Work

¹ Chen et al. 2013, 2011, Wang et al. 2017 ² Han et al. 2014, Tang et al. 2011

³ Chen et al. 2013, Du et al. 2005, Wong et al. 2009, Xiao et al. 2011, Zhou et al. 2011

⁴ Wang et al. 2017, Rahat et al. 2018

• A New Class of Trajectory Queries
• kBFT
• kBCovFT
• A Novel Two Level Index Structure
• Trajectory Quadtree (TQ-tree)
• Z-ordering
• Efficient Divide and Conquer Approach
• Two Phase Pruning
• Incorporation with a Best-First Search Technique

7

Major Contributions

• Storing Trajectories with Similar Orientation Together
• We need to find co-located trajectories quickly
• We want to organize trajectories of different lengths suitably
• Evaluating Service Value
• A user can be partially served by a facility
• A user can be served by multiple facilities, so served segments of trajectories need to be traced
• A user may change facilities several times (i.e. several hops) to achieve a higher service value in kBCovFT query

8

Challenges

• Trajectory Indexing
• Trajectories with spatial locality are grouped and stored together
• Trajectories stored together are indexed using z-curve
• Algorithm
• Facility trajectories are recursively divided to prune TQ-tree nodes
• Only trajectories at relevant nodes are retrieved based on z-ordering
• A priority queue of states of facilities is maintained and updated to answer kBFT
• kBFT solution method is used in the greedy approach of kBCovFT

9

Key Ideas

• User Trajectories

10

Trajectory Quadtree (TQ-tree)

• Quadtree Structure to Partition Space

11

Trajectory Quadtree (TQ-tree)

• Quadtree Structure to Partition Space (2^nd Level)

12

Trajectory Quadtree (TQ-tree)

• TQ Tree Node Structure

13

Trajectory Quadtree (TQ-tree)

Upper bound of service value e.g. total number of trajectories under this TQ-tree node

Inter-node trajectories

• Z-ordered Inter-node Trajectory List

​

​

​

​

​

• Single node with all trajectories under it
• Z-ordering of the start points of the inter node trajectories
• Z-ordering of the end points of the inter node trajectories
• Inter-node trajectories in z-ordered buckets:

​

14

Trajectory Quadtree (TQ-tree)

• Idea
• Apply a best-first technique with divide and conquer approach
• Explore facilities based on service value upper bounds
• Maintain a max priority queue of facility exploration entities
• Key Observation: Many facilities need not to be fully explored
• Steps
• A max priority queue is initialized with unexplored states of facilities
• State at top is relaxed & reinserted until k facilities are fully explored

# Service value for inter-node trajectories is calculated in divide and conquer method

# Exploration state is updated with child Q-nodes and relevant portions of the facility

15

Processing kBFT

• Input: Facility graph, f & TQ-tree node Q ; Output: Service value
• Steps

​

​

​

​

​

• Recursive calls with children of Q and corresponding portions of f
• Evaluation of service value of f for the inter-node trajectories of Q

# Pruning based on z-id and distance(euclidean/road network) threshold checking

• Termination if f is empty or leaf is reached

16

Divide and Conquer: Service Evaluation

• Two-Phase Greedy Method
• Initial filtering heuristic based on kBFT solution

# Choosing a moderately larger pool of trajectories using kBFT solution e.g. if k=4, 16 or 8 individually best facilities may be chosen

• Greedy facility selection

# Calculating service value of the facilities and picking the best among remaining ones

# Repeating the process until k facilities are chosen

• Quality of Solution
• Proof of non-submodularity of the service value function
• Calculation of approximation ratio

17

Processing kBCovFT

• Datasets
• User trajectory dataset: Point to point - NY Taxi-trips (1,032,637), multipoint - NY Foursquare (212,751), Beijing Geolife (30,266)
• Bus route dataset: NY, Beijing bus routes
• Parameters

​

​

​

* red color indicates default value

• Performance Comparison
• BL (Baseline): Trajectory retrieved with range query, no TQ-tree indexing
• TQ(B): Only TQ-tree indexing; TQ(Z): Z-ordering with TQ-tree

18

Experimental Setup

19

Effect of No. of Trajectories

• TQ(Z) is on average 2 orders of magnitude faster than TQ(B)
• TQ(B) is 1 order of magnitude faster than the baseline
• TQ(Z) takes 2 orders of magnitude less I/O than the TQ(B)

20

Effect of No. of Facilities

• TQ(Z) is 3 orders of magnitude faster than the baseline
• TQ(Z) takes 2 orders of magnitude less I/O than the TQ(B)

• Introduced a Pair of New Trajectory Queries
• Proposed an Efficient Two Level Index Structure
• Presented a Divide and Conquer Based Solution for the 1^st Query
• Devised a Two-step Greedy Approximation Algorithm for the 2^nd Query
• Conducted Experiments Extensively to Validate the Claims
• Discussed Generalization and Extensions of Proposed Approaches to Multipoint Trajectories and Temporal Domain

21

Summary

Thank You ☺