基于壓縮的海量不完整數(shù)據(jù)近似查詢(xún)方法

王　妍　劉賡浩　王俊陸　宋寶燕

1(遼寧大學(xué)信息學(xué)院　沈陽(yáng)　110036)

2　　　(東北大學(xué)信息與工程學(xué)院　沈陽(yáng)　110819)

(wang_yan@lnu.edu.cn)

?

基于壓縮的海量不完整數(shù)據(jù)近似查詢(xún)方法

王妍1,2劉賡浩1王俊陸1宋寶燕1

1(遼寧大學(xué)信息學(xué)院沈陽(yáng)110036)

2(東北大學(xué)信息與工程學(xué)院沈陽(yáng)110819)

(wang_yan@lnu.edu.cn)

A Compression-Based Approximate Query Method for Massive Incomplete Data

Wang Yan1,2, Liu Genghao1, Wang Junlu1, and Song Baoyan1

1(SchoolofInformation,LiaoningUniversity,Shenyang110036)

2(SchoolofInformationScienceandEngineering,NortheasternUniversity,Shenyang110819)

AbstractWith the explosive increase of data, incomplete data are widespread. Traditional methods of data repair will cause high processing cost for mass data, and cannot be fully restored. Thus the approximate querying on these huge amounts of incomplete data for meeting the given requirements attracted greater attention from academics. Therefore, this paper proposes an approximate query method for massive incomplete data based on compression. Tagging the missing attribute value field and finding out the frequent query conditions, this method compresses these data based on the statistical frequent query conditions, and establishes the corresponding indexes. According to the attribute partition rules, index files are compressed again in order to further save storage space. In the stage of query, this method uses encoding dictionary to make selection and projection operations on the index compression files for getting approximate query results of incomplete data in the end. Experimental results show that this method can quickly locate the position of incomplete data compression, improve the query efficiency, save the storage space, and ensure the integrity of the query results.

Key wordsincomplete data; approximate query; data compression; index; encoding dictionary

摘要隨著數(shù)據(jù)的爆炸式增加，不完整數(shù)據(jù)普遍存在，傳統(tǒng)的數(shù)據(jù)修復(fù)方法對(duì)于海量數(shù)據(jù)處理代價(jià)過(guò)高，且不能徹底修復(fù)，在這些不完整的海量數(shù)據(jù)上進(jìn)行滿(mǎn)足給定需求的近似查詢(xún)引起了學(xué)術(shù)界的關(guān)注.因此，提出一種基于壓縮的海量不完整數(shù)據(jù)近似查詢(xún)方法，該方法對(duì)屬性值缺失字段進(jìn)行標(biāo)記，根據(jù)頻繁查詢(xún)條件對(duì)標(biāo)記后的數(shù)據(jù)進(jìn)行壓縮，并建立對(duì)應(yīng)索引；根據(jù)屬性劃分對(duì)索引文件再次壓縮以節(jié)省存儲(chǔ)空間，采用編碼字典對(duì)索引壓縮文件進(jìn)行選擇和投影操作，最終獲得不完整數(shù)據(jù)的近似查詢(xún)結(jié)果.實(shí)驗(yàn)表明，該方法能夠快速定位不完整數(shù)據(jù)的壓縮位置，提高了查詢(xún)效率，節(jié)省了存儲(chǔ)空間，并且保證了查詢(xún)結(jié)果的完整性.

關(guān)鍵詞不完整數(shù)據(jù)；近似查詢(xún)；數(shù)據(jù)壓縮；索引；編碼字典

隨著信息技術(shù)的發(fā)展，數(shù)據(jù)規(guī)模不斷增加，尤其是在以計(jì)算機(jī)和互聯(lián)網(wǎng)為基礎(chǔ)的應(yīng)用中數(shù)據(jù)更是以指數(shù)形式增長(zhǎng).而在海量數(shù)據(jù)帶來(lái)豐富信息的同時(shí)，也帶來(lái)許多質(zhì)量問(wèn)題，這些問(wèn)題嚴(yán)重地制約著數(shù)據(jù)的應(yīng)用價(jià)值[1-2].其中，數(shù)據(jù)缺失是一個(gè)常見(jiàn)的現(xiàn)象.不合理地處理缺失數(shù)據(jù)將造成錯(cuò)誤結(jié)果，甚至是嚴(yán)重的損失[3].因此，如何有效存儲(chǔ)和管理有屬性值缺失的海量數(shù)據(jù),即海量不完整數(shù)據(jù)，是研究的重中之重.

近幾年來(lái)，許多學(xué)者對(duì)海量不完整數(shù)據(jù)的處理進(jìn)行了研究.現(xiàn)有的方法在對(duì)海量不完整數(shù)據(jù)進(jìn)行操作之前，需要對(duì)其進(jìn)行數(shù)據(jù)清洗[4-7]，然后再對(duì)清洗后的“干凈”數(shù)據(jù)進(jìn)行壓縮存儲(chǔ)[8-11]和管理.然而，對(duì)于海量數(shù)據(jù)而言，先進(jìn)行數(shù)據(jù)清洗再操作數(shù)據(jù)有很多弊端.首先，基于數(shù)據(jù)的海量性，數(shù)據(jù)清洗的代價(jià)將會(huì)非常大；其次，清洗的結(jié)果會(huì)受到很多因素的影響，可能會(huì)引入新的“噪聲”導(dǎo)致清洗結(jié)果并不準(zhǔn)確；此外，數(shù)據(jù)清洗還會(huì)產(chǎn)生時(shí)效性問(wèn)題，結(jié)果就是很多時(shí)效數(shù)據(jù)將失去意義.因此，我們的工作就是越過(guò)數(shù)據(jù)清洗直接對(duì)海量不完整數(shù)據(jù)進(jìn)行壓縮存儲(chǔ)以及管理，而現(xiàn)有的壓縮算法都是對(duì)完備數(shù)據(jù)的壓縮，所以我們要設(shè)計(jì)一種新的適用于不完整數(shù)據(jù)的壓縮算法，以及與其相對(duì)應(yīng)的查詢(xún)算法.由此可見(jiàn)，針對(duì)海量不完整數(shù)據(jù)的壓縮與查詢(xún)處理方法的研究是十分必要的[12].

針對(duì)上述問(wèn)題，本文提出了一種基于壓縮的海量不完整數(shù)據(jù)近似查詢(xún)方法(compression-based approximate query for massive incomplete data, AQ-MI),該方法可以快速地定位查詢(xún)數(shù)據(jù)的壓縮位置，提高查詢(xún)效率，還能夠大幅度地減少存儲(chǔ)空間，并且保證查詢(xún)結(jié)果的完整性.本文的主要貢獻(xiàn)有3點(diǎn)：

1) 提出一種面向海量不完整數(shù)據(jù)的壓縮策略，利用頻繁查詢(xún)條件索引法，在被標(biāo)記數(shù)據(jù)壓縮時(shí)將每一元組所滿(mǎn)足的不確定條件和確定性條件作為索引存儲(chǔ)于索引表中.采用屬性值缺失字段標(biāo)記策略，對(duì)帶有標(biāo)記的字段進(jìn)行重復(fù)壓縮，以保證查詢(xún)結(jié)果的完整性和可信性.還提出了一種基于Attr-1的索引文件壓縮方法，進(jìn)一步減少存儲(chǔ)空間.

2) 提出一種無(wú)解壓近似查詢(xún)方法，查詢(xún)時(shí)分析查詢(xún)語(yǔ)句，對(duì)索引壓縮文件進(jìn)行相應(yīng)的選擇和投影操作，根據(jù)獲得的被標(biāo)記數(shù)據(jù)壓縮地址，最終得到近似查詢(xún)結(jié)果.

3) 設(shè)計(jì)了詳細(xì)的性能評(píng)估實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果表明AQ-MI算法可以快速地定位查詢(xún)數(shù)據(jù)的壓縮位置，提高查詢(xún)效率，還能夠大幅度地減少存儲(chǔ)空間，并且保證查詢(xún)結(jié)果的完整性.

1相關(guān)工作

文獻(xiàn)[4-7]是常見(jiàn)的對(duì)不完整數(shù)據(jù)的清洗方法.文獻(xiàn)[4]采用基于記錄刪除的數(shù)據(jù)清洗策略，在查詢(xún)之前先刪除不完整的記錄，再在“干凈的”數(shù)據(jù)庫(kù)上進(jìn)行計(jì)算查詢(xún)，雖然得到唯一確定的結(jié)果，但丟失了部分有價(jià)值的信息.文獻(xiàn)[5-7]采用基于數(shù)據(jù)填充的數(shù)據(jù)清洗策略，在查詢(xún)之前用一定值去填充屬性值缺失的字段，從而使信息完備化，然而這種方法只是在一定程度上補(bǔ)以主觀(guān)的估計(jì)值，不一定完全符合客觀(guān)事實(shí)，而且對(duì)缺失值不正確的填充往往將新的噪聲引入數(shù)據(jù)，使查詢(xún)產(chǎn)生錯(cuò)誤的結(jié)果.

對(duì)海量數(shù)據(jù)的壓縮，最常見(jiàn)的方法是基于編碼字典的壓縮[8-10]，這類(lèi)方法采用按列存儲(chǔ)的思想對(duì)數(shù)據(jù)進(jìn)行壓縮，將對(duì)原始數(shù)據(jù)的查詢(xún)轉(zhuǎn)化為對(duì)壓縮編碼位的操作.文獻(xiàn)[8-9]是對(duì)串表壓縮算法LZW進(jìn)行改進(jìn)，主要思想是利用較短的碼字表示較長(zhǎng)的字符串來(lái)實(shí)現(xiàn)壓縮.文獻(xiàn)[10]應(yīng)用一種對(duì)稱(chēng)編碼SVC，進(jìn)一步減短對(duì)應(yīng)碼字長(zhǎng)度，提高測(cè)試數(shù)據(jù)的壓縮效果.采用這種編碼字典方法可以實(shí)現(xiàn)不解壓直接查詢(xún)，提高了效率，但是增加了匹配字典和維護(hù)字典的代價(jià)，不適用于更新頻繁的系統(tǒng).文獻(xiàn)[11]提出一種海量數(shù)據(jù)壓縮存儲(chǔ)結(jié)構(gòu)，在數(shù)據(jù)壓縮時(shí)，為每條元組計(jì)算相應(yīng)的索引項(xiàng)，該方法雖然在查詢(xún)時(shí)可以提高效率，但對(duì)于海量數(shù)據(jù)而言，索引的規(guī)模也很大，即增加了大量額外的存儲(chǔ)空間.

就目前的海量不完整數(shù)據(jù)的存儲(chǔ)和管理方法而言，很多方面都存在弊端.現(xiàn)有方法都是對(duì)原始數(shù)據(jù)進(jìn)行數(shù)據(jù)清洗后，再在完備數(shù)據(jù)上進(jìn)行壓縮和查詢(xún)，然而對(duì)海量數(shù)據(jù)的清洗存在清洗代價(jià)大、清洗結(jié)果不準(zhǔn)確以及時(shí)效性差等問(wèn)題.因此，本文提出AQ-MI方法，越過(guò)數(shù)據(jù)清洗直接對(duì)海量不完整數(shù)據(jù)進(jìn)行壓縮和查詢(xún)，該方法可以快速地定位查詢(xún)數(shù)據(jù)的壓縮位置，提高查詢(xún)效率，還能夠大幅度地減少存儲(chǔ)空間，并且保證查詢(xún)結(jié)果的完整性.

2定義和數(shù)據(jù)結(jié)構(gòu)

2.1相關(guān)定義

由于對(duì)海量數(shù)據(jù)的操作需要較高的時(shí)間和空間代價(jià)，因此有查詢(xún)類(lèi)型少、查詢(xún)語(yǔ)句簡(jiǎn)單固定、更新和刪除頻率低等特點(diǎn).我們的目的是改善使用頻繁的數(shù)據(jù)操作的響應(yīng)時(shí)間.假設(shè)對(duì)于一個(gè)海量數(shù)據(jù)庫(kù)應(yīng)用，經(jīng)過(guò)統(tǒng)計(jì)后可以獲得頻繁使用的數(shù)據(jù)操作語(yǔ)句，即查詢(xún)語(yǔ)句中WHERE后出現(xiàn)的查詢(xún)條件，將這些查詢(xún)條件分為確定性查詢(xún)條件和不確定查詢(xún)條件.

定義1. 確定性查詢(xún)條件Def_Query.查詢(xún)下發(fā)前已經(jīng)確定的查詢(xún)條件，一般為頻繁使用的固定范圍查詢(xún)，這類(lèi)查詢(xún)大多是查詢(xún)某一屬性值是否超過(guò)設(shè)定的閾值，如“Temperature>35”.確定性查詢(xún)條件的屬性名和屬性值固定，作為一個(gè)整體出現(xiàn).

定義2. 不確定查詢(xún)條件Undef_Query.查詢(xún)下發(fā)前不能完全確定的查詢(xún)條件，一般為頻繁使用的不固定等值查詢(xún)，這類(lèi)查詢(xún)大多是查詢(xún)某一屬性值是否存在于記錄中，如“Username=***”.不確定查詢(xún)條件的屬性名固定，屬性值可變.

2.2基本數(shù)據(jù)結(jié)構(gòu)

經(jīng)過(guò)統(tǒng)計(jì)獲得所有確定性查詢(xún)條件和不確定查詢(xún)條件后，在壓縮存儲(chǔ)時(shí)將每一條元組所滿(mǎn)足的不確定查詢(xún)條件的屬性值和確定性查詢(xún)條件作為索引存儲(chǔ)于數(shù)據(jù)庫(kù)中，同時(shí)將元組存放到相應(yīng)的待壓縮緩存塊中.當(dāng)某一緩存塊裝滿(mǎn)后，將其按順序進(jìn)行壓縮存儲(chǔ)，并在數(shù)據(jù)庫(kù)中存儲(chǔ)元組所在壓縮文件地址.索引表結(jié)構(gòu)和壓縮文件地址表結(jié)構(gòu)分別如圖1和圖2所示:

Fig. 1　Structure of index table.圖1　索引表結(jié)構(gòu)

Fig. 2　Structure of compressed file address table.圖2　壓縮文件地址表結(jié)構(gòu)

圖1中，Id為索引序號(hào)，Tp_Id為元組序號(hào)，字段Undef_Val_i為當(dāng)前元組第i個(gè)不確定查詢(xún)條件的屬性值.字段Def_Query以位編碼形式存儲(chǔ)當(dāng)前元組所滿(mǎn)足的確定性查詢(xún)條件.對(duì)于n個(gè)確定性查詢(xún)條件Q1,Q2,…,Qn，設(shè)當(dāng)前元組的字段Def_Query的位編碼為B1B2…Bn，若當(dāng)前元組滿(mǎn)足條件Qi，則Bi=1；否則Bi=0.

圖2中，Block_Id為當(dāng)前元組所在緩存塊的序號(hào)，字段Address為緩存塊壓縮后對(duì)應(yīng)的壓縮文件地址.

通過(guò)將索引表和地址表在屬性Block_Id上的連接便能夠得到完整的索引文件.值得注意的是，不同Def_Query值對(duì)應(yīng)不同的緩存塊，也就對(duì)應(yīng)不同的壓縮文件地址.而當(dāng)某一緩存塊壓縮存儲(chǔ)后，將為Block_Id賦一個(gè)新的值，因此相同的Def_Query值也可能對(duì)應(yīng)不同的緩存塊和壓縮文件地址.

3基于壓縮的海量不完整數(shù)據(jù)近似查詢(xún)算法

3.1不完整數(shù)據(jù)的標(biāo)記

傳統(tǒng)的數(shù)據(jù)清洗方法很難將不完整數(shù)據(jù)徹底清洗干凈，還會(huì)造成信息損失，降低效率.因此，我們希望不對(duì)原始數(shù)據(jù)清洗，直接進(jìn)行存儲(chǔ)和管理，以此來(lái)避免信息的損失.實(shí)際上，只要能在數(shù)據(jù)庫(kù)中把完整的和不完整的分量標(biāo)識(shí)出來(lái)，并在查詢(xún)回答中正確地保持標(biāo)識(shí)，那么無(wú)論是完整的還是不完整的信息，只要它符合查詢(xún)條件，都將保留在查詢(xún)結(jié)果中，信息丟失問(wèn)題自然不存在.

根據(jù)上述思想，在預(yù)處理階段，掃描一次原始數(shù)據(jù)D，將屬性值缺失的字段用“*”進(jìn)行標(biāo)記，標(biāo)記后的數(shù)據(jù)記為D*.一個(gè)簡(jiǎn)單例子如表1所示，用標(biāo)記“*”來(lái)區(qū)分?jǐn)?shù)據(jù)庫(kù)的完整和不完整分量.

Table 1Area Temperature Information Table with “*” Mark

表1　用“*”標(biāo)記的地區(qū)溫度信息表TempInfo

假設(shè)查詢(xún)語(yǔ)句:

SELECTPlace,Temperature,Duration

FROMTempInfo

WHERETemperature>19

ANDDuration>8.

則查詢(xún)結(jié)果如表2所示：

Table 2　Query Result

如表2所示，被“*”標(biāo)記的字段為屬性值缺失字段，它可以滿(mǎn)足任何查詢(xún)條件，因此在查詢(xún)計(jì)算中可以正確地保持標(biāo)記語(yǔ)義，使得查詢(xún)結(jié)果可信有意義.

3.2D*數(shù)據(jù)的壓縮存儲(chǔ)

在對(duì)原始數(shù)據(jù)掃描標(biāo)記后，獲得D*數(shù)據(jù)，根據(jù)統(tǒng)計(jì)的頻繁查詢(xún)條件壓縮數(shù)據(jù)至不同壓縮文件并建立對(duì)應(yīng)索引，然后壓縮索引文件來(lái)進(jìn)一步節(jié)省存儲(chǔ)空間.因此，在壓縮存儲(chǔ)階段，分為對(duì)D*數(shù)據(jù)的壓縮和對(duì)索引文件的壓縮.

3.2.1D*數(shù)據(jù)的壓縮

對(duì)于海量不完整數(shù)據(jù)D*，假設(shè)D*包含m條元組，n個(gè)屬性.進(jìn)行壓縮處理后，得到索引文件和壓縮數(shù)據(jù).假設(shè)索引文件包含i條元組、j個(gè)屬性，則i≥m且j?n.圖3是D*數(shù)據(jù)的壓縮示意圖：

Fig. 3　The process of D*data compression.圖3　D*數(shù)據(jù)壓縮示意圖

對(duì)于D*的每一條元組t，首先計(jì)算t所滿(mǎn)足的確定性查詢(xún)條件的Def_Query值，將t寫(xiě)入為該Def_Query分配的待壓縮緩存塊BlockDef_Query中，然后將t的不確定查詢(xún)條件的屬性值Undef_Vals和Def_Query作為索引項(xiàng)存儲(chǔ)于數(shù)據(jù)庫(kù)索引表中，同時(shí)在索引表中記錄元組t所在的待壓縮緩存塊BlockDef_Query的序號(hào)Block_IdDef_Query.若緩存塊BlockDef_Query已滿(mǎn)，則采用某一壓縮算法對(duì)BlockDef_Query進(jìn)行壓縮.在壓縮存儲(chǔ)的同時(shí)，將獲得該壓縮文件的地址AddressDef_Query，最后把Block_IdDef_Query和AddressDef_Query序?qū)?xiě)入地址表.下面舉一個(gè)簡(jiǎn)單的例子，如表3所示：

Table 3　Area Temperature Information Table

表3為地區(qū)溫度信息表，假設(shè)不確定查詢(xún)條件為Place=***；確定性查詢(xún)條件為T(mén)emperature>35，Duration>5.則經(jīng)過(guò)計(jì)算可得元組1的Def_Query值為10，元組2的Def_Query值為01.因此這2條記錄將分別壓縮至2個(gè)壓縮文件，它們的索引表和地址表連接后所得索引文件內(nèi)容如表4所示.

Table 4　Example 1 of Index File

對(duì)于標(biāo)記為“*”的屬性值缺失字段，它可能是任何值，那么就應(yīng)該滿(mǎn)足任何查詢(xún)條件，為了保證查詢(xún)結(jié)果可信有意義，需要對(duì)含有屬性標(biāo)記有“*”的元組進(jìn)行重復(fù)壓縮.即對(duì)于含有“*”標(biāo)記字段的元組t，可能會(huì)計(jì)算得出2個(gè)甚至多個(gè)Def_Query值，則需要將t分別寫(xiě)入為這些Def_Query值分配的多個(gè)待壓縮緩存塊BlockDef_Query中，后續(xù)的處理過(guò)程同未含有標(biāo)記字段的元組.

對(duì)表3的例子進(jìn)行修改，如表5所示：

Table 5Area Temperature Information Table with “*” Mark

表5　用“*”標(biāo)記的地區(qū)溫度信息表

如果將上述例子中的信息表修改為如表5所示，則元組2的Def_Query值為01或者11，因此需要將該元組同時(shí)壓縮至01和11對(duì)應(yīng)的2個(gè)壓縮文件中.其索引文件如表6所示：

Table 6　Example 2 of Index File

3.2.2D*數(shù)據(jù)的壓縮優(yōu)化

在統(tǒng)計(jì)確定性查詢(xún)條件時(shí)，可能會(huì)出現(xiàn)許多冗余條件，比如經(jīng)統(tǒng)計(jì)，頻繁使用的查詢(xún)條件有：Temperature>35和Temperature>55.如此將會(huì)使得索引表中屬性Def_Query的位編碼字段長(zhǎng)度增加1 b，那么多個(gè)條件的集合對(duì)應(yīng)的位編碼將會(huì)更加冗余.如此一來(lái)，不僅會(huì)增加索引文件的存儲(chǔ)空間，還會(huì)降低查詢(xún)計(jì)算的效率.

針對(duì)這個(gè)問(wèn)題，本文的優(yōu)化策略是將有包含關(guān)系的確定性條件進(jìn)行削減，剔除掉被包含的條件，只保留最大滿(mǎn)足條件.如上述例子的2個(gè)條件，只保留Temperature>35.這將大大減少索引編碼的長(zhǎng)度，節(jié)省了存儲(chǔ)空間，同時(shí)，在查詢(xún)索引匹配時(shí)效率也將更高.雖然這樣處理會(huì)使得最終的查詢(xún)結(jié)果是近似的(包含精確結(jié)果)，但對(duì)于海量數(shù)據(jù)而言，快速地返回滿(mǎn)足需求的近似結(jié)果是值得提倡的[13].

3.2.3基于Attr-1的索引文件壓縮

根據(jù)D*數(shù)據(jù)的壓縮過(guò)程可知，為了提高查詢(xún)效率，D*數(shù)據(jù)的每個(gè)元組都建立了一條或多條索引，不僅如此，索引表的字段Undef_Val_i數(shù)量未知，它是由不確定查詢(xún)條件來(lái)確定的，因此索引表可能是一張寬表，如此不論是從元組數(shù)量還是從屬性數(shù)量上都增加了額外的存儲(chǔ)空間.為了進(jìn)一步減少存儲(chǔ)空間，對(duì)索引文件進(jìn)行壓縮.而為了不增加除了D*數(shù)據(jù)查詢(xún)時(shí)的解壓耗時(shí)，對(duì)索引文件采用編碼字典方式進(jìn)行壓縮，以便后期的無(wú)解壓查詢(xún).

對(duì)于D*數(shù)據(jù)的索引文件T，假設(shè)T包含n個(gè)屬性，共有m條元組.對(duì)于屬性Ai中出現(xiàn)的所有候選值，按照壓縮模式中Ai對(duì)應(yīng)的編碼模式調(diào)用不同的編碼方法.T中所有屬性經(jīng)壓縮處理后，得到編碼字典和索引壓縮文件.圖4是索引文件的壓縮示意圖：

Fig. 4　The process of index file compression.圖4　Attr-1索引文件壓縮示意圖

如圖4所示，索引文件中屬性Def_Query的值已經(jīng)是位編碼類(lèi)型，因此無(wú)需對(duì)該屬性進(jìn)行壓縮編碼，僅僅對(duì)索引文件表的其他Attr-1個(gè)屬性依據(jù)壓縮模式配置文件進(jìn)行編碼，而屬性Def_Query的所有數(shù)據(jù)則直接拷貝到索引壓縮文件末尾，即屬性Def_Query對(duì)應(yīng)的數(shù)據(jù)不出現(xiàn)在編碼字典中.

在壓縮編碼時(shí)候，不同屬性可以采用不同的編碼方式，而且還要兼顧存儲(chǔ)空間和查詢(xún)效率，因此采用K-of-N編碼(K-of-Nencoding)[14].假設(shè)壓縮模式配置文件規(guī)定索引文件的全部屬性(除Def_Query)的編碼方式皆為K-of-N編碼，對(duì)表6所示的索引文件進(jìn)行壓縮編碼，得到的編碼字典如表7～11所示：

Table 7　Example of Encoding Dictionary for Id

Table 8　Example of Encoding Dictionary for Tp_Id

Table 9　Example of Encoding Dictionary for Place

Table 10　Example of Encoding Dictionary for Block_Id

Table 11　Example of Encoding Dictionary for Address

表6所示的索引文件壓縮后對(duì)應(yīng)的索引壓縮文件如表12所示：

Table 12　Example of Index Compression File

表7至表12的例子只是為了解釋壓縮原理，并不能很好地顯示出壓縮效果.而實(shí)際中的數(shù)據(jù)值往往占據(jù)很大的存儲(chǔ)空間，比如某字段值為@addr4031331963，此時(shí)將其壓縮編碼為001就會(huì)明顯顯示出壓縮的效果.

3.2.4海量不完整數(shù)據(jù)D*壓縮算法

如算法1所示為海量不完整數(shù)據(jù)D*的壓縮算法，壓縮過(guò)程包括2個(gè)階段:1)將不完整數(shù)據(jù)D*根據(jù)確定性和不確定查詢(xún)條件進(jìn)行壓縮并建立對(duì)應(yīng)的索引;2)通過(guò)壓縮模式配置文件對(duì)階段1生成的索引文件進(jìn)行壓縮，以進(jìn)一步減少存儲(chǔ)空間.

算法1. 海量不完整數(shù)據(jù)D*壓縮算法.

輸入:海量不完整數(shù)據(jù)D*、索引壓縮模式配置文件C;

輸出:壓縮數(shù)據(jù)K、索引壓縮文件T、編碼字典M.

① for each元組t∈Rdo

② if (t不包含被標(biāo)記字段)

③ 計(jì)算t所滿(mǎn)足的確定性查詢(xún)條件的Def_Query值;

④ 將t寫(xiě)入為該Def_Query分配的待壓縮緩存塊BlockDef_Query中，設(shè)定其序號(hào)為Block_IdDef_Query;

⑤ else

⑥ 計(jì)算t所滿(mǎn)足的多個(gè)Def_Query值;

⑦ 將t重復(fù)寫(xiě)入這些Def_Query對(duì)應(yīng)的待壓縮緩存塊BlockDef_Query中，設(shè)定其序號(hào)為Block_IdDef_Query;

⑧ end if

⑨ 將t的不確定查詢(xún)條件的屬性值Undef_Vals，Def_Query，Block_IdDef_Query插入數(shù)據(jù)庫(kù)索引表;

⑩ if (BlockDef_Query已滿(mǎn))

根據(jù)算法1的描述可知，階段1以元組為單位對(duì)D*數(shù)據(jù)進(jìn)行計(jì)算并進(jìn)行壓縮，因此時(shí)間復(fù)雜度為O(N)；階段2分別以屬性和元組為單位，對(duì)索引文件進(jìn)行了一次掃描，2次掃描分別生成了編碼字典和索引壓縮文件，因此時(shí)間復(fù)雜度為O(N).所以，海量不完整數(shù)據(jù)D*的壓縮算法時(shí)間復(fù)雜度為O(N).

3.3壓縮后D*數(shù)據(jù)的近似查詢(xún)

3.3.1近似查詢(xún)

所謂近似查詢(xún)，體現(xiàn)在2個(gè)方面：1)在統(tǒng)計(jì)頻繁確定性查詢(xún)條件時(shí)，為了節(jié)省存儲(chǔ)空間并且提高查詢(xún)效率，將被包含的確定性條件剔除，如此在查詢(xún)時(shí)便會(huì)得到包含精確結(jié)果的近似查詢(xún)結(jié)果；2)在查詢(xún)結(jié)果中帶有*標(biāo)記的不完整數(shù)據(jù).由于索引的存在可以快速獲得滿(mǎn)足查詢(xún)條件的壓縮文件地址集合，因此在查詢(xún)處理階段，主要工作就是對(duì)索引壓縮文件的無(wú)解壓查詢(xún)，其本質(zhì)就是通過(guò)對(duì)查詢(xún)語(yǔ)句的解析，將對(duì)原始數(shù)據(jù)的查詢(xún)轉(zhuǎn)化為對(duì)壓縮編碼位的選擇和投影操作.

3.3.2選擇操作

基于本文提出的壓縮和查詢(xún)處理方法的特殊性，在無(wú)解壓查詢(xún)時(shí)可能涉及到的選擇操作僅是對(duì)屬性Undef_Vals和屬性Def_Query的等值操作，因此對(duì)其他操作不做贅述.依舊以K-of-N編碼為例，假設(shè)要進(jìn)行的等值操作為Undef_Val_i=X，X的編碼為xnxn-1…x2x1，待比較數(shù)據(jù)的編碼為anan-1…a2a1.等值操作規(guī)則如下：

K-of-N編碼由于采用了N位中有K位為1的規(guī)則，因此只需要知道這些為1的編碼位具體是哪些位，就可以唯一地確定一個(gè)編碼.假設(shè)X的編碼xnxn-1…x2x1中，xi1xi2…xik為編碼為1的位，則在待比較的編碼中，只有編碼ai1ai2…aik對(duì)應(yīng)的編碼也全部為1，才是和B相等的數(shù)據(jù).該操作要處理的編碼位為K位，以上過(guò)程可形式化地表示為

(1)

同理可得不等值操作的形式化表示為

(2)

需要注意的是，屬性Def_Query本身就是位編碼形式，因此K-of-N編碼的選擇操作規(guī)則不適用于屬性Def_Query.因?yàn)镈ef_Query的值是由若干確定性查詢(xún)條件生成的，所以需要比較每一位才能知道是否等值.假設(shè)要進(jìn)行的等值操作為Def_Query=X，X的編碼為xnxn-1…x2x1，待比較數(shù)據(jù)的編碼為anan-1…a2a1.等值操作規(guī)則如下：

對(duì)于待比較編碼anan-1…a2a1，如果其上所有編碼位上的編碼與X的編碼xnxn-1…x2x1一一對(duì)應(yīng)地全部相同，那么該編碼就與X的編碼相等.操作規(guī)則形式化描述為

(3)

同理可得不等值操作的形式化表示為

(4)

3.3.3投影操作

由于采用了按列壓縮和存儲(chǔ)的基本思想，因此對(duì)索引壓縮文件的投影操作相對(duì)來(lái)說(shuō)比較簡(jiǎn)單.投影操作在所有的選擇操作結(jié)束后執(zhí)行，選擇操作結(jié)束后獲得滿(mǎn)足選擇條件的元組集合.對(duì)于索引壓縮文件來(lái)說(shuō)，僅是對(duì)屬性Address進(jìn)行投影操作，因此，對(duì)于元組集合中的每一條元組對(duì)應(yīng)的屬性Address，在編碼字典中查找對(duì)應(yīng)的原始數(shù)據(jù)值，在這些原始值集合中去掉重復(fù)的數(shù)據(jù)，就得到投影操作的最終結(jié)果.

3.3.4海量不完整數(shù)據(jù)D*查詢(xún)算法

在進(jìn)行無(wú)解壓查詢(xún)時(shí)，需要由查詢(xún)條件來(lái)構(gòu)造查詢(xún)索引.查詢(xún)索引構(gòu)造方法如下：首先分析查詢(xún)語(yǔ)句，將其查詢(xún)條件用不確定查詢(xún)條件和位編碼形式的確定性查詢(xún)條件來(lái)表示.如此，原查詢(xún)語(yǔ)句的查詢(xún)條件就轉(zhuǎn)化為由Undef_Query和Def_Query組成的查詢(xún)索引.

如果查詢(xún)索引中只存在Def_Query，則直接以Def_Query對(duì)索引壓縮文件進(jìn)行選擇操作，對(duì)得到的選擇結(jié)果在屬性Address上做投影操作即可得到滿(mǎn)足查詢(xún)條件的D*數(shù)據(jù)的壓縮地址集合，根據(jù)地址集合解壓文件后即可得到查詢(xún)結(jié)果.如果查詢(xún)索引中存在Undef_Query，則需要在編碼字典中找到Undef_Query對(duì)應(yīng)的編碼，然后對(duì)索引壓縮文件進(jìn)行后續(xù)操作.海量不完整數(shù)據(jù)D*查詢(xún)算法如算法2所示：

算法2. 海量不完整數(shù)據(jù)D*查詢(xún)算法.

輸入:查詢(xún)語(yǔ)句Q、編碼字典M、索引壓縮文件T、壓縮數(shù)據(jù)K;

輸出:查詢(xún)結(jié)果Result.

① 解析查詢(xún)語(yǔ)句Q，得到Undef_Query和Def_Query構(gòu)造查詢(xún)索引X;*選擇操作*

② if (Undef_Query≠Null)

③ for eachUndef_Val∈Undef_Querydo

④ 在編碼字典M中查找對(duì)應(yīng)的編碼;

⑤ 采用式(1)(2)對(duì)T進(jìn)行選擇操作;

⑥ end for

⑦ end if

⑧ if (Def_Query≠Null)

⑨ 采用式(3)(4)對(duì)T進(jìn)行選擇操作;

⑩ end if

根據(jù)算法2的描述可知，在選擇操作中，最好情況下對(duì)Def_Query進(jìn)行選擇操作，時(shí)間復(fù)雜度為O(1)；最壞情況下對(duì)Undef_Query中的多個(gè)條件進(jìn)行選擇操作，時(shí)間復(fù)雜度為O(N)，因此選擇操作時(shí)間復(fù)雜度為O(N).在投影操作中，需要對(duì)編碼字典進(jìn)行一次掃描，所以投影操作時(shí)間復(fù)雜度為O(N).最后根據(jù)查詢(xún)到的地址集合將查詢(xún)結(jié)果依次解壓出來(lái)，時(shí)間復(fù)雜度為O(N).所以，海量不完整數(shù)據(jù)D*的查詢(xún)算法時(shí)間復(fù)雜度為O(N).

3.4不完整數(shù)據(jù)多重壓縮的優(yōu)化

根據(jù)2.2.1節(jié)的描述，在對(duì)含有*標(biāo)記的屬性的元組進(jìn)行壓縮的時(shí)候，會(huì)涉及到同一元組的多重壓縮.在只有1個(gè)*屬性滿(mǎn)足確定性查詢(xún)條件的情況下，該元組重復(fù)壓縮至2個(gè)壓縮文件；2個(gè)*屬性分別滿(mǎn)足2個(gè)確定性查詢(xún)條件時(shí)，將增加至4個(gè)壓縮文件,如此便呈現(xiàn)指數(shù)增長(zhǎng)，將會(huì)大大增加壓縮的代價(jià).

針對(duì)這個(gè)問(wèn)題，本文采用基于屬性重要性的主客觀(guān)權(quán)重分配策略.在對(duì)原始數(shù)據(jù)進(jìn)行壓縮存儲(chǔ)之前，首先對(duì)全部屬性進(jìn)行主觀(guān)權(quán)重分配并設(shè)定閾值，即根據(jù)專(zhuān)家經(jīng)驗(yàn)主觀(guān)評(píng)估各屬性之間的相對(duì)重要程度，相對(duì)重要的屬性分配相對(duì)較高權(quán)重.設(shè)定閾值為γ，則權(quán)重大于γ的屬性為重要屬性.在壓縮階段，只有當(dāng)*標(biāo)記的屬性權(quán)重大于閾值時(shí)才進(jìn)行多重編碼，否則只對(duì)元組編碼一次即可.

每次查詢(xún)之后，對(duì)查詢(xún)結(jié)果的屬性進(jìn)行客觀(guān)權(quán)重分配并反饋給初始主觀(guān)權(quán)重進(jìn)行調(diào)整.假設(shè)查詢(xún)結(jié)果為n個(gè)屬性對(duì)應(yīng)的m條元組記錄，則大體過(guò)程如下.

1) 采用m×n階特征值矩陣對(duì)查詢(xún)結(jié)果進(jìn)行聚類(lèi)如式(5)所示：

(5)

2) 計(jì)算得到特征值矩陣的*余子式，保證數(shù)據(jù)集的完備性；

3) 采用最大最小法建立模糊相似關(guān)系如式(6)所示：

(6)

4) 利用模糊等價(jià)閉包法求出模糊等價(jià)矩陣并確定分類(lèi)數(shù)目；

5) 依次求出刪除各屬性后的分類(lèi)數(shù)目以確定各屬性的重要性；

6) 根據(jù)重要性的大小確定各屬性的權(quán)重分配，若某屬性刪除后分類(lèi)數(shù)目沒(méi)有發(fā)生變化，則表明該屬性在查詢(xún)結(jié)果的整體性評(píng)價(jià)中是不必要的；

7) 將本次查詢(xún)得到的部分屬性客觀(guān)權(quán)重反饋給初始主觀(guān)權(quán)重進(jìn)行動(dòng)態(tài)調(diào)整，以便于新增數(shù)據(jù)的壓縮優(yōu)化.

采用基于屬性重要性的主客觀(guān)權(quán)重分配策略將在很大程度上減少壓縮耗時(shí)以及存儲(chǔ)空間，同時(shí)也保證了重要屬性在查詢(xún)結(jié)果中的正確性和完整性.

4實(shí)驗(yàn)及其分析

本節(jié)通過(guò)實(shí)驗(yàn)來(lái)驗(yàn)證本文提出的基于壓縮的不完整數(shù)據(jù)近似查詢(xún)方法AQ-MI的性能.實(shí)驗(yàn)主要分為壓縮率實(shí)驗(yàn)、查詢(xún)效率實(shí)驗(yàn)、優(yōu)化對(duì)比實(shí)驗(yàn)和信息丟失比實(shí)驗(yàn)4個(gè)部分.將AQ-MI與壓縮處理技術(shù)中典型的字典壓縮算法LZW[9]和索引壓縮算法PI[11]在壓縮率以及查詢(xún)效率2方面進(jìn)行了對(duì)比分析，又將AQ-MI與數(shù)據(jù)清洗技術(shù)中典型的基于元組刪除法RWD[4]和基于數(shù)據(jù)填充法MIBOI[5]在查詢(xún)結(jié)果信息丟失比例方面進(jìn)行了對(duì)比分析，最終給出實(shí)驗(yàn)結(jié)果.

4.1實(shí)驗(yàn)設(shè)置

本實(shí)驗(yàn)中采用的數(shù)據(jù)為T(mén)PC-H Benchmark[15]生成工具DBGen生成的Lineitem表.DBGen按照主鍵L_OrderKey值遞增順序產(chǎn)生帶有隨機(jī)屬性值缺失字段的Lineitem記錄.

4.2壓縮率實(shí)驗(yàn)

在這個(gè)實(shí)驗(yàn)中，采用壓縮率(compression rate,CR)來(lái)衡量不同方法的壓縮效果.首先對(duì)壓縮率進(jìn)行如下定義：壓縮率即壓縮后數(shù)據(jù)與壓縮前數(shù)據(jù)的比值.

由CR定義可知，CR越小說(shuō)明壓縮效果越好.設(shè)定Lineitem表的屬性數(shù)量固定為16，記錄數(shù)量不斷增加.3種壓縮方法的CR如圖5所示:

Fig. 5　Experiment result of CR.圖5　CR實(shí)驗(yàn)結(jié)果圖

圖5顯示了3種壓縮方法的CR.從圖5中可以看出，CR與數(shù)據(jù)大小的變化沒(méi)有什么明顯的關(guān)系，隨著原始數(shù)據(jù)從100 MB增大至2 GB，各個(gè)壓縮方法的CR基本保持穩(wěn)定.由CR定義可知各個(gè)壓縮方法的CR公式：

CRPI=(索引文件大小+壓縮數(shù)據(jù)大小)原始數(shù)據(jù)大小；

CRLZW=(編碼字典大小+壓縮數(shù)據(jù)大小)原始數(shù)據(jù)大小；

CRAQ-MI=(編碼字典大小+索引壓縮文件大小+壓縮數(shù)據(jù)大小)原始數(shù)據(jù)大小.

顯然地，PI的CR最大，其次是AQ-MI和LZW.這是由于PI將原始數(shù)據(jù)壓縮的同時(shí)建立了索引文件，雖然這樣能夠提升查詢(xún)效率，卻增加了額外的存儲(chǔ)空間.而LZW壓縮效果最佳，這是因?yàn)樗鼔嚎s后的數(shù)據(jù)僅僅多了一個(gè)編碼字典.本文提出的AQ-MI比LZW多出一個(gè)索引壓縮文件，因此CR稍大，但是僅僅犧牲一點(diǎn)存儲(chǔ)空間卻換來(lái)了查詢(xún)效率的提高是值得的.

4.3查詢(xún)效率實(shí)驗(yàn)

在這個(gè)實(shí)驗(yàn)中，對(duì)3種壓縮方法的壓縮數(shù)據(jù)進(jìn)行查詢(xún)的效率測(cè)試，即查詢(xún)時(shí)間測(cè)試.主要考察在數(shù)據(jù)大小固定時(shí)，3種方法分別進(jìn)行壓縮后數(shù)據(jù)的查詢(xún)執(zhí)行情況，以驗(yàn)證各個(gè)算法的實(shí)時(shí)性能.設(shè)定Lineitem表的記錄數(shù)量固定為700萬(wàn)條，大小為1 GB，查詢(xún)條件數(shù)量不斷增加.3種方法的查詢(xún)效率如圖6所示：

Fig. 6　Experiment result of query efficiency.圖6　查詢(xún)效率實(shí)驗(yàn)結(jié)果圖

圖6顯示了3種壓縮方法將1 GB的原始數(shù)據(jù)壓縮后，在不同查詢(xún)條件數(shù)目下的查詢(xún)時(shí)間.從圖6中可以看出，隨著查詢(xún)條件數(shù)量從2個(gè)增加到5個(gè)，各方法壓縮后數(shù)據(jù)的查詢(xún)時(shí)間都在增加.其中，LZW的查詢(xún)時(shí)間最長(zhǎng)，其次是AQ-MI和PI.這是因?yàn)長(zhǎng)ZW在查詢(xún)時(shí)需要先分析查詢(xún)條件，然后對(duì)壓縮數(shù)據(jù)做選擇和投影操作，其查詢(xún)時(shí)間會(huì)隨著操作條件的增加而增加.PI在壓縮時(shí)就建立了對(duì)應(yīng)壓縮地址的索引，分析并得到滿(mǎn)足查詢(xún)條件的索引，就可以快速地返回查詢(xún)結(jié)果.本文提出的AQ-MI比PI多了一步無(wú)解壓查詢(xún)索引壓縮文件，雖然也需要做選擇和投影操作，但不論查詢(xún)條件數(shù)量多少，大多數(shù)情況下僅需要對(duì)屬性Def_Query做一次選擇操作，對(duì)屬性Address做一次投影操作即可，然后得到D*數(shù)據(jù)壓縮地址就可以快速返回查詢(xún)結(jié)果.

4.4優(yōu)化對(duì)比實(shí)驗(yàn)

在這個(gè)實(shí)驗(yàn)中，對(duì)本文所提方法AQ-MI和優(yōu)化后方法AQ-MI′進(jìn)行對(duì)比測(cè)試.主要考察采用壓縮優(yōu)化策略前后的壓縮效果.設(shè)定Lineitem表的屬性數(shù)量固定為16，記錄數(shù)量固定為700萬(wàn)條，大小為1 GB，Def_Query數(shù)量不斷增加.AQ-MI和AO-MI′的CR如圖7所示：

Fig. 7　Experiment result of optimization comparison of CR.圖7　CR優(yōu)化對(duì)比實(shí)驗(yàn)結(jié)果圖

圖7顯示了AQ-MI和AO-MI′的CR.從圖7可以看出，隨著Def_Query數(shù)目從2個(gè)增加到5個(gè)，AQ-MI和AO-MI′的CR都在增大，但是顯然AQ-MI的CR增長(zhǎng)幅度更大，這是因?yàn)锳Q-MI在對(duì)含有*標(biāo)記的屬性的元組進(jìn)行壓縮的時(shí)候，只要有1個(gè)*屬性滿(mǎn)足Def_Query，就會(huì)讓該元組的壓縮次數(shù)增加1倍，雖然屬性值缺失字段是隨機(jī)產(chǎn)生的，CR并不會(huì)呈現(xiàn)指數(shù)增長(zhǎng)，但Def_Query數(shù)量的增多自然會(huì)導(dǎo)致壓縮效率的降低.相對(duì)地，AQ-MI′的CR雖然也在增長(zhǎng)，但明顯遠(yuǎn)遠(yuǎn)低于AQ-MI，這是由于其采用了基于屬性重要性的主客觀(guān)權(quán)重分配策略，權(quán)重高于閾值的屬性?xún)H僅是少數(shù)，CR自然就比AQ-MI低了.查詢(xún)同理，CR低，索引文件的元組數(shù)量就少，從而減少了查詢(xún)時(shí)的投影操作以及字典匹配操作，查詢(xún)效率自然就高，這里不再贅述.在實(shí)際應(yīng)用中，對(duì)海量數(shù)據(jù)的操作需要較高的時(shí)間和空間代價(jià)，一般情況下查詢(xún)類(lèi)型較少，而本文的壓縮優(yōu)化正適用于數(shù)據(jù)量大，確定性查詢(xún)條件多的情況，且Def_Query數(shù)目越多優(yōu)化效果越明顯.

4.5信息丟失比實(shí)驗(yàn)

在這個(gè)實(shí)驗(yàn)中，采用信息丟失比(information loss ratio,ILR)來(lái)對(duì)本文提出的AQ-MI方法和主流數(shù)據(jù)清洗方法RWD，MIBOI在信息保持方面的性能進(jìn)行比較.首先對(duì)信息丟失比進(jìn)行如下定義：所有滿(mǎn)足查詢(xún)條件但丟失的屬性值所有滿(mǎn)足查詢(xún)條件的屬性值.

由ILR定義可知，ILR越小說(shuō)明信息保持性能越好.設(shè)定對(duì)Lineitem表的查詢(xún)條件不變，數(shù)據(jù)記錄數(shù)量不斷增加.3種方法的ILR如圖8所示：

Fig. 8　Experiment result of ILR.圖8　ILR實(shí)驗(yàn)結(jié)果圖

圖8顯示了3種方法的ILR.從圖8中可以看出，隨著原始數(shù)據(jù)從100 MB增大至2 GB，RWD查詢(xún)結(jié)果的ILR最高，其次是MIBOI，而本文提出的AQ-MI沒(méi)有信息丟失.這是因?yàn)镽WD是基于記錄刪除的清洗方法，在查詢(xún)之前將屬性值缺失的記錄刪除，這樣雖然能查詢(xún)得到唯一確定的結(jié)果，但是丟失了很多有價(jià)值的信息，尤其是在原始數(shù)據(jù)中含有很多不完整數(shù)據(jù)的情況下丟失比更大.MIBOI是基于數(shù)據(jù)填補(bǔ)的清洗方法，在查詢(xún)預(yù)處理階段是以不完備數(shù)據(jù)聚類(lèi)的結(jié)果為基礎(chǔ)進(jìn)行缺失數(shù)據(jù)的填補(bǔ)，雖然能夠得到一個(gè)完備的信息表，但一些填補(bǔ)的數(shù)據(jù)不一定符合客觀(guān)事實(shí)，即與缺失的真實(shí)數(shù)據(jù)不一致，這就可能導(dǎo)致查詢(xún)結(jié)果缺少了本該包含的信息，但至少它的ILR比直接刪除記錄的RWD要低很多.而本文提出的AQ-MI方法在預(yù)處理階段只是掃描數(shù)據(jù)庫(kù)并標(biāo)記屬性值缺失字段，在后續(xù)的壓縮存儲(chǔ)過(guò)程中，對(duì)有標(biāo)記字段的元組進(jìn)行多重壓縮，保證了查詢(xún)結(jié)果的完整性和可信性.

5結(jié)束語(yǔ)

傳統(tǒng)的數(shù)據(jù)修復(fù)方法對(duì)于海量數(shù)據(jù)處理代價(jià)過(guò)高，且不能徹底修復(fù)，為了實(shí)現(xiàn)在不完整的海量數(shù)據(jù)上進(jìn)行滿(mǎn)足給定需求的近似查詢(xún)，提出了一種基于壓縮的海量不完整數(shù)據(jù)近似查詢(xún)方法AQ-MI.該方法對(duì)屬性值缺失字段進(jìn)行標(biāo)記，根據(jù)頻繁查詢(xún)條件對(duì)標(biāo)記后的數(shù)據(jù)進(jìn)行壓縮，并建立對(duì)應(yīng)索引；根據(jù)屬性劃分對(duì)索引文件再次壓縮以節(jié)省存儲(chǔ)空間，采用編碼字典對(duì)索引壓縮文件進(jìn)行選擇和投影操作，最終獲得不完整數(shù)據(jù)的近似查詢(xún)結(jié)果.實(shí)驗(yàn)表明:與現(xiàn)有的壓縮查詢(xún)處理方法相比，AQ-MI不僅能在很大程度上減少存儲(chǔ)空間，還能夠提高查詢(xún)效率.此外，它對(duì)不完整信息的處理與現(xiàn)有的數(shù)據(jù)清洗方法相比，更能保證查詢(xún)結(jié)果的完整性.

參考文獻(xiàn)

[1]Li Jianzhong, Liu Xianmin. An important aspect of big data: Data usability[J]. Journal of Computer Research and Development, 2013, 50(6): 1147-1162 (in Chinese)(李建中, 劉顯敏. 大數(shù)據(jù)的一個(gè)重要方面: 數(shù)據(jù)可用性[J]. 計(jì)算機(jī)研究與發(fā)展, 2013, 50(6): 1147-1162)

[2]Aste M, Boninsegna M, Freno A, et al. Techniques for dealing with incomplete data: A tutorial and survey[J]. Pattern Analysis and Applications, 2015, 18(1): 1-29

[3]Dai J. Rough set approach to incomplete numerical data[J]. Information Sciences, 2013, 241(12): 43-57

[4]Kolahi S, Lakshmanan L V S. On approximating optimum repairs for functional dependency violations[C]Proc of the 12th Int Conf on Database Theory. New York: ACM, 2009: 53-62

[5]Wu Sen, Feng Xiaodong, Shan Zhiguang. Missing data imputation approach based on incomplete data clustering[J]. Chinese Journal of Computers, 2012, 35(8): 1726-1738 (in Chinese)(武森, 馮小東, 單志廣. 基于不完備數(shù)據(jù)聚類(lèi)的缺失數(shù)據(jù)填補(bǔ)方法[J]. 計(jì)算機(jī)學(xué)報(bào), 2012, 35(8): 1726-1738)

[6]Chen Zhikui, Lü Ailing, Zhang Qingchen, et al. A new algorithm for imputing missing data based on distinguishing the importance of attributes[J]. Microelectronics and Computer, 2013, 39(7): 2630-2631 (in Chinese)(陳志奎, 呂愛(ài)玲, 張清辰. 基于屬性重要性的不完備數(shù)據(jù)填充算法[J]. 微電子學(xué)與計(jì)算機(jī), 2013, 39(7): 2630-2631)

[7]Chen Yuxin, Cheng Xu, Zhao Peng, et al. Process missing information for massive sparse data storage in cloud environment[J]. Journal of Computer Research and Development, 2012, 49(Suppl): 316-322 (in Chinese)(陳郁馨, 程序, 趙鵬, 等. 云環(huán)境中一種面向海量稀疏數(shù)據(jù)存儲(chǔ)的缺失值處理方法[J]. 計(jì)算機(jī)研究與發(fā)展, 2012, 49(增刊): 316-322)

[8]Xu Xia, Ma Guangsi, Yu Tao. Research and improvement on LZW lossless compression algorithm[J]. Computer Technology and Development, 2009, 19(4): 125-127 (in Chinese)(許霞, 馬光思, 魚(yú)濤. LZW無(wú)損壓縮算法的研究與改進(jìn)[J]. 計(jì)算機(jī)技術(shù)與發(fā)展, 2009, 19(4): 125-127)

[9]Nandi U, Mandal J K. Modified compression techniques based on optimality of LZW code (MOLZW) [J]. Procedia Technology, 2013, 10: 949-956

[10]Liang Huaguo, Jiang Cuiyun, Luo Qiang. Test data compression and decompression using symmetry-variable codes[J]. Journal of Computer Research and Development, 2011, 48(12): 2391-2399 (in Chinses)(梁華國(guó), 蔣翠云, 羅強(qiáng). 應(yīng)用對(duì)稱(chēng)編碼的測(cè)試數(shù)據(jù)壓縮解壓方法[J]. 計(jì)算機(jī)研究與發(fā)展, 2011, 48(12): 2391-2399)

[11]Zhao Kai, Li Jianzhong, Luo Jizhou. Storage and operation of massive data compression based on predication index[J]. Computer Science, 2005, 32(9): 86-90 (in Chinese)(趙鍇,李建中,駱吉洲. 基于謂詞索引的海量數(shù)據(jù)壓縮存儲(chǔ)及數(shù)據(jù)操作算法[J]. 計(jì)算機(jī)科學(xué), 2005, 32(9): 86-90)

[12]Arenas M, Pérez J, Reutter J. Data exchange beyond complete data[J]. Journal of the ACM, 2011, 60(4): 83-94

[13]Nair R. Big data needs approximate computing: Technical perspective[J]. Communications of the ACM, 2014, 58(1): 104-104

[14]Wong H K T, Liu H F, Olken F, et al. Bit transposed files[C]Proc of the 11th Int Conf on VLDB. San Francisco: Morgan Kaufmann, 1985: 448-457

[15]Transaction Processing Performance Council(TPC). TPC BENCHMARKTMH (Decision Support) Standard Specification Revision 2.17.1[EBOL]. (2014-11-13) [2015-05-13]. http:www.tpc.orgtpchdefault.asp

Wang Yan, born in 1978. PhD candidate and associate professor. Student member of China Computer Federation. Her main research interests include massive data query technology, sensing data processing, big data management, etc.

Liu Genghao, born in 1990. Master candidate. Student member of China Computer Federation. His main research interests include massive data query technology, etc.

Wang Junlu, born in 1988. Master and assistant engineer. Student member of China Computer Federation. His main research interests include database theory and techniques, big data processing techniques and massive data processing techniques, etc.

Song Baoyan, born in 1965. PhD and professor. Senior member of China Computer Federation. Her main research interests include database theory and techniques, RFID event stream processing techniques, big data management and graph data management, etc.

中圖法分類(lèi)號(hào)TP391

通信作者：宋寶燕(bysong@lnu.edu.cn)

基金項(xiàng)目：國(guó)家自然科學(xué)基金項(xiàng)目(61472169,61472072)；國(guó)家科技支撐計(jì)劃基金項(xiàng)目(2012BAF13B08)；國(guó)家“九七三”重點(diǎn)基礎(chǔ)研究發(fā)展計(jì)劃前期研究專(zhuān)項(xiàng)基金項(xiàng)目(2014CB360509)；遼寧省科學(xué)事業(yè)公益研究基金項(xiàng)目(2015003003)；遼寧省工業(yè)攻關(guān)及成果產(chǎn)業(yè)化計(jì)劃項(xiàng)目(2012216007)

收稿日期：2015-06-30；修回日期：2015-11-06

This work was supported by the National Natural Science Foundation of China (61472169，61472072), the National Key Technology Research and Development Program of China (2012BAF13B08), the National Basic Research Program of China (973 Program) (2014CB360509), the Science Commonweal Research Foundation of Liaoning Province (2015003003), and the Industrial Research and Production Industrialization Program of Liaoning Province (2012216007).