Novel approach uses frequent pattern mining to identify most popular routes in lieu of shortest routes to reach a destination.
Every time we use an application like say, Google Maps to find the quickest way of getting to a destination, what kicks in is the shortest path algorithm. However, in some situations, the shortest path may not necessarily be the most preferred one for travellers. This is because despite covering a lesser distance to get from point A to B, the shortest path may have several issues such as a narrow road, bad road condition, ill-illumination, rendering it unsafe and so on. These factors lead to a preference of longer routes over shortest paths.
User Preferences Of Routes
Prof. P. Krishna Reddy at the International Institute of Information Technology Hyderabad and his student researcher P. Revanth Rathan set out to investigate how to extract the most popular path instead of the shortest path for source-destination queries within an acceptable response time. In a research paper titled, “A framework for discovering popular paths using transactional modelling and pattern mining’, the duo has proposed a new framework for ranking paths based on their popularity keeping in mind dynamic traffic conditions. “Typically the extent of preference of one route over another reveals the popularity of the chosen route,” says Revanth, explaining that they have captured this popularity by modelling the number of users traversing a given path. According to him, popularity of a chosen route is dependent on the infrastructure it boasts of, such as cafes and restaurants that fall on the way or if it is a pot-hole-free road and so on. This explains why one would choose a slightly longer route versus a shorter one in getting to a destination. The team’s research deals with efficient discovery of such routes that are more preferred by users.
Frequent Patterns
What sets this work apart from existing research on determining popularity of paths is that the IIITH group modelled the popularity metric based on user preferences by extending the model of frequent patterns. Employing the notion of frequent pattens makes the framework scalable. It essentially means that If more number of users traverse a path, that path is labelled as popular and the paths are then ranked based on this metric. Unlike other similar works, for computing the metric, the team also considered cases where a path with different edges has users taking a detour along one of the edges and returning via another edge. By considering the real graph data of the city of Beijing, they demonstrated that the most popular paths are in effect only slightly longer than the shortest paths.
Timestamp Data: A Way Ahead
An advancement of this work making frequent pattern mining even more relevant is if the road traversal data is available with corresponding timestamps recorded with it. “There are differences in user preferences of certain routes based on the time. For instance, people would prefer a path that is well-lit at night and choose it over a shorter route that lacks street lights,” explains Revanth. Such data would be immensely helpful in finding most popular paths based on the time of the day. “While travelling or commuting, people choose one route over another due to several http://theshoalspharmacy.com reasons, including the condition of the road and other interesting features of the road such as good hotels, point of interest and so on. So, recommending the popular paths with the proposed framework improves safety and security of the travel in addition to improving travel experience. The trade-off is that the user has to travel a little longer but it is worth it considering the other advantages the popular path affords”, says Prof. P. Krishna Reddy.
Next post