基于位置服务的近邻检测算法研究

发布时间：2018-05-05 12:28

本文选题：LBS + 近邻检测　；参考：《北京交通大学》2017年硕士论文

【摘要】：近邻检测是基于位置服务LBS(Location Based Service)中的重要功能,能够搜寻附近用户,该功能广泛应用于社交、商业、军事等各领域。现如今人们在享受位置服务的同时也更加重视隐私保护。由于近邻检测中搜寻附近好友的原理是基于对用户的定位,因此很容易涉及到位置信息等隐私的泄漏。因此多数近邻检测算法为保护隐私而大大增加了算法的时间复杂度,影响了检测效率。本文的研究目的是在保护用户位置隐私的前提下提高近邻检测算法的效率,提高服务的实用性。本文利用欧氏空间在LBS中能够模拟在时空数据库的实际情况且方便理论论证的优点,提出了欧式空间和公路网络模型下的近邻检测算法。本文综合考虑了欧氏空间和公路网络两种距离模型在理想环境和实际应用中相互结合的特点,发挥其各自优势。另外,本文最大程度地实现了用户位置隐私的保护。首先利用欧式空间的特点提出了基于隐私保护的近邻检测算法。该算法对被检测对象进行基于欧式空间的匿名方式处理从而保护其位置隐私,此外通过构造Voronoi单元对检测区域进行分割,且对可能结果集进行条件筛选来缩小检测的区域,从而提高了检测效率。之后通过仿真实验的具体数据对该算法与传统的近邻检测算法,就检测准确率、耗时情况等各项性能进行了对比。结果表明该算法在检测效率方面优于传统近邻检测算法,且能够有效地保护被检测对象的位置隐私。然后在此算法基础之上,针对公路网络能够更有效模拟实际对象的空间位置关系的特点,提出了基于隐私保护的公路网络近邻检测算法,对被检测对象进行基于公路网络的匿名方式处理防止隐私泄露。该算法通过扩展圆对二维检测平面进行分割,根据被检测对象在子区域中的分布情况进行筛选,再将被检测对象是其最近邻点的可能性值与既定阈值进行比较进一步过滤,最终检测出近邻点。此外通过仿真实验对该算法进行了数据测试,并且将结果与欧式空间近邻检测算法的性能进行对比,发现公路网络算法在效率和精确率方面都具有更好的优势。以上两种算法均较为有效地实现了检测对象的位置隐私保护。
[Abstract]:Nearest neighbor detection is an important function of location based LBS(Location Based Service, which can search nearby users. It is widely used in social, commercial, military and other fields. Nowadays, people pay more attention to privacy while enjoying location services. Because the principle of searching for close friends in nearest neighbor detection is based on the location of the user, it is easy to leak the privacy such as location information. Therefore, most nearest neighbor detection algorithms greatly increase the time complexity and affect the detection efficiency in order to protect privacy. The purpose of this paper is to improve the efficiency of nearest neighbor detection algorithm and improve the practicability of service under the premise of protecting user location privacy. Based on the advantage of Euclidean space being able to simulate the actual situation in spatio-temporal database in LBS and convenient for theoretical argumentation, this paper presents an algorithm for nearest neighbor detection in Euclidean space and highway network model. In this paper, the characteristics of Euclidean space and highway network models are considered, which are combined in ideal environment and practical application, and their respective advantages are brought into play. In addition, this paper maximizes the protection of user location privacy. Firstly, a privacy protection based nearest neighbor detection algorithm is proposed based on the characteristics of Euclidean space. In order to protect the privacy of the detected object, the detected object is processed anonymously based on Euclidean space. In addition, the detected region is segmented by constructing a Voronoi unit, and the detected region is reduced by conditional filtering of the possible result set. Thus, the detection efficiency is improved. Then the performance of the algorithm is compared with that of the traditional nearest neighbor detection algorithm, such as detection accuracy, time consuming and so on. The results show that the proposed algorithm is superior to the traditional nearest neighbor detection algorithm in detection efficiency and can effectively protect the location privacy of the object under detection. On the basis of this algorithm, aiming at the characteristic that highway network can more effectively simulate the spatial position relationship of real objects, a privacy protection based nearest neighbor detection algorithm for highway network is proposed. The detected object is treated anonymously based on highway network to prevent privacy disclosure. In this algorithm, the two-dimensional detection plane is segmented by extending the circle, and then the probability value of the nearest neighbor of the detected object is filtered further by comparing the probability value of the detected object with the established threshold value according to the distribution of the detected object in the sub-region. Finally, the nearest neighbor point is detected. In addition, the algorithm is tested by simulation, and compared with the performance of Euclidean spatial nearest neighbor detection algorithm, it is found that the highway network algorithm has better efficiency and accuracy. The above two algorithms can effectively protect the location privacy of the detected object.
【学位授予单位】：北京交通大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：TN929.5

【参考文献】