[發明專利]一種提速的基于IPC編碼的查詢處理方法

有效

• 申請號: 201710035078.0
• 申請日: 2017-01-17
• 公開（公告）號: CN106909621B
• 公開（公告）日: 2020-02-11
• 發明（設計）人: 付璽;王斌;李鵬;王卿;李雄;徐杰;馬宏遠
• 申請（專利權）人: 中國科學院信息工程研究所
• 主分類號: G06F16/24
• 分類號: G06F16/24;G06F16/22
• 代理公司: 11200 北京君尚知識產權代理有限公司
• 代理人: 邱曉鋒

1.一種提速的基于IPC編碼的查詢處理方法，其特征在于，包括以下步驟：

(1)將IPC編碼下的索引文件視為樹形的跳表文件，在解壓縮IPC編碼的索引文件時實現恢復與略過算法；所述恢復與略過算法用一個存儲節點信息的結構體的棧來加速實現：

在恢復函數即restore函數里，一個節點信息結構體需要保存的項為：1)left，即該節點在當前區間左邊的元素個數；2)right，即該節點在當前區間右邊的元素個數；3)max，即當前區間的最大值；4)min，即當前區間的最小值；5)orgvalue，即該節點的原值；6)pos，即當前節點的位置；

在略過函數即skip函數里，一個節點信息結構體需要保存的項為：1)left，即該節點在當前區間左邊的元素個數；2)right，即該節點在當前區間右邊的元素個數；3)len，即當前區間的長度；4)tmpvalue，即該節點在IPC索引文件中記錄的值；

(2)在處理布爾求交查詢時，根據鏈表的單調性判斷是否略過某些子樹，通過略過操作來提高線上布爾查詢處理速度；在處理布爾求交查詢時，對一個已經解壓的順序列表與一個IPC編碼壓縮的索引列表執行快速求交算法；

定義恢復后的數值列表保存在數列Rlr中，待恢復的列表是ls，已恢復列表是Rlr1，節點信息結構體的棧是S，并定義Rlrcur、Rlr1cur為Rlr與Rlr1上的當前指針；對于一個根為root的樹，定義leftlist是root到其最左葉子節點的路徑的逆路徑；則所述快速求交算法包括以下步驟：

1)恢復根節點并壓入棧；

2)當棧不為空時，取root為棧首元素并執行如下循環；

3)如果root的原值小于Rlr1cur所指的值，則略過root的整個左子樹；對root的左子樹的根節點調用skip函數；

4)如果root的原值不小于Rlr1cur所指的值，恢復root的子樹下所有最左邊的節點；

5)執行如下循環；

6)如果Rlr1cur所指的值小于或等于root的原值，那么執行第7)步，否則執行第10)步；

7)如果Rlr1cur所指的值等于root的原值，那么把root的原值壓入結果列表Rlr，Rlr上指針Rlrcur后移，無論條件是否滿足，執行第8)步；

8)如果Rlr1列表到了其邊界，那么跳出函數，否則執行第9)步；

9)Rlr1列表上指針Rlr1cur后移，返回第5)步；

10)定義tmp是棧S的top節點的指針，并彈出棧；

11)如果Rlr1cur所指的值小于tmp節點的leftlist下下一個節點的原值，并且tmp節點存在右孩子，那么執行第12)步，否則執行第13)步；

12)恢復他的右孩子節點并壓入棧S，回到第2)步；

13)調用skip函數跳過其所有右子樹節點，并回到第5)步；最后在列表Rlr中保存的值就是布爾與查詢中求交的結果，并且在算法中實現了skip的操作；

(3)在處理排序查詢時，采用帶skip的頻率獲取算法，根據文檔ID列表的求交結果的位置快速取出對應的頻率的索引文件的值，通過略過所有不需要訪問的子樹來提高線上排序查詢的處理速度；所述帶skip的頻率獲取算法使用TAAT處理方式，在達到累加器的上限之前，對查詢詞的處理采用union策略，在達到上限后，采用繼續更新累加器的continue策略。

2.如權利要求1所述的方法，其特征在于，在排序查詢里的用于獲得文件ID的快速求交算法與布爾求交查詢的快速求交算法的區別在于，在排序查詢里將求交結果的位置信息存入位置列表中，作為頻率列表里的對應元素的索引。