Method of and server for generating parking suggestions to be displayed on an electronic device
A method and a server for determining parking suggestions for a destination location on a map comprising: acquiring based on the destination location, a set of past routes having been taken on the map by users and terminating at the destination location. A set of final locations associated with the set of past routes is determined, each final location being an actual ending location of users having taken the respective past route. A road graph including a set of map objects is acquired, where each map object has: a respective object location, a respective object class indicative of a respective type of structure on the map. The set of final locations is then clustered based on the destination location, the respective classes and the respective final locations to obtain a set of clusters on the road graph, where each cluster includes a respective subset of final locations.
1. A computer-implemented method for determining parking suggestions for a given destination location on a map, the parking suggestions being displayable on the map, the map being displayable on an electronic device, the method executable by a server, the server being connectable to the electronic device and to a database, the server executing a clustering algorithm, the method comprising:
acquiring, from the database, based on the given destination location, a set of past routes having been taken on the map by users associated with respective electronic devices, each respective past route of the set of past routes terminating at the given destination location;
determining, by the server, a set of final locations associated with the set of past routes, each final location being an actual ending location of at least one respective user of a respective electronic device having taken the respective past route to the given destination location on the map, each final location being a candidate parking suggestion;
acquiring, from the database, a road graph of the map, the road graph including a set of map objects, each map object having:
a respective object location, and
a respective object class, the respective object class being indicative of a respective type of structure on the map;
clustering, by the server, the set of final locations to obtain a set of clusters, each cluster including a respective subset of final locations, each cluster of at least a portion of the set of clusters being associated with at least one map object and the associated respective object location, the clustering being based on:
the given destination location,
the respective final locations,
the respective object locations, and
the respective classes of the respective map objects;
receiving, from the electronic device, a request for a current route to the given destination location, the request including an indication of a starting location;
determining, by the server, a current route on the map from the starting location to the given destination location and at least one cluster including a respective subset of final locations as a parking suggestion for the given destination location; and
transmitting, to the electronic device, the current route, the current route including the parking suggestion.
2. The method of claim 1 , wherein the determining the set of final locations is based on a respective distance between each final location and the given destination location being below a predetermined threshold.
3. The method of claim 2 , wherein
the respective object class is indicative of a level of hierarchy of the respective map object on the road graph; and wherein
the clustering is executed in a hierarchical manner.
4. The method of claim 3 , wherein
each cluster has a respective centroid and a respective size; and wherein
the determining the at least one cluster including the respective subset of final locations as the parking suggestion is based on the respective centroid and the respective size of the at least one cluster.
5. The method of claim 4 , wherein the clustering is performed by using a heuristic evaluation function.
6. The method of claim 5 , wherein the clustering algorithm is based on Kruskal's algorithm.
7. The method of claim 6 , wherein the set of clusters has a predetermined number of clusters.
8. The method of claim 2 , wherein
each past route is associated with a respective period of time spent by the at least one user of the respective electronic device at the final location; and wherein
the determining the set of final locations is further based on the period of time being above a predetermined time threshold.
9. The method of claim 6 , wherein the method further comprises, prior to the clustering: associating, by the server, each final location of at least a portion of the set of final locations with at least one map object based on a respective distance between the final location and the at least one respective object location associated with each of the at least one map object.
10. The method of claim 7 , wherein the respective object class is one of:
a road segment,
a roadblock, and
a known parking location.
11. The method of claim 10 , wherein the road segment class includes one of: a freeway, an arterial road, a collector road, and a local road.
12. A server for determining parking suggestions for a given destination location on a map, the parking suggestions being displayable on the map, the map being displayable on an electronic device connected to the server, the server being connected to a database, the server comprising:
a processor;
a non-transitory computer-readable medium comprising instructions;
the processor, upon executing the instructions, being configured to:
acquire, from the database, based on the given destination location, a set of past routes having been taken on the map by users associated with respective electronic devices, each respective past route of the set of past routes terminating at the given destination location;
determine a set of final locations associated with the set of past routes, each final location being an actual ending location of at least one respective user of a respective electronic device having taken the respective past route to the given destination location on the map, each final location being a candidate parking suggestion;
acquire, from the database, a road graph of the map, the road graph including a set of map objects, each map object having:
a respective object location, and
a respective object class, the respective object class being indicative of a respective type of structure on the map;
cluster the set of final locations to obtain a set of clusters, each cluster including a respective subset of final locations, each cluster of at least a portion of the set of clusters being associated with at least one map object and the associated respective object location, the clustering being based on:
the given destination location,
the respective final locations,
the respective object locations, and
the respective classes of the respective map objects;
receive, from the electronic device, a request for a current route to the given destination location, the request including an indication of a starting location;
determine a current route on the map from the starting location to the given destination location and at least one cluster including a respective subset of final locations as a parking suggestion for the given destination location;
transmit, to the electronic device, the current route, the current route including the parking suggestion.
13. The server of claim 12 , wherein the determining the set of final locations is based on a respective distance between each final location and the given destination location being below a predetermined threshold.
14. The server of claim 13 , wherein
the respective object class is indicative of a level of hierarchy of the respective map object on the road graph; and wherein
the clustering is executed in a hierarchical manner.
15. The server of claim 14 , wherein
each cluster has a respective centroid and a respective size; and wherein
the determining the at least one cluster including the respective subset of final locations as the parking suggestion is based on the respective centroid and the respective size of the at least one cluster.
16. The server of claim 15 , wherein the clustering is performed by using a heuristic evaluation function.
17. The server of claim 16 , wherein the clustering algorithm is based on Kruskal's algorithm.
18. The server of claim 17 , wherein the set of clusters has a predetermined number of clusters.
19. The server of claim 13 , wherein
each past route is associated with a respective period of time spent by the at least one user of the respective electronic device at the final location; and wherein
the determining the set of final locations is further based on the period of time being above a predetermined time threshold.
20. The server of claim 17 , wherein the processor is further configured to, prior to the clustering:
associate each final location of at least a portion of the set of final locations with at least one map object based on a respective distance between the final location and the at least one respective object location associated with each of the at least one map object.