大数据安全与隐私 - Lab2 - 数据安全检索

实验环境准备

利用 pcl 库中的模块来实现 K-D Tree。

1. 安装 pcl 库。

brew install pcl

2. Cmake 相关配置。

   cd ./test
   touch CMakeLists.txt

   CmakeLists.txt：

   cmake_minimum_required(VERSION 2.6 FATAL_ERROR) # 选择cmake版本
   project(PCLtest) # 给工程命名
   find_package(PCL REQUIRED) 
   include_directories(${PCL_INCLUDE_DIRS})
   link_directories(${PCL_LIBRARY_DIRS})
   add_definitions(${PCL_DEFINITIONS})
   add_executable(PCLtest main.cpp)
   target_link_libraries(PCLtest ${PCL_LIBRARIES})

3. test：

main.cpp: 实验源代码。

mkdir build && cd ./build
cmake ..
make
./PCLtest

安全查询的实现：保序加密（分段映射）

1. 定点数转换：将小数转换为定点数。为了保留小数点后的6位精度，代码将原始的浮点数乘以1e6，将其转化为整数。这样可以确保在段内的随机化不会造成显著的精度损失。同时，分段数目也影响着精度。

2. 分段计算：计算原始整数值所属的分段。分段是基于整数值与分段大小的比率计算的。

3. 随机化：在分段内加入随机偏移，增加保序加密的安全性。这样，虽然数据的顺序保持，但值本身有一定的随机性。因为随机偏移的原因，解密的值和加密前的值可能略有不同。这种保序加密通常用于需要顺序查询但同时又需要保持一定随机性和安全性的场景。本质是一种近似的安全查询。

K-D Tree

k-D Tree 是一种可以高效处理 $k$ 维空间信息的数据结构。可应用于多维空间数据的范围搜索和最近邻搜索。

最近邻搜索

由于 K-D Tree 的性质，通过二叉搜索可以很快找到最邻近的近似点，但最邻近肯定距离查询点更近，应该位于以查询点为圆心且通过叶子节点的圆域内。

为了找到真正的最近邻需进行 回溯 操作：算法沿搜索路径反向查找是否有距离查询点更近的数据点。回溯的过程中，判断在该父节点的其他子节点空间中是否有距离查询点更近的数据点。

即以查询点为圆心，以查询点到最邻近的近似点的距离为半径，画圆。若发现该圆并不和某平面相交，则代表不用进入该父节点的右子空间中去搜索。