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

在審

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

一種高維空間的近似最近鄰查詢系統，涉及計算機數據處理領域。本發明是為了解決現有最近鄰查詢方法還存在查詢時間長、查詢精度低以及依賴哈希函數質量的問題。本發明包括：存儲模塊和查詢模塊；存儲模塊包括：存儲數據劃分單元、維度矩陣獲取單元、存儲塊獲取單元；存儲數據劃分單元：獲取多維數據集，采用PCA方法在預設在預設重構誤差閾值ε的條件下對多維數據進行降維處理，獲得降維后的多維數據集，將降維后維度相同的多維數據劃分到同一個存儲結構中；維度矩陣獲取單元：利用多維數據構建維度矩陣；存儲塊獲取單元：將存儲結構合并為存儲塊，并在存儲塊上構建索引；查詢模塊：利用維度矩陣在存儲塊上查詢數據。本發明用于高維數據的查詢。

技術領域

本發明涉及計算機數據存儲及查詢技術領域，特別涉及一種高維空間的近似最近鄰查詢系統。

背景技術

隨著互聯網、物聯網、大數據等技術的快速發展，KNN查詢作為一種基礎操作被廣泛應用到數據處理領域中。KNN問題是基于給定的距離度量(例如，歐幾里得距離)從數據集中確定k個最接近q的數據點。然而雖然KNN問題在低維空間中存在有效的查詢解決方案，但由于所謂的“維度詛咒”現象，KNN在高維空間中的應用仍具有挑戰性。

隨著數據規模和維度的增大，現有的KNN問題的解決方法性能急劇下降，查詢時間顯著變長(例如KD-tree、M-tree)，同時，隨著維度的增加，基于圖的索引在構建KNN圖上也需要花費相對較長的時間。使用深度學習方法的學習索引雖然大幅減少了查詢時間，但很難保證查詢的精度。而基于LSH的索引，它的性能高度依賴于使用的哈希函數的質量。因此現有的最近鄰查詢方法還存在查詢時間長、查詢精度低以及依賴哈希函數質量的問題。

發明內容

本發明目的是為了解決現有最近鄰查詢方法還存在查詢時間長、查詢精度低以及依賴哈希函數質量的問題，而提出了一種高維空間的近似最近鄰查詢系統。

一種高維空間的近似最近鄰查詢系統，包括：存儲模塊和查詢模塊；

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

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

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

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

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

進一步地，所述預設重構誤差閾值ε通過以下方式獲得：

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

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

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

進一步地，所述利用多維數據集中的多維數據構建維度矩陣，包括以下步驟：

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

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