Ensuring travelers' safety on roads has become a research challenge in recent years. We introduce a novel safe route planning problem and develop an efficient solution to ensure the travelers' safety on roads. Though few research attempts have been made in this regard, all of them assume that people share their sensitive travel experiences with a centralized entity for finding the safest routes, which is not ideal in practice for privacy reasons. Furthermore, existing works formulate safe route planning in ways that do not meet a traveler's need for safe travel on roads. Our approach finds the safest routes within a user-specified distance threshold based on the personalized travel experience of the knowledgeable crowd without involving any centralized computation. We develop a privacy-preserving model to quantify the travel experience of a user into personalized safety scores. Our algorithms for finding the safest route further enhance user privacy by minimizing the exposure of personalized safety scores with others. Our safe route planner can find the safest routes for individuals and groups by considering both a fixed and a set of flexible destination locations. Extensive experiments using real datasets show that our approach finds the safest route in seconds. Compared to the direct algorithm, our iterative algorithm requires 47% less exposure of personalized safety scores.
翻译:近些年来,确保旅行者在公路上的安全已成为一项研究挑战。我们引入了一个新的安全路线规划问题,并制定了确保旅行者在公路上安全的高效解决方案。尽管在这方面进行了很少的研究尝试,但所有这些尝试都假定,人们与一个中央实体分享其敏感的旅行经验,以寻找最安全的路线,实际上由于隐私原因并不理想。此外,现有的工程制定安全路线规划的方式不符合旅行者在公路上安全旅行的需要。我们的方法在用户指定的距离门槛内找到最安全的路线,其依据是有知识的人群的个人化旅行经验,而不涉及任何集中计算。我们开发了一个隐私保护模式,将用户的旅行经验量化为个性化安全分数。我们寻找最安全的路线的算法通过尽量减少个人化安全分数与其他人接触的机会,进一步加强了用户的隐私。我们的安全路线规划员可以找到个人和群体最安全的路线,既考虑固定地点,也考虑一套灵活的目的地地点。使用实际数据集进行的广泛实验表明,我们的方法在几秒钟内找到最安全的路线。与直接算法相比,我们的迭代算法要求更少的个人安全分。