[發明專利]搜索方法、搜索程序以及搜索裝置

有效

• 申請號: 201410697191.1
• 申請日: 2014-11-26
• 公開（公告）號: CN104731847B
• 公開（公告）日: 2019-05-28
• 發明（設計）人: 野間唯;此島真喜子
• 申請（專利權）人: 富士通株式會社
• 主分類號: G06F16/9032
• 分類號: G06F16/9032
• 代理公司: 北京集佳知識產權代理有限公司 11227
• 代理人: 康建峰;韓雪梅

本公開涉及一種搜索方法、搜索程序以及搜索裝置。根據實施例的搜索裝置基于包括節點和距離的參數將特征向量映射在超球體上，其中，在交點處m維特征空間與經過該超球體的直線相交，該超球體存在于維度比m更大的空間中，該距離是從超球體的北極至特征空間的距離。在這種情況下，搜索裝置搜索允許映射在超球體上的特征向量的位置集中在超球體的預定半球上的參數。

技術領域

本文所公開的實施例涉及搜索方法等。

背景技術

例如，為了認證各種系統的用戶，而獲取用戶的生物統計信息，然后，確定與所獲取的生物統計信息匹配的生物統計信息是否已被數據庫所預先記錄并且能在該數據庫中找到。這里，由于在認證時要獲取的生物統計信息很少完全匹配在登記時獲取的生物統計信息，所以能夠有效地執行相似性搜索。

為了表達用于執行相似性搜索的相似性等級，可使用將生物統計信息的特征值轉換成散列向量(hash vetor)的技術。該技術將具有相近漢明距離(close hammingdistance)的散列向量的每條生物統計信息識別為相似生物統計信息。

傳統技術已采用超平面將特征值轉換成散列向量。然而，還可使用采用超球體將特征值轉換成散列向量的技術，并且期望使用超球體的技術實現精度改善。

引用文獻列表

專利文獻

專利文獻1：日本已公開專利公布第2011-100395號

專利文獻2：日本已公開專利公布第2012-160047號

專利文獻3：日本已公開專利公布第2011-39755號

非專利文獻

非專利文獻1：Jae-Pil Heo,Youngwoon Lee,Junfeng He,Shih-Fu Chang,andSung-Eui Yoon,“Spherical hashing”,in CVPR,pp.2957-2964,2012。

非專利文獻2：Kengo Terasawa and Yuzuru Tanaka,“Spherical lsh forapproximate nearest neighbor search on unit hyper-sphere”,in FrankK.H.A.Dehne,Jorg-Rudiger Sack,and Norbert Zeh,editors,WADS,Vol.4619 ofLecture Notes in Computer Science,pp.27-38.Springer,2007。

然而，前述傳統技術引起了利用超球體計算散列向量將導致計算量增加的問題。

此外，當利用超球體將特征向量轉換成散列向量時，蟲孔(wormhole)可以引起甚至明顯不同的特征向量，從而在轉換成散列向量后具有縮短的漢明距離。由于這個原因，那些不同的特征向量會被錯誤地確定為相似特征向量。

因此，本發明的一個實施例的一個方面的目的是提供一種以簡單方式利用超球體實現要執行的相似性搜索的搜索方法、搜索程序以及搜索裝置。

發明內容

根據實施例的一個方面，一種搜索方法包括：獲取在數據庫中存儲的第一維特征向量；以及搜索以下參數：當特征向量基于包括交點和距離的所述參數映射在球體的表面上時，通過所述參數，要映射在所述球體的表面上的特征向量的位置集中在所述球體的半球上，在該交點處特征空間與經過該球體的直線相交，，該球體存在于維度比該特征空間大一維或更多維的空間中，該距離是從球體的預定點至該特征空間的距離。

附圖說明

圖1是例示根據第一實施例的搜索裝置的配置的功能塊圖。

圖2A是例示特征值存儲單元的示例數據結構的視圖。