CN108829804B 基于距离划分树的高维数据相似性连接查询方法及装置 （洛阳师范学院）

号US2016378809A1,2016.12.29基于距离划分树的高维数据相似性连接查本发明实施例提供一种基于距离划分树的算候选相似节点对集合中各候选相似节点对包2映射模块，用于获取所有待查询的高维的原始数据，并将所述原距离划分树构建模块，用于根据预设的第一距离阈值及卡方候选相似节点对集合获取模块，用于遍历所述距离划分树，并对所从所述原始数据中随机获取原始数据子集，根据所述原始数据子集构建对若所述初始距离划分树中的第一层最左边子节点的编号大于1，则生成一个虚拟子节在所述初始距离划分树中的第一层最右边生若判断获知所述初始距离划分树中的第一层的所述子节点的将所述原始数据子集映射到一维空间，并根据所述第二距离阈值计算各原始数据子集在所述一维空间的映射值π1(vi)，若判断获知所述子节点中所述原始数据子集的个数大于预设距离划分树节点的数据结构为：在距离划分树中每一个节点，34[0004]相似性查询是一种应用广泛的重要操作，目前有很多血[0010]计算所述候选相似节点对集合中各候选相似节点对包括的原始数据之间的原始5[0021]若所述初始距离划分树中的第一层最左边子节点的编号大于1，则生成一个虚拟[0033]若判断获知叶子节点Ni的距离范围下界与叶子节点Nj的距离范围6[0051]若所述初始距离划分树中的第一层最左边子节点的编号大于1，则生成一个虚拟7[0068]图1为本发明实施例提供的基于距离划分树的高维数据相似性连接查询方法流程[0071]图4为本发明实施例提供的基于距离划分树的高维数据相似性连接查询装置结构此处附图中描述和示出的本发明实施例的组件可以以各种不同的配置来布置和设计。因8[0075]图1为本发明实施例提供的基于距离划分树的高维数据相似性连接查询方法流程[0076]步骤101：获取所有待查询的高维的原始数据，并将所述原始数据映射到一维空[0078]应当说明的是，高维数据相似性连接查询(High-DimensionalDataSimilarityi一维空间中的所述原始数据和所述第二距离阈值构[0083]在具体的实施过程中，根据预先设定的第一距离阈值ε及卡方分布性质可以确定ij)>ε)>1-P(χ2>k2)。根据一维空间中的原始数据和第二距离阈值构建距离维映射空间中新的距离阈值ε'＝kε为单位进行划分，将原高维数据划分到等宽的9[0087]步骤104：计算所述候选相似节点对集合中各候选相似节点对包括的原始数据之(包括父亲节点和叶子节点)，都包含有该节点所在level，层内编号orderNo，数据个数数据在一维映射空间对应的子节点的编号pid-「m,(v,)lkel,如果编号为pid的子节点不当说明的是，通过所在层次level可以计算出当前层次中每个节点对应的距离宽度为：[0102]若所述初始距离划分树中的第一层最左边子节点的编号大于1，则生成一个虚拟[0111]在上述实施例的基础上，所述根据所述原始数据子集构建对应的初始距离划分对应的映射值计算出每个原始数据在一维映射空间对应的子节点的编号[0122]若判断获知叶子节点Ni的距离范围下界与叶子节点Nj的距离范围界减Ni的距离范围上界的结果小于或等于第二距离阈值，则节点Ni中的数据与节点Nj中的[0127]在上述各实施例的基础上，所述将所述原始距离与所述[0129]在具体的实施过程中，根据公式(1)可以计算每一个候选数据对中两个原始数据[0134]图4为本发明实施例提供的基于距离划分树的高维数据相似性连接查询装置结构[0135]映射模块401用于获取所有待查询的高维的原始数据，并将所述原始数据映射到一维空间；距离划分树构建模块402用于根据预设的第一距离阈值及卡方分布性质确定第二距离阈值，根据所述一维空间中的所述原始数据和所述第二距离阈值构建距离划分树；候选相似节点对集合获取模块403用于遍历所述距离划分树，并对所述距离划分树中的各划分树构建模块402根据预先设定的第一距离阈值ε及卡方分布性质可以确定出第二距离阈值kε,根据一维空间中的原始数据和第二距离阈值构建距离划分树。候选相似节点对集[0148]若所述初始距离划分树中的第一层最左边子节点的编号大于1，则生成一个虚拟装置501包括至少一个可以软件或固件(firmware)的形式存储于所述存储器502中或固化[0161]其中，存储器502可以是，但不限于，随机存取存储器(RandomAccessMemor本发明实施例任一实施例揭示的流过程定义的服务器所执行的方法可以应用于处理器504以是通用处理器，包括中央处理器(CentralProcessingUnit，简称CPU)、网络处理器可以是微处理器或者该处理器504也可以是任何常规[0164]输入输出单元506用于提供给用户输入数据实现用户与所述服务器(或本地终端)[0166]显示单元508在所述电子设备与用户之间提供一个交互界面(例如用户操作界面)[0168]输入输出单元506用于提供给用户输入数据实现用户与处理终端的交互。所述输显示了根据本发明的多个实施例的装置、方法和计算机程序产品的可能实现的体系架构、[0171]另外，在本发