Constructing Top-k Routes with Personalized Submodular Maximization of POI (point of interest) Features
| Graph | Route1 | Route2 |
|---|---|---|
 |
 |
 |
| Route3 | Route4 | Route5 |
 |
 |
 |
We are given a collection of POIs (points of interest) with rated features and travelling costs between points. User wants to find top k routes from start to destination points, that maximally satisfy feature preferences and it's cost is not bigger than cost budget.
| Graph1 | Graph2 | Graph3 |
|---|---|---|
 |
 |
|
All data was generated in random way. Number of POIs is in range from 5 to 8 and every edge has weights from 5 to 100.
Feature vectors for every POI are generated of size from 2 to 4.
User request is also generated by picking random source and destination points, cost budget and preference vector.
| Graph1 | Route1 |
|---|---|
|
 |
| Route2 | Route3 |
 |
 |
| Route4 | Route5 |
 |
 |
| Graph2 | Route1 |
|---|---|
|
 |
| Route2 | Route3 |
 |
 |
| Route4 | Route5 |
 |
 |
| Graph3 | Route1 |
|---|---|
|
|
| Route2 | Route3 |
|
|
| Route4 | Route5 |
|
|
PACER returns priority queue with routes, which maximally satisfy user requirements for given graph. In priority queue routes are ordered by gain. Gain is a value that indicates proximity of features of nodes on route to user preference.
As we can see from these plots, best route has the highest gain but not the smallest cost. Routes are chosen such that they pass POIs with, the the closest to required by user preference vector, feature vectors, such that cost of such route is not higher than travel budget.