[發明專利]一種從m部圖中得到極大完全子圖的數據庫搜索方法

有效

• 申請號: 201710132397.3
• 申請日: 2017-03-07
• 公開（公告）號: CN107038215B
• 公開（公告）日: 2020-07-17
• 發明（設計）人: 殷永;李越
• 申請（專利權）人: 東方網力科技股份有限公司
• 主分類號: G06F16/583
• 分類號: G06F16/583;G06K9/00
• 代理公司: 北京金智普華知識產權代理有限公司 11401
• 代理人: 皋吉甫

1.一種從m部圖中得到極大完全子圖的數據庫搜索方法，所述搜索方法應用于從人臉識別數據庫，其特征在于，所述方法通過建立無向圖模型，構成一個k階極大完全子圖，并通過鄰接鏈表來存儲無向圖G，以正序邊和最大頂點為基本量，通過剪枝法對無向圖G的頂點數和k階完全子圖的計算量T_k進行計算，從而得到該極大完全子圖的空間復雜度和時間復雜度，完成對極大完全子圖的搜索，并將搜索結果用于人臉識別數據中，通過尋找頻繁項集，大幅減少對數據庫的訪問，提高識別效率，所述方法包括：

S1：將不同區域人臉照片之間的相似關系圖以m部無向圖G表示，并構建無向圖模型G，其中，G＝(V,E)是m部無向圖，V表示頂點的集合，E表示邊的集合；

S2：對m部圖進行遍歷，獲取k階完全子圖；

S3：找出S2中每個k階完全子圖的最大頂點；

S4：遍歷與最大頂點有邊相連的頂點集合S；

S5：判斷S里的每個頂點U是否與k階圖內其他頂點均有邊相連，如果有，進行S6，如果無，進行S7；

S6：k階完全子圖與U合并生成k+1階完全子圖，判斷k是否與m相同，如果相同，終止，如果不同，則k＝k+1，以U作為最大頂點繼續遍歷操作，進行S4；

S7：無法擴展，該無向圖最大為N階完全子圖；

S8：通過頂點集合V，邊的集合E和數組Adj三個數據，對S6和S7中獲得的N階完全子圖或k階完全子圖進行偽代碼換算；

S9:對S8中換算的結果，進行算法的時間復雜度和空間復雜度計算；

S10：將S9中的換算結果代入人臉識別數據庫；

S11：通過尋找人臉數據庫中的頻繁項集，減少對數據庫的訪問，完成人臉識別過程。

2.根據權利要求1所述的搜索方法，其特征在于，所述S1中構建無向圖模型G時，為了簡化問題，設置每個頂點集合的頂點數目都為num，圖G中對應每個區域的頂點集合分別記為V_i,i＝1,2,...,m，則V＝{u:u∈V_i,i＝1,2,...,m}，E＝{(u,v):u∈V_i,v∈V_j,i≠j,i,j＝1,2,...,m}。

3.根據權利要求1所述的搜索方法，其特征在于，所述S1中無向圖G通過鄰接鏈表進行存儲，所述鄰接鏈表為多條鏈表構成的數組，記為Adj，鏈表中存儲正序邊的鏈接關系，對于每一個節點中u∈V，鄰接鏈表Adj[u]包含所有與頂點u之間且構成正序邊(u,v)的結點v。

4.根據權利要求1所述的搜索方法，其特征在于，所述S8中偽代碼換算方法為：

S81：k＝3，每條邊(u,v)∈G.E，每個頂點x∈G.Adj[v]；

S82：令x∈G.Adj[u]，將{u,v,x}插入到表示k階極大完全子圖的集合；

S83：令k＝4:m，每一個v為A_k-1中的最大頂點，每一個x∈G.Adj[v]；

S84：令x∈G.Adj[A_k]，則v與A_k-1中的每一個頂點都相連；

S85：將A_k-1∪{x}插入到并從中刪除A_k-1。

5.根據權利要求2所述的搜索方法，其特征在于，所述時間復雜度和空間復雜度計算方法如下：

S91：假設對于第k(1≤k＜m)個頂點集合中的頂點，在下標大于k每一個頂點集合中，與它有邊相連的頂點的個數為常數c；

S92：假設所有的k-1階完全圖的個數是k階完全圖的k倍，且m階完全圖的個數為1，則k階完全圖的個數應該為

S93：由于最大頂點最多來自m-k+1個不同的頂點集合，則與所有最大頂點有邊相連的頂點個數最多為：

S94：計算k階完全子圖的計算量：

S95：計算時間復雜度：

S96：計算空間復雜度：S＝|E|＝c*num*(m-1)＝O(num*m)。