隨機(jī)跳躍索引一種支持隨機(jī)插入的可信賴索引

1、隨機(jī)跳躍索引：一種支持隨機(jī)插入的可信賴索引本課題得到: 國(guó)防科工委項(xiàng)目(A2120061061), 上海市科學(xué)技術(shù)委員會(huì)重點(diǎn)基礎(chǔ)研究項(xiàng)目（08JC1400100），上海市人才發(fā)展資金（001），上海市領(lǐng)軍人才后備人選專項(xiàng)資金資助. 劉鳳晨,男,1982年生,甘肅蘭州人,博士研究生,主要研究方向：信息檢索,智能算法,檢索算法,E-mail: aric. 黃河,男, 1972年出生, 安徽淮南人博士后，副教授，碩士生導(dǎo)師,主要研究方向：網(wǎng)絡(luò)與信息安全, E-mail: huanghe. 劉慶文,男, 1966年出生,山東濟(jì)南人,博士后，講師，主要研究方向：數(shù)據(jù)庫(kù)、分布式信息處理E-mail: ne

2、tperson.丁永生,男, 1967年出生,安徽懷寧人,博士,教授，博士生導(dǎo)師，從事智能系統(tǒng)、網(wǎng)絡(luò)智能、DNA計(jì)算、人工免疫系統(tǒng)、生物網(wǎng)絡(luò)結(jié)構(gòu)、生物信息學(xué)、數(shù)字化紡織服裝、智能決策與分析等研究, E-mail: ysding劉鳳晨1, 黃河2， 劉慶文3，丁永生1,41(東華大學(xué) 信息科學(xué)與技術(shù)學(xué)院, 上海 201620)2(北京航空航天大學(xué),軟件學(xué)院, 北京 100083)3(北京科技大學(xué) 計(jì)算機(jī)學(xué)院, 北京 100083)4(數(shù)字化紡織服裝技術(shù)教育部工程研究中心，上海 201620)摘 要:跳躍索引是一種可信賴性索引，但只能為嚴(yán)格單調(diào)遞增的序列建立索引，不能處理非順序序列。為了解決這個(gè)問(wèn)

3、題，本文提出了一種新的索引，它可以對(duì)任意順序的序列建立索引，并且依然保證索引的可信賴性。通過(guò)在原有跳躍索引結(jié)構(gòu)加中入左側(cè)跳躍指針的方法，索引節(jié)點(diǎn)可以根據(jù)待加入節(jié)點(diǎn)值的大小將其納入自己的左側(cè)或右側(cè)指針以處理隨機(jī)序列；索引結(jié)構(gòu)中的每一個(gè)節(jié)點(diǎn)到根節(jié)點(diǎn)的路徑固定且唯一，保證了索引的可信賴性。實(shí)驗(yàn)結(jié)果和理論證明都表明該索引是可以處理隨機(jī)序列的可信賴索引，相對(duì)原有索引，索引建立復(fù)雜度明顯降低且具有相同的查找復(fù)雜度。本文的創(chuàng)新之處是在保證索引的可信賴性的基礎(chǔ)上解決了跳躍索引不能為隨機(jī)序列建立索引的問(wèn)題。關(guān)鍵詞：可信賴性；倒排表；索引；B+樹(shù)；檢索；算法中圖法分類號(hào):TP391.3文獻(xiàn)標(biāo)識(shí)碼: AA Trus

4、tworthy Index for Inserting Random SequencesLIU Feng-Chen1, HUANG He2,LIU Qing-Wen3, DING Yong-Sheng1,4 1(College of Information Sciences and Technology, Donghua University, Shanghai 201620, China)2(College of Software, Beijing University of Aeronautics and Astronautics, Beijing 100083, China)3(Scho

5、ol of Computer Science, Beijing University of Science and Technology, 100083 China)4(Engineering Research Center of Digitized Textile & Fashion Technology, Ministry of Education, Shanghai 201620, China)Abstract: Jump Index is a kind of trustworthy index which can only build index for strictly mo

6、notonically increased sequences rather than unordered sequences. To solve this problem, this paper proposed a novel index supporting building index for random sequences, without losing the trustworthy of jump index. By adding left pointers on the node of jump index, the candidate node in random sequ

7、ences can be indexed into one of the left or right pointers of a node in the index. The left jump pointers are used to index nodes with less value than current nodes value, while right jump pointers point to those nodes with higher value. Every node in the index has the unique and permanent path fro

8、m root node, which ensures the trustworthy in the index. Experiment results and proofs in this paper show that the index is trustworthy and supports indexing for random sequences, also it has more efficiency of building index and same complexity of search compared with jump index. The contribution o

9、f this paper is that the new index with trustworthy solve the problem that jump index cannot insert and build index for random sequences.Key words:Trustworthy；Inverted Index; B+ Tree; Retrieval; Algorithm1 引言在商業(yè)運(yùn)作以及一些重大事務(wù)的關(guān)鍵決策過(guò)程中，電子郵件、會(huì)議記錄、財(cái)務(wù)狀況以及項(xiàng)目計(jì)劃書(shū)等諸如此類的文件起著關(guān)鍵作用,屬于重要而且基本的信息。因此這些信息必須以一種可信賴（trustwo

10、rthy）的方式保存，從而使它們不能被惡意的刪除或者篡改，并且易于訪問(wèn)。然而，隨著文檔被大量的電子化這些信息也變得更容易被篡改、刪除，且不留任何痕跡。因此，確保數(shù)據(jù)信息的易于訪問(wèn)性、準(zhǔn)確性、可靠性和不可抵賴性已經(jīng)成為勢(shì)在必行的趨勢(shì)。在這種趨勢(shì)的推動(dòng)之下，WORM（Write Once Read Many一次寫入多次讀?。┐鎯?chǔ)設(shè)備便成了此類信息存儲(chǔ)的主要方式。但是在WORM保存數(shù)據(jù)并不能充分保證數(shù)據(jù)的可信賴性1，例如，它不能為以前所發(fā)生的事件提供不可抵賴性證據(jù)。此外，即便是數(shù)據(jù)保存在WORM設(shè)備中，如果訪問(wèn)這些數(shù)據(jù)的索引可以被改動(dòng)的話，數(shù)據(jù)還是可以被隱藏或者刪除的。例如，索引中指向某一數(shù)據(jù)的指針

11、被刪除或者改動(dòng)后指向另一數(shù)據(jù)，這時(shí)原來(lái)的數(shù)據(jù)會(huì)再也訪問(wèn)不到了。因此，僅僅是數(shù)據(jù)以可信賴的方式保存是不夠的，索引本身也要以可信賴的方式保存。為了解決可信賴性索引的問(wèn)題，近幾年的研究也提出了一些方法， 其中跳躍索引(Jump Index) 2是目前解決索引可信賴性最好的方法，但它要求被索引文檔ID有序遞增，不支持以隨機(jī)插入的方式建立索引。本文針對(duì)跳躍索引不能支持以隨機(jī)插入的方式建立索引的不足，設(shè)計(jì)了新的跳躍索引結(jié)構(gòu)，該索引支持被索引文檔的非順序插入，而且具有和原有索引相同的可信賴性。2 相關(guān)工作針對(duì)索引的可信賴性，目前的一些研究中提出了化石索引（fossilized index）1的概念，主要思想

12、是不允許對(duì)索引進(jìn)行操作。Generalized Hash Tree(GHT)1,3,4就是一種化石索引，但這種方法對(duì)數(shù)據(jù)信息的結(jié)構(gòu)要求嚴(yán)格，不具有通用性。它可以根據(jù)數(shù)據(jù)的屬性提供精確查找，適用于結(jié)構(gòu)化的數(shù)據(jù)。但是大部分商業(yè)數(shù)據(jù)，例如郵件內(nèi)容、會(huì)議記錄、備忘錄等都是非結(jié)構(gòu)化或半結(jié)構(gòu)化的，這類信息查找最適合的方法是關(guān)鍵詞查找?；陉P(guān)鍵詞的查找最典型的方法就是倒排表(Inverted Index)5,6。Jump Index就是在每一條記錄的倒排表(Posting Lists) 7,8,9中以Jump Index方式建立索引。該索引的建立是為了提高不同倒排表之間的合并和連接(Merge and Jo

13、in)2操作。圖2中是Zigzag Join2,10算法，它可以將兩個(gè)倒排表以時(shí)間復(fù)雜度合并與連接，分別為兩個(gè)倒排表的長(zhǎng)度，是一種效率很高的算法。Jump Index就是為了支持Zigzag Join算法中的FindGeq()方法。圖1(a)中是Jump Index跳躍索引的節(jié)點(diǎn)的結(jié)構(gòu)，Jump Index每一個(gè)節(jié)點(diǎn)保存著倒排表中文章ID，跳躍指針指向下一個(gè)節(jié)點(diǎn)。例如，節(jié)點(diǎn)的第個(gè)跳躍指針指向節(jié)點(diǎn)， 。Jump Index的結(jié)構(gòu)保證了索引中從根節(jié)點(diǎn)到任意一個(gè)節(jié)點(diǎn)的路徑是唯一的，這就確保了索引的可信賴性。但是，Jump Index要求待建立索引的序列是嚴(yán)格單調(diào)遞增的，這樣的約束條件為Jump In

14、dex帶來(lái)了很大的局限性。例如，對(duì)一個(gè)隨機(jī)的序列首先要對(duì)其排序后才能建立索引，之后，如果新的序列到來(lái)只能將原有序列與新序列合并排序后重新建立索引，對(duì)較小的序列來(lái)說(shuō)尚且可行，但是對(duì)非常大的序列來(lái)說(shuō)，滿足這種約束條件后再建立索引所付出的代價(jià)是非常大的。圖1(b)的例子中，序列11，2，5，7，15滿足約束條件，可以插入到索引中；序列28，9，14不滿足約束條件，因?yàn)?和14要插入的位置已經(jīng)被10和15占據(jù)。遇到這種情況，Jump Index只能將兩個(gè)序列合并為1，2，5，7，8，9，10，14，15后重新建立索引。(a) Jump Index跳躍索引的節(jié)點(diǎn)結(jié)構(gòu)(b) 索引的插入過(guò)程圖1：Jump

15、Index跳躍索引結(jié)構(gòu)與插入過(guò)程圖2：Zigzag Join 算法3 可隨機(jī)插入的跳躍索引3.1 隨機(jī)跳躍索引能否讓Jump Index擺脫嚴(yán)格單調(diào)遞增的束縛呢？為了克服原有跳躍索引的不足，我們?cè)O(shè)計(jì)了一種新的可信賴的且支持隨機(jī)插入的索引隨機(jī)跳躍索引（random jump index）。這種索引不要求倒排表中的文章ID必須嚴(yán)格單調(diào)遞增，這些文章ID可以是任意序列（單調(diào)遞增、遞減或無(wú)序）。Random jump index 支持zigzag join算法中的FindGeq()方法，并且能在最大時(shí)間復(fù)雜度為找到結(jié)果，其中是倒排表中文章ID序列中最大值。該索引的時(shí)間復(fù)雜度的范圍相比B+樹(shù)查找的時(shí)間復(fù)

16、雜度要寬松一些，這里為B+樹(shù)中當(dāng)前葉節(jié)點(diǎn)的個(gè)數(shù)，但這保證了索引中每個(gè)節(jié)點(diǎn)的路徑唯一且保持不變。事實(shí)上，在實(shí)際應(yīng)用當(dāng)中，文章ID是隨著文章總數(shù)增長(zhǎng)而增加的，相當(dāng)于數(shù)據(jù)庫(kù)中文章的總數(shù)目。因此，隨機(jī)跳躍索引的時(shí)間復(fù)雜度是文章總數(shù)的對(duì)數(shù)級(jí)。 任何數(shù),在以2為底數(shù)時(shí)，都可以在步之內(nèi)到達(dá)。跳躍索引的方法就是受這種將一個(gè)數(shù)與二進(jìn)制相互轉(zhuǎn)換的啟發(fā)而得來(lái)的。假設(shè)一個(gè)數(shù)字序列為，其中。任意數(shù)可以表示成二進(jìn)制數(shù)，若要由此序列得到，可以從序列第一個(gè)位置開(kāi)始，向前跳躍，然后再向前跳躍直至，最后得到。如果我們將這種方法運(yùn)用到倒排表中，由于倒排表不一定包含所有的文章ID，所以必須告訴跳躍指針（jump pointer）下一

17、步跳躍的步長(zhǎng)。圖3(a)中是隨機(jī)跳躍索引的節(jié)點(diǎn)的結(jié)構(gòu)，中間的ID表示文章ID，ID左邊的指針（left pointer）指向比它小的文章ID，右邊的指針（right pointer）指向比它大的文章ID。節(jié)點(diǎn)右邊的第個(gè)指針指向比大的節(jié)點(diǎn), 。圖3(b)中，第1個(gè)節(jié)點(diǎn)的右邊第0個(gè)指針指向2，因?yàn)?；右邊第二個(gè)指針指向5，因?yàn)?，右邊其它的指針都是這樣計(jì)算得出的。節(jié)點(diǎn)左邊的第個(gè)指針指向比小的節(jié)點(diǎn), 。圖3(c)中，第15個(gè)節(jié)點(diǎn)的左邊第0個(gè)指針指向14，因?yàn)?；?0個(gè)節(jié)點(diǎn)的左邊第0個(gè)指針指向9，因?yàn)椤?a) Random Jump Index隨機(jī)跳躍索引的節(jié)點(diǎn)結(jié)構(gòu) (b) 建立索引過(guò)程(c) 隨機(jī)序列插

18、入過(guò)程圖3：Random Jump Index隨機(jī)跳躍索引結(jié)構(gòu)與索引建立過(guò)程 下面討論更一般的情況：假設(shè)倒排表中的記錄為。從隨機(jī)跳躍索引的根節(jié)點(diǎn)開(kāi)始，通過(guò)左右跳躍指針，序列中的每一個(gè)記錄都可以查找到。查找過(guò)程如下：設(shè)待查找的節(jié)點(diǎn)為，首先從根節(jié)點(diǎn)開(kāi)始，找到節(jié)點(diǎn)的跳躍指針，當(dāng)時(shí)，為左指針，當(dāng)時(shí)，為右指針，然后通過(guò)跳躍指針從跳到另一個(gè)節(jié)點(diǎn)。在 中找到節(jié)點(diǎn)的跳躍指針，當(dāng)時(shí)，為左指針，當(dāng)時(shí)，為右指針，通過(guò)跳躍指針找到節(jié)點(diǎn)，之后重復(fù)上述步驟直至找到。在圖3(c)中，查找節(jié)點(diǎn)9，首先從根節(jié)點(diǎn)1跳到節(jié)點(diǎn)10，此時(shí)跳躍右指針；然后從節(jié)點(diǎn)10跳到節(jié)點(diǎn)9，此時(shí)跳躍左指針。 圖4中，以偽代碼的形式列出了插入算法Ins

19、ert()，查找算法Lookup()，F(xiàn)indGeq()算法返回第一個(gè)大于等于的節(jié)點(diǎn)，F(xiàn)indGeqRec(,)算法是以為根節(jié)點(diǎn)在其子樹(shù)中尋找第一個(gè)大于等于的節(jié)點(diǎn)。在Zigzag join算法中執(zhí)行FindGeq()可直接調(diào)用FindGeqRec(,)算法。s.rptri表示節(jié)點(diǎn)中右指針，s.lptrj表示節(jié)點(diǎn)中左指針。assert用來(lái)檢查所得節(jié)點(diǎn)是否滿足約束條件。圖4：Random Jump Index隨機(jī)跳躍索引的基本算法3.2 復(fù)雜度分析為了清晰的說(shuō)明隨機(jī)跳躍索引的復(fù)雜度首先給出下列命題，然后證明之。命題1：設(shè)是算法Lookup()執(zhí)行過(guò)程中循環(huán)執(zhí)行第7或20步所得和的序列，則序列中。證

20、明：在隨機(jī)跳躍索引中執(zhí)行Lookup()依次跳過(guò)的文章ID序列為：，為Random Jump Index中的根節(jié)點(diǎn)。在查找的過(guò)程中從跳到會(huì)出現(xiàn)以下四種情況：(I)，(II)，(III) ，(IV)。現(xiàn)在分別對(duì)這四種情況證明：(I)，由算法Lookup()第20步可得(a)，因?yàn)榈挠抑羔樦赶?，所以?b)。同理得到(c)。由(a)和(c)得到(d)。再由(b)和(d)得。因此。(II)，由算法Lookup()第20步可得(a)，因?yàn)榈挠抑羔樦赶?，所以?b)。由于，是的左指針，且(c)。由(a)和(c)得到(d)。再由(b)和(d)得。因此。(III) ，由算法Lookup()第7步可得(a)，

21、因?yàn)榈淖笾羔樦赶?，所以?b)。同理得到(c)。由(a)和(c)得到(d)。再由(b)和(d)得。因此。(IV)，由算法Lookup()第7步可得(a)，因?yàn)榈淖笾羔樦赶颍裕?b)。由于，是的右指針，且 (c)。由(a)和(c)得到(d)。再由(b)和(d)得。因此。以上四種情況下均有，同理可以證明，最后得出。證畢 由上面的證明可以看出Lookup()執(zhí)行過(guò)程中的循環(huán)次數(shù)不會(huì)超過(guò)，而，因此最多跳躍步就可以找到。算法Insert()和FindGeq()時(shí)間復(fù)雜度也為。如果為所有文章的總數(shù)，以上算法的最大時(shí)間復(fù)雜度為。因此，可以得出這種隨機(jī)跳躍索引的查找性能是和原有跳躍索引性能是一樣的。3.3

22、 隨機(jī)跳躍索引的可信賴性跳躍索引的優(yōu)勢(shì)在于它保證了索引中數(shù)據(jù)的可信賴性，即數(shù)據(jù)不能被改動(dòng)或隱藏，數(shù)據(jù)的路徑唯一且固定不變。而這些特性是由跳躍索引的兩條性質(zhì)保證的，隨機(jī)跳躍索引具有和跳躍索引相同的可信賴性，為了說(shuō)明這一點(diǎn)，下面證明它也具有跳躍索引的兩條性質(zhì)。命題2：當(dāng)文章ID插入到倒排表的隨機(jī)跳躍索引中之后，該文章ID總是可以被成功的查找到。證明：在執(zhí)行Insert()時(shí)，數(shù)據(jù)是被寫在WORM設(shè)備上的，所以數(shù)據(jù)在寫入之后是不會(huì)被改動(dòng)的。上一節(jié)中的序列對(duì)Lookup()是唯一的，因此插入的數(shù)據(jù)總是可以被找到。證畢命題3：設(shè)是一個(gè)在倒排表中的文章ID。如果，那么FindGeq()返回的值不會(huì)大于。證

23、明：設(shè)是隨機(jī)跳躍索引的根節(jié)點(diǎn)。此時(shí)有三種情況:(I) (II) (III) . 在分別證明之前，設(shè)在索引中的跳躍指針序列為（例如，執(zhí)行Lookup()所得序列）。同樣，設(shè)FindGeq()返回值的序列為。 (I) ，首先證明。在第一次調(diào)用FindGeqRec()，由第28步得到，因?yàn)?。如果通過(guò)了第29和第33步的檢查，那么，。如果上兩步都為假，那么FindGeqRec()將執(zhí)行第39步。由于在索引中，s.rptr不會(huì)為NULL，所以，。這時(shí)又有兩種情況：(i) 這種情況下，因?yàn)椤?(ii) 。此時(shí)直接調(diào)用FindGeqRec()。 (II) ，首先證明。第一次調(diào)用FindGeqRec()，由第

24、5步得到，因?yàn)椤Ｈ绻ㄟ^(guò)了第6和第11步的檢查，那么，。如果上兩步都為假，那么FindGeqRec()將執(zhí)行第17步。由于在索引中，s.lptr不會(huì)為NULL，所以，。這時(shí)又有兩種情況：(i) 這種情況下，因?yàn)椤?(ii) 。此時(shí)直接調(diào)用FindGeqRec()。 (III) ，由(II)得FindGeqRec()返回值，又因?yàn)?，所以?以上三種情況下都有FindGeqRec()。證畢 命題3保證了在連接兩個(gè)倒排表時(shí)沒(méi)有文章ID會(huì)被隱藏。如果文章ID d在兩個(gè)倒排表中都出現(xiàn)，執(zhí)行zigzag join算法時(shí)從表中最小的值開(kāi)始調(diào)用FindGeq()，性質(zhì)3可以保證在返回d之前，F(xiàn)indGeq()

25、返回的值不會(huì)大于它。換言之，d最終被兩個(gè)倒排表中的FindGeq()返回，并且出現(xiàn)在最終結(jié)果當(dāng)中。這兩條性質(zhì)保證了隨機(jī)跳躍索引與跳躍索引具有相同的可信賴性。3.4 廣義的隨機(jī)跳躍索引索引的深度是影響查找速度的主要因素。在文章ID非常多時(shí)，例如、甚至更大，減小索引深度能明顯減少查找次數(shù)。為此，可以用作為底數(shù)，不僅僅以2為底數(shù)。每個(gè)節(jié)點(diǎn)的左右跳躍指針個(gè)數(shù)為，跳躍指針用參數(shù)表示，其中，。如果為當(dāng)前節(jié)點(diǎn)，右指針指向，那么；左指針指向，那么。圖5中的例子是以3為底數(shù)，文章ID總數(shù)。節(jié)點(diǎn)13的右跳躍指針指向16，因?yàn)?，同理右跳躍指針指向53，因?yàn)椋?3的左跳躍指針指向7，因?yàn)椤?用廣義的隨機(jī)跳躍索引，In

26、sert()、Lookup()和FindGeqRec()算法的時(shí)間復(fù)雜度均為。圖5：廣義的隨機(jī)跳躍索引4 性能評(píng)估本節(jié)首先對(duì)Random Jump Index的索引大小做出分析；然后比較Random Jump Index與Jump Index兩種索引在建立時(shí)，隨機(jī)插入與嚴(yán)格單調(diào)遞增插入的比較次數(shù)，最后對(duì)這兩種索引的查找性能作出比較。影響這些性能的關(guān)鍵變量有底數(shù)，文章ID的總數(shù)。 在對(duì)總數(shù)為的文章ID集合建立隨機(jī)跳躍索引時(shí)，索引的大小可由下面的公式表示：，其中為一個(gè)跳躍指針的大小，通常為4個(gè)字節(jié)，為節(jié)點(diǎn)元素值的大小，通常為4或8個(gè)字節(jié)。索引大小 與和成正比。在實(shí)際應(yīng)用中對(duì)不同的，可以根據(jù)查找的查

27、找效率與存儲(chǔ)效率所相應(yīng)調(diào)整。 下面對(duì)比二者建立索引時(shí)的效率。Random Jump Index可以連續(xù)處理多個(gè)文章ID序列，而Jump Index只能處理一個(gè)文章ID序列，如果有新的序列到達(dá)，Jump Index只能將原有序列與新序列按照遞增順序合并后，毀掉以前的索引重新建立索引；對(duì)于Random Jump Index則只需要將新序列插入到原有索引即可。顯然，在處理多序列時(shí)Random Jump Index要大大優(yōu)于Jump Index?，F(xiàn)在只對(duì)比處理單個(gè)序列時(shí)二者的復(fù)雜度：設(shè)為隨機(jī)序列，Random Jump Index繼續(xù)將該序列的個(gè)元素依次插入的索引中即可，總的比較次數(shù)為；對(duì)于Jump

28、Index則需要將該序列排序后再依次插入索引，當(dāng)該序列有序時(shí)它的比較次數(shù)與也是，當(dāng)序列無(wú)序時(shí)調(diào)整次序需要次比較，所以Jump Index對(duì)該序列建立索引總比較次數(shù)為?？梢?jiàn)對(duì)單個(gè)序列建立索引時(shí)，Random Jump Index效率也高于Jump Index。 最后，對(duì)比兩者的查找效率。Jump Index查找時(shí)，根節(jié)點(diǎn)始終為序列中最小的節(jié)點(diǎn)，最大比較次數(shù)為。Random Jump Index查找時(shí)比較次數(shù)與根節(jié)點(diǎn)的值有關(guān)，而等于該序列的期望值， ；Random Jump Index查找時(shí)的平均比較次數(shù)為。命題1決定了二者的最壞查找效率相等，但平均查找效率Random Jump Index要優(yōu)于

29、Jump Index。(a)索引大小對(duì)比 (b)建立索引的效率對(duì)比(c)查找效率對(duì)比圖6：隨機(jī)跳躍索引的性能試驗(yàn)結(jié)果5 試驗(yàn)結(jié)果我們用MATLAB進(jìn)行了仿真試驗(yàn)，針對(duì)不同的文章ID總數(shù)，不同的底數(shù)，將二者的索引大小，建立索引的效率，以及查找效率做了對(duì)比。其中，。圖6(a)中是兩者索引大小的對(duì)比結(jié)果。試驗(yàn)中，。由于隨機(jī)跳躍索引多了左跳躍指針，所以其索引要比Jump Index大。對(duì)同樣的，索引大小隨著的增大而增加，可見(jiàn)在降低索引深度的同時(shí)會(huì)增加索引大小。圖6(b)是對(duì)兩種索引建立的效率比較。這里， 圖6(b)中Jump Index曲線是對(duì)單個(gè)序列建立索引時(shí)的最小比較次數(shù)，Random Jump

30、Index曲線是對(duì)單個(gè)序列建立索引時(shí)的最大比較次數(shù)，可見(jiàn)，后者最大比較次數(shù)小于前者的最小比較次數(shù)。對(duì)相同的，二者的比較次數(shù)都隨著的增加在不斷減小。圖6(c)是對(duì)查找效率的比較。試驗(yàn)結(jié)果顯示二者的查找效率是非常接近的，而且隨著的增加查找效率也越來(lái)越高。6 結(jié)束語(yǔ)本文提出的Random Jump Index隨機(jī)跳躍索引，不再受限于Jump Index 跳躍索引嚴(yán)格單調(diào)遞增的約束條件；通過(guò)在原有跳躍索引結(jié)構(gòu)上加入左側(cè)跳躍指針的方法，索引節(jié)點(diǎn)可以根據(jù)待加入節(jié)點(diǎn)值的大小將其納入自己的左側(cè)或右側(cè)跳躍指針，使隨機(jī)跳躍索引可以支持多個(gè)序列的隨機(jī)插入，顯著的提高了Jump Index建立索引的效率；它與后者有著

31、相同的查找效率；隨機(jī)跳躍索引中的每一個(gè)節(jié)點(diǎn)到根節(jié)點(diǎn)的路徑固定且唯一，保證了索引的可信賴性。仿真試驗(yàn)結(jié)果表明：其建立索引的效率明顯優(yōu)于后者，兩者的查找效率也非常接近。參考文獻(xiàn):1 Q. Zhu and W. W. Hsu. Fossilized index: the linchpin of trustworthy non-alterable electronic records/Proceedings of the ACM International Conference on Management of Data, Baltimore USA, 2005. New York: ACM Pres

32、s, 2005: 395-406.2 Soumyadeb Mitra, Windsor W. Hsu, Marianne Winslett. Trustworthy keyword search for regulatory-compliant records retention/ Proceedings of the 32nd international conference on Very large data bases, Seoul Korea, 2006:1001-1012.3 Kyriacos Pavlou, Richard T. Snodgrass, Forensic analy

33、sis of database tampering/Proceedings of the 2006 ACM SIGMOD international conference on Management of data, Chicago, 2006. New York: ACM Press, 2006: 109-120. 4 Nikolai Joukov, Harry Papaxenopoulos, Erez Zadok, Secure deletion myths, issues, and solutions/Proceedings of the second ACM workshop on S

34、torage security and survivability, Alexandria, 2006. New York: ACM Press, 2006: 61-66.5 M.-S. Kim, K.-Y. Whang, J.-G. Lee, and M.-J. Lee. n-Gram/2L: a space and time efficient two-Level n-Gram inverted index structure/Proceedings of the 31st international conference on Very large data bases, Trondhe

35、im Norway, 2005: 325-336.6 M. F. Fontoura, A. Neumann, S. Rajagopalan, E. Shekita, and J. Zien. High performance index build algorithms for intranet search engines/ Proceedings of the Thirtieth international conference on Very large data bases, Toronto Canada, 2004: 1122- 1133.7 Craig Silverstein, H

36、annes Marais, Monika Henzinger, and Michael Moricz. Analysis of a very large web search engine query log. ACM SIGIR Forum, 1999, 33(1): 612.8 Ethan Miller, Dan Shen, Junli Liu, and Charles Nicholas. Performance and scalability of a large-scale n-gram based information retrieval system. Journal of Di

37、gital Information, 2000,1(5): 125. 9 Ian H. Witten, Alistair. Moffat, and Timothy C. Bell. Managing Gigabytes: Compressing and Indexing Documents and Images. 2nd Edition. San Francisco: Morgan Kaufmann Publishers, 1999.10 Hector Garcia-Molina, Jeffrey D. Ullman, and Jennifer D. Widom. Database Syste

38、m Implementation. Upper Saddle River, New Jersey: Prentice-Hall, 2000.LIU Feng-Chen, born in 1982, Ph.D. candidate. His research interests include information retrieval, retrieval algorithm and intelligent algorithm.Huang He, born in 1972, Ph.D., associate professor, M.S supervisor. His research int

39、erests include computer network and information security.LIU Qin-Wen, born in 1966, Ph.D. lecture. His research interests include cluster, security of database and distributed information system.DING Yong-Sheng, born in 1967, Ph.D., Professor, Ph.D. supervisor. His research interests include intelli

40、gent systems, network intelligence, DNA computing, artificial immune systems, bio-network, bioinformatics, digitalized textile and garment, intelligent decision making and analysis.劉鳳晨,男,1982年生,甘肅蘭州人,博士研究生,主要研究方向：信息檢索,智能算法,檢索算法,E-mail: aric. 黃河,男, 1972年出生,安徽淮南人, 博士后,副教授，碩士生導(dǎo)師,主要研究方向：計(jì)算機(jī)網(wǎng)絡(luò)與信息安全, E-ma

41、il: huanghe. 劉慶文,男, 1966年出生,山東濟(jì)南人,博士后，講師，主要研究方向：數(shù)據(jù)庫(kù)、分布式信息處理E-mail: netperson.丁永生,男, 1967年出生,安徽懷寧人,博士,教授，博士生導(dǎo)師，從事智能系統(tǒng)、網(wǎng)絡(luò)智能、DNA計(jì)算、人工免疫系統(tǒng)、生物網(wǎng)絡(luò)結(jié)構(gòu)、生物信息學(xué)、數(shù)字化紡織服裝、智能決策與分析等研究, E-mail: ysding本課題得到:國(guó)防科工委項(xiàng)目(A2120061061), 上海市科學(xué)技術(shù)委員會(huì)重點(diǎn)基礎(chǔ)研究項(xiàng)目（08JC1400100），上海市人才發(fā)展資金（001），上海市領(lǐng)軍人才后備人選專項(xiàng)資金資助.聯(lián)系作者:劉鳳晨, Email: aric 電話:

42、21-67792323BackgroundThis research is partly supported by the Commission of Science Technology and Industry of China under grant No. A2120061061, Project of the Shanghai Committee of Science and Technology (No. 08JC1400100), Shanghai Talent Developing Foundation (No. 001), Specialized Foundation for Excellent Talent from Shanghai.In the recent few years, the trustworthy problem in write once read many devices is raised by many researches. To address this issue some researchers proposed a kind o