[發明專利]一種高維空間的近似最近鄰查詢系統

在審

• 申請號: 202310366005.5
• 申請日: 2023-04-07
• 公開（公告）號: CN116401279A
• 公開（公告）日: 2023-07-07
• 發明（設計）人: 黎玲利;姜佩杰
• 申請（專利權）人: 黑龍江大學
• 主分類號: G06F16/2455
• 分類號: G06F16/2455;G06F16/22;G06F16/28;G06F18/2135;G06F18/241
• 代理公司: 哈爾濱市松花江聯合專利商標代理有限公司 23213
• 代理人: 岳昕

1.一種高維空間的近似最近鄰查詢系統，其特征在于所述系統包括：存儲模塊和查詢模塊；

所述存儲模塊：存儲數據，并在存儲的數據上構建索引，包括：存儲數據劃分單元、維度矩陣獲取單元、存儲塊獲取單元；

所述存儲數據劃分單元：獲取多維數據集，采用PCA方法在預設重構誤差閾值ε的條件下對多維數據進行降維處理，獲得降維后的多維數據集，將降維后維度相同的多維數據劃分到同一個存儲結構中，n個維度對應n個存儲結構；

所述維度矩陣獲取單元：利用多維數據集中的多維數據構建維度矩陣；

所述存儲塊獲取單元：將n個存儲結構合并為多個存儲塊，并在每個存儲塊上構建索引；

所述查詢模塊：利用維度矩陣基于存儲塊獲取單元構建的索引在存儲塊上查詢數據，獲得查詢結果。

2.根據權利要求1所述的一種高維空間的近似最近鄰查詢系統，其特征在于：所述預設重構誤差閾值ε通過以下方式獲得：

步驟一一、在多維數據集采樣第一預設百分比的多維數據作為第一采樣數據集，采用PCA降維方法在主成分貢獻率達到第二預設百分比的條件下，對第一采樣數據集中的數據進行降維，并計算重構誤差的平均值ave_ε作為初標準值；

步驟一二、將初標準值ave_ε的a％、a+b％、a+2b％、....a+ib％作為測試值，對第一采樣數據集進行降維，將降維后的第一采樣數據的維度設為降維后第一采樣數據的標簽，計算相同標簽的第一采樣數據的方差，最小的方差即為重構誤差閾值ε；

其中，a、b、i為正整數。

3.根據權利要求2所述的一種高維空間的近似最近鄰查詢系統，其特征在于：所述利用多維數據集中的多維數據構建維度矩陣，包括以下步驟：

步驟二一、創建一個[dim×dim]的矩陣matrix，并將matrix初始化為0矩陣；

其中，dim是多維數據集的維度；

步驟二二、在多維數據集中采樣第三預設百分比的多維數據作為訓練集test_data，并在test_data中獲取test_data中的每個多維數據data的K個近鄰點；

其中，K是整數；

步驟二三、在降維后的多維數據集中獲取data和data的K個近鄰點的維度，并利用data和data的K個近鄰點的維度更新矩陣matrix，獲得維度矩陣matrix'。

4.根據權利要求3所述的一種高維空間的近似最近鄰查詢系統，其特征在于：所述步驟二三中在降維后的多維數據集中獲取data和data的K個近鄰點的維度，并利用data和data的K個近鄰點的維度更新矩陣matrix，獲得matrix'，包括以下步驟：

首先，在降維后的多維數據集中獲取data的維度dim(data)，以及data的K個近鄰點的維度dim(result1)、dim(result2).......dim(resultK)；

然后，將matrix矩陣中第dim(data)行第dim(result1)列的值加1，將matrix矩陣中第dim(data)行第dim(result2)列的值加1，依次類推，最后將matrix矩陣中第dim(data)行第dim(resultK)列的值加1，獲得matrix'。

5.根據權利要求4所述的一種高維空間的近似最近鄰查詢系統，其特征在于：所述將n個存儲結構合并為多個存儲塊，具體為：

將所存儲結構按照維度的大小從小到大排序，按照預設合并個數閾值num，依次將每num個存儲結構合并為一個存儲塊。

6.根據權利要求4所述的一種高維空間的近似最近鄰查詢系統，其特征在于：所述將n個存儲結構合并為多個存儲塊，還能通過以下方式實現：

首先，將matrix'每一行作為一個向量，從而獲得dim個向量；

然后，采用k-means聚類對dim個向量聚類，獲得每個向量的k-means標簽；

最后，獲取k-means標簽相同的每個向量所在維度，將與每個向量所在維度相同的存儲結構合并為一個存儲塊；

其中，每個向量指的是k-means標簽相同的每個向量。