Backward Path Growth for Efficient Mobile Sequential Recommendation

Huang, Jianbin; Huangfu, Xuejun; Sun, Heli; Li, Hui; Zhao, Peixiang; Cheng, Hong; Song, Qinbao · 2014 · OpenAlex-citations

DOI: 10.1109/tkde.2014.2298012

archive: archived pipeline: cataloged verified

Get this paper ↗ (DOI — opens at the source; we link to it, we don't host it)

Summary

This paper addresses the Mobile Sequential Recommendation (MSR) problem, which involves suggesting an optimal driving route for an empty taxi to connect a sequence of high-probability pick-up points, thereby minimizing the expected travel distance (cost) before securing a passenger. The primary motivation is the high computational complexity of existing methods, which struggle to handle large sets of pick-up points or flexible route length constraints. While previous approaches like LCP and SkyRoute rely on monotone properties for pruning, their time and space complexities grow exponentially, limiting their applicability to small datasets or fixed-length routes. This work proposes a generalized MSR solution that supports arbitrary length ranges ($L_{min}$ to $L_{max}$) and significantly improves efficiency through a novel backward path growth algorithm. The proposed method employs a two-stage framework: offline pre-processing and online search. The core innovation lies in identifying the iterative property of the Potential Travel Distance (PTD) function, which allows for the recursive calculation of route costs. Specifically, the authors derive a backward recursive formula where the PTD sub-function of a sequence can be computed from its postfix sub-sequence. This enables the incremental construction of potential sequences from the terminal point backward to the start. During the offline stage, a backward incremental sequence generation algorithm builds these candidates while applying an incremental pruning policy to remove non-optimal sequences early. Additionally, a batch pruning algorithm is used to eliminate suboptimal sequences of specific lengths. The online stage then selects the optimal route for a taxi’s current position using the pre-computed candidates. Experimental results on both real and synthetic datasets demonstrate that the proposed method significantly outperforms state-of-the-art algorithms in terms of pruning efficiency and search speed. The incremental and batch pruning strategies effectively reduce the search space, allowing the system to handle a larger number of pick-up points and arbitrary length constraints that were previously computationally prohibitive. The recursive nature of the PTD calculation ensures that costs are not computed from scratch for every route, further enhancing performance. The significance of this work lies in its ability to make mobile sequential recommendation scalable and practical for real-world applications. By decoupling the heavy computational load into an offline phase and leveraging the iterative properties of the cost function, the method enables real-time route suggestions for taxi drivers with minimal latency. This approach not only reduces fuel consumption and traffic congestion by optimizing empty cruising but also provides a robust framework for similar trajectory-based recommendation problems, such as tourist route planning or parking spot search, where flexible length constraints and large candidate sets are common.

Provenance

The full processing record for this entry. Every stage of this paper's journey through the pipeline is logged — what ran, with which tool and model, how many attempts it took, and when it last completed.

Summary generated by qwen3.6-27b-prismaquant on 2026-06-26; verification: verified.

Topics

Ranked by relevance to this paper. Hover a topic for its definition.

• telematics crash prediction