LPSQ: Achieving Efficient and Privacy-Preserving Location-Point-Set Similarity Range Query for Cloud Computing

作者：Shan-Ling Jiang, Haiyong Bao, Da-Qi Li, Jing Wang, Qinglei Kong, Cheng Huang, Hong-ning Dai · 发表于：IEEE Transactions on Cloud Computing · 年份：2026 · DOI：10.1109/tcc.2025.3628970 · 研究领域：Computer Science

Location point set similarity range query aims to retrieve candidate point sets that are similar to the given point set in terms of location distribution patterns and geographical features, and it is vital in GIS (Geographic Information Systems), IoT (Internet of Things), and biometrics. Due to the economic and flexible advantages of cloud services, location data is frequently outsourced to cloud servers, which simultaneously increases the risk of privacy breaches. To address this, service providers choose to encrypt data before outsourcing. However, the existing schemes for similarity range query of encrypted location point sets have some problems, such as high computational complexity of measurements, which limit the query efficiency and security of schemes. To tackle these problems, this paper achieves the efficient and privacy-preserving location-point-set similarity range query for cloud computing (LPSQ). Firstly, we propose a lightweight similarity measurement called Geo-Jaccard similarity, to reduce the time complexity to $O(n)$ O ( n ) . Secondly, to enhance the efficiency of the scheme, we integrate the kd-tree with pivot point technology to construct a pkd-tree, and design a corresponding filtering and verification algorithm. Thirdly, to enhance the security of our scheme, we encrypt the pkd-tree using a mix of matrix encryption and SHE (Symmetric Homomorphic Encryption), and design a series of protocols under SHE, such as SHE batch minimum value calcu...