張 莉，李衛(wèi)平

（1.鄭州成功財經(jīng)學院 信息工程系，河南 鄭州451200；2.武漢理工大學 信息工程學院，湖北 武漢430070；3.鐵道警察學院 公安技術(shù)系，河南 鄭州450053）

0 引 言

傳統(tǒng)的搜索引擎通過網(wǎng)絡爬蟲收集到海量的網(wǎng)頁信息，然后通過預先排序的方式響應用戶的搜索請求，這種方式不能滿足用戶對實時信息的搜索請求［1］，其不能對用戶剛剛發(fā)布的微博信息進行檢索。在大規(guī)模的微博系統(tǒng)中，系統(tǒng)每秒鐘需要處理成千上萬條狀態(tài)更新，因此為用戶提供實時的搜索服務是一項極具挑戰(zhàn)的事情［2］。為了使每條用戶消息都能夠被檢索，需要對每條消息實時地建立索引，并同時提供高效的基于關(guān)鍵字的搜索服務［3］。在索引的建立和維護中，由于消息到達的頻率非常高，因此實時性和高效性是相互矛盾的，必須加以權(quán)衡。

微博實時搜索的另一個挑戰(zhàn)是缺少有效的微博消息排名算法。例如，當某公司剛剛發(fā)布一個新產(chǎn)品后，用戶A想通過微博搜索附近專賣店的排隊購買情況，而搜索返回的大都是該產(chǎn)品的廣告等無用信息?，F(xiàn)有的微博搜索大都基于信息的發(fā)布時間，因此最新的消息總是排在前面。由于缺少適當?shù)呐琶惴ǎ⒉┧阉骱茈y滿足用戶的各種不同類型的實時搜索需求。

為了降低排名算法的開銷，本文提出了一種高效的適應性微博信息索引方法。根據(jù)微博消息的轉(zhuǎn)發(fā)和回復等信息將消息組合成樹形結(jié)構(gòu)，通過對樹形結(jié)構(gòu)進行分析，將消息聚類成若干話題，在內(nèi)存中維護活躍的話題，并據(jù)此更改倒排索引的結(jié)構(gòu)。

1 相關(guān)工作

1.1 部分索引與視圖實體化

在數(shù)據(jù)庫系統(tǒng)中，對數(shù)據(jù)建立索引結(jié)構(gòu)可以加快數(shù)據(jù)處理過程，然而現(xiàn)有的索引方法主要用于基于相似性的KNN 搜索。例如，iDistance索引方法［4］不能高效的應對大量的插入操作，因而不能直接應用于微博消息的索引。部分索引方法［5］只對部分查詢概率高的數(shù)據(jù)進行索引，因而能應對大量的數(shù)據(jù)插入操作。學者［6］采用統(tǒng)計模型監(jiān)測用戶的查詢分布，并根據(jù)查詢的分布情況動態(tài)的調(diào)整索引結(jié)構(gòu)。另一研究者［7］應用分布式哈希表對罕見的數(shù)據(jù)建立部分索引結(jié)構(gòu)，而對常見的數(shù)據(jù)應用泛洪搜索方法。

視圖實體化的基本原理與部分索引技術(shù)相似。文獻［9，10］討論了如何在多維數(shù)據(jù)庫和數(shù)據(jù)倉庫系統(tǒng)中適應性地對視圖進行調(diào)整。文獻 ［11，12］提出的代價模型可以動態(tài)的選取數(shù)據(jù)的視圖并進行實例化。Silberstein A等［13］應用適應性視圖實例化策略來減小流注入系統(tǒng)的開銷。本文提出的一種索引方法的基本思想與上述方法相似，其差別在于本文只對查詢必要的數(shù)據(jù)進行實時索引，而對其它數(shù)據(jù)通過批處理的方式進行處理。

1.2 微博搜索

Google和Twitter都有自己的實時搜索引擎。Google通過Web爬蟲適應性地抓取微博數(shù)據(jù)，而Twitter通過現(xiàn)有的Lucene技術(shù)提供搜索服務。這兩個系統(tǒng)都將用戶的查詢看作是連續(xù)的查詢操作，并實時地對查詢結(jié)果進行更新。然而，搜索引擎的排名函數(shù)僅僅考慮時間維度，因此搜索結(jié)果按照時間進行排序。通過對微博系統(tǒng)中的用戶行為進行分析，Java等［14］和Teevan等［1］分別提出了復雜的排名算法。由于大多數(shù)的排名算法都很復雜，執(zhí)行效率低并且占用大量的資源，只能通過離線的方式進行處理。為了解決這一問題，Sankaranarayanan等［15］過濾掉微博中的噪音數(shù)據(jù)，并且將相似的消息聚類成話題。這種方法通過對相同話題中的消息進行排名，從而大大減小了排名所用的計算開銷。本文根據(jù)微博消息的轉(zhuǎn)發(fā)和回復等信息將消息組合成樹形結(jié)構(gòu)，通過對樹形結(jié)構(gòu)進行分析，將消息聚類成若干話題。為了降低排名算法的開銷，本文在內(nèi)存中維護活躍的話題，并據(jù)此更改倒排索引的結(jié)構(gòu)。

2 系統(tǒng)結(jié)構(gòu)

2.1 數(shù)據(jù)表示與編碼

在微博社會網(wǎng)絡中，用戶通過好友關(guān)系 （如關(guān)注與被關(guān)注）構(gòu)成一個社會圖Gu＝（U，E），其中U 為系統(tǒng)中的用戶集合，E 為用戶之間的好友關(guān)系。

除了社會圖以外，微博中消息之間的轉(zhuǎn)發(fā)與回復關(guān)系構(gòu)成了消息關(guān)系圖。圖1是簡單的微博消息關(guān)系，其中每個節(jié)點表示一條消息，消息之間的有向邊表示消息之間的轉(zhuǎn)發(fā)與回復關(guān)系。用戶A 發(fā)布了一條消息 （根節(jié)點），此后用戶B，C和D 分別轉(zhuǎn)發(fā)或回復了該條消息。微博消息之間的關(guān)系圖是一個樹形結(jié)構(gòu)，本文應用該樹形結(jié)構(gòu)表示一個話題。搜索時，將該話題包含的樹形結(jié)構(gòu)進行組合，作為結(jié)果一起返回給用戶。

圖1 簡單的微博消息關(guān)系

由于維護話題樹的開銷很高，本文不顯示的對其進行維護，而是樹中的每條消息進行編碼。給定消息ti，通過各自的時間戳 （消息進入系統(tǒng)的時間）對節(jié)點ti的子節(jié)點進行排序。如果節(jié)點ti的編碼是x，節(jié)點tj是ti的第k 個子節(jié)點，那么tj的編碼是x－k，例如節(jié)點D 是節(jié)點A 的第3個子節(jié)點，其編碼為0－2（編碼計數(shù)從0開始）。通過該編碼方式可以很容易地將樹的編碼重構(gòu)成樹。

2.2 系統(tǒng)設計

本文采用倒排索引的方式用于數(shù)據(jù)的查詢。當新的消息進入系統(tǒng)時，索引程序決定是否對其建立索引結(jié)構(gòu)。為了快速的建立和維護索引結(jié)構(gòu)，內(nèi)存中保存數(shù)據(jù)的統(tǒng)計信息，數(shù)據(jù)庫中保存著微博數(shù)據(jù) （tweets）及其倒排索引。當指定關(guān)鍵字查詢時，倒排索引返回包含關(guān)鍵字的消息（tweets）列表T。圖2給出了倒排索引的索引結(jié)構(gòu)。索引的每條記錄保存著消息的標示符TID （區(qū)分不同的消息），排名值U－PageRank，詞頻TF，樹的標示符TID，以及消息的時間戳time。TID 是消息組成的話題的根節(jié)點的標示符。包含相同關(guān)鍵字的消息組成一個鏈表，其中最近插入的消息在鏈表的頭部。

圖2 倒排索引結(jié)構(gòu)

為了方便排序過程，系統(tǒng)還包含微博消息的數(shù)據(jù)表。其元數(shù)據(jù)結(jié)構(gòu)包括所屬話題樹的根節(jié)點 （TID），父節(jié)點（RID），時間戳 （time），子節(jié)點個數(shù) （count），話題樹的編碼 （coding），作者的標示符 （UID）和pointer。當消息在索引文件中時，pointer為空，當消息寫回日志時，pointer指向日志的偏移地址。為了支持對消息和用戶標示符的檢索，采用B＋樹對TID 和UID 進行索引。除了消息數(shù)據(jù)表，系統(tǒng)還包含日志文件用于記錄那些沒有被索引的消息。數(shù)據(jù)表中包含的消息是有選擇性的，即重要的消息。噪音數(shù)據(jù)周期性的被寫入日志文件的末端，后臺的批處理索引過程會定期掃描日志文件以便對噪音數(shù)據(jù)進行索引。

為了支持微博消息的實時索引及搜索，在內(nèi)存中保存部分重要的信息，如關(guān)鍵字閾值，候選話題鏈表和流行話題鏈表。關(guān)鍵字閾值記錄了最近流行的查詢的統(tǒng)計信息。候選話題鏈表維護著新近話題的相關(guān)信息。流行話題鏈表維護著用戶廣為討論的話題。基于上述信息，可以快速地將新消息區(qū)分為重要消息和噪音消息，據(jù)此采用不同的索引策略。此外，基于內(nèi)存中的數(shù)據(jù)結(jié)構(gòu)，可以結(jié)合時間戳，流行性和相似性實時地響應用戶的查詢操作。

3 基于內(nèi)容和排名的索引模式

本文基于微博消息的內(nèi)容及消息相對于查詢的排名來對消息進行索引。將新消息與流行查詢集合相匹配，并按照該消息在查詢結(jié)果中的排名決定是實時索引還是進行后臺的批處理索引。為了提高搜索結(jié)果的質(zhì)量，本文的排名算法綜合考慮從消息的PageRank值，話題的流行性以及消息和查詢之間的相似性。

3.1 微博消息分類

由于微博消息內(nèi)容短，消息本身含有的信息量非常少，本文采用基于查詢的分類方法。本文假設用戶只關(guān)心檢索結(jié)果的Top－k項，該假設在文獻 ［8］中得到了驗證。其中62%的用戶訪問了第一個返回頁面中的一項，并且超過90%的用戶在瀏覽了3個頁面后就停止瀏覽行為。

定義1 微博消息分類：給定消息t和用戶查詢集合Q ，在查詢函數(shù)F 下，如果-qi∈Q，并且t是qi的前Top－k項結(jié)果，那么t是重要消息。否則，t是噪音消息。

為了返回查詢集合Q 中查詢的Top－k項結(jié)果，只需要對重要消息進行索引，而噪音消息可通過批處理方法周期性的索引。這種方法可以降低索引頻繁更新帶來的開銷。

對于不同的查詢集合Q，分類結(jié)果是不同的。理想情況下，當包Q 含所有查詢時，該分類對每個查詢都得到準確的結(jié)果。然而這種方法的索引維護代價高，可通過部分索引的方法在準確性和效率上進行折中。研究表明，社會現(xiàn)象事實上服從Zipf定律，即80%的用戶請求可以用20%的常用查詢來表達。因此，可以在查詢集合Q 中維護部分常用的查詢，以此來降低索引維護的開銷。假設第n 個查詢出現(xiàn)的概率為

式中：α和β——Zipf分布的參數(shù)。令s為每秒提交的查詢的個數(shù)，那么第n個查詢的時間間隔的期望是

式 （2）表明，在t（n）秒之后，第n個查詢被提交到系統(tǒng)的概率很高。如果系統(tǒng)進行批處理索引的周期是t′，那么只有當t（n）＜t′時，才將第n個查詢加入到Q 。這種方法的直觀解釋是：不需要對頻繁的查詢進行頻繁的索引更新。

為了估計查詢分布，在磁盤上保存一個查詢?nèi)罩?。當某查詢第一次進入系統(tǒng)時，將其視為非頻繁的查詢，并在下一次批處理索引更新時進行更新。通過對查詢?nèi)罩具M行分析來建立一個查詢柱狀圖，并用Zipf分布模擬其分布情況?；谑?（2），將頻繁查詢加入到Q。

假設微博消息集合為T，用F（qi，tj）表示消息tj∈T給定查詢qi∈Q 下的排名值。

定義2 支配集：給定消息集合T，查詢q，以及消息t∈T，t的與q 相關(guān)的支配集包含比t的排名值更高的那些消息，即

計算消息t的支配集的最直接方法是對Q 中所有的查詢計算支配集。這種方法需要對整個消息集合進行掃描，為了解決上述問題，本文提出了相應的優(yōu)化方法。

3.2 Top－k閾值優(yōu)化

在自然語言中，單詞服從Zipf定律［16］，即每個單詞在文本中出現(xiàn)的概率是固定的。在給定查詢下，重要消息的個數(shù)隨著時間的推移趨于穩(wěn)定值。

定理1 令每個關(guān)鍵字在微博消息集合中出現(xiàn)的概率是固定的，并且微博消息以穩(wěn)定的速率進入系統(tǒng)。如果查詢qi有m 個結(jié)果 （m K），那么qi的Top－k個結(jié)果的方差隨著K 的增大而減小。

證明：系統(tǒng)含有n 條消息，并且有m 條消息包含關(guān)鍵字，K ＜m ≤n。假設消息在數(shù)據(jù)集中是隨機分布的，通過對消息的排名值進行排序得到列表｛t1，t2，…，tn｝，第K 條消息排在位置x 的概率為

那么，Top－k個結(jié)果的數(shù)學期望是

式中：score（i）——第i個消息的排名值。于是該問題轉(zhuǎn)化為順序統(tǒng)計問題?；谖墨I ［4］給出的上界，當m 足夠大時，對于大的K 值可以得到E（K）近似值。

定理1與本文的分類方法相對應。對每一個查詢q∈Q，保持這一個Top－k閾值，所有查詢的Top－k閾值組成了閾值表Tθ。Tθ（q）返回查詢q的Top－k個結(jié)果的閾值。

引理1 對于消息t，如果F（qi，t）＜Tθ（qi），那么t在此刻的支配集含有的元素個數(shù)大于K 。

證明：如果F（qi，t）＜Tθ（qi），那么t的排名值小于當前第K 個結(jié)果的排名值。于是，排名值大于t的消息的個數(shù)大于K 。

定理2 對于消息t，如果對所有的qi∈Q，都滿足F（qi，t）＜Tθ（qi）并且F（qi，t）隨著時間而減小，那么t是噪音消息。

證明：由于F（qi，t）隨著時間為減小，那么消息t不再是查詢qi的查詢結(jié)果。因為t不再是所有查詢的查詢結(jié)果，那么t是噪音消息。

定理2要求排名函數(shù)F（qi，t）隨著時間而減小。為了保持熱點話題及其發(fā)展傾向，本文的排名方法F（qi，t）在一小部分熱點話題中會存在部分的凸起，但是整體趨勢是下降的。

4 實驗設計與結(jié)果分析

本節(jié)通過實驗對提出的索引模式的性能進行了驗證。實驗采用的數(shù)據(jù)集為Twitter數(shù)據(jù)集，該數(shù)據(jù)集的詳細信息見文獻 ［17］。在實驗中，用數(shù)據(jù)集的前10天的數(shù)據(jù)作為啟動數(shù)據(jù)對系統(tǒng)進行初始化 （包括建立Top－k閾值，統(tǒng)計話題的流行性），并用最后10 天的數(shù)據(jù)測試系統(tǒng)的性能。在關(guān)鍵字的提取過程中，提取了前10天的所有關(guān)鍵字，并刪除了無意義的虛詞以及頻率低的關(guān)鍵字，最后得到大約5千個關(guān)鍵字。在查詢過程中，查詢包含的關(guān)鍵字隨機生成，并且查詢關(guān)鍵字的個數(shù)服從Zipf分布。其中查詢的60%包含一個關(guān)鍵字，30%包含兩個關(guān)鍵字，10%包含3 個及以上的關(guān)鍵字。所有的實驗重復10次，并取所有結(jié)果的平均值。在實驗中，將本文提出的tweets索引模式記為TI。

4.1 索引適應性分析

實驗分析了適應性索引模式對系統(tǒng)性能的影響。圖3顯示了實時進行索引的消息數(shù)量的百分比。如果查詢結(jié)果只返回top－10項，那么可以對超過80%的消息進行剪枝，并應用離線批處理進行索引。由于只需要對部分消息實時進行索引，因此可以大大提高索引的性能。圖4對比了TI索引與完全索引的索引時間對比。在TI中，索引的開銷與消息的個數(shù)近似成正比，并且其時間遠遠低于完全索引方法。

為了測試適應性索引是否損失了查詢結(jié)果的準確性，本文令查詢準確性為，其中R 為完全索引返回的結(jié)果集，R′為TI方法返回的結(jié)果集。對比結(jié)果如圖5所示。其中，Constant Threshold方法查詢處理的Top－k閾值不動態(tài)變化，而Adaptive Threshold 方法 的Top－k閾值根據(jù)新消息不斷地更新。從圖5 中可以看出，適應性索引的準確性要高于Top－k閾值不變的索引方法。

圖3 TI索引方法的適應性分析

圖4 索引時間對比

圖5 索引的準確性對比

圖6展示了索引的準確性相對于時間的變化情況。由于Constant Threshold方法從來不對閾值進行更新，所以其準確性逐漸降低。而Adaptive Threshold方法的閾值隨著查詢不斷地進行更新，所以其準確性相對平穩(wěn)。圖7展示了Adaptive Threshold方法的tweets消息索引的百分比隨著時間的變化。從圖中可以看出，適應性閾值索引方法性能比較穩(wěn)定，并且不依賴于K 的選取。

4.2 查詢性能分析

由于適應性閾值索引方法采用查詢結(jié)果更新閾值，其

圖6 準確性隨著日期的變化

圖7 索引的百分比隨著日期的變化

開銷非常小，本文采用該方法作為tweets的索引方法TI，并將其與完全基于時間的查詢TimeBased相對比，結(jié)果如圖8所示。TI的性能分為排名開銷TIRank和搜索時的讀操作開銷TIRead兩部分。圖中x軸表示查詢命中的消息的個數(shù)，y軸表示查詢所用的時間。由于對每一個關(guān)鍵字其倒排索引的規(guī)模與包含的消息個數(shù)成正比，因此TI的搜索時間也隨著增加。在后續(xù)的研究工作中，將采用并行化的方式來提高TI索引模式的性能。

4.3 內(nèi)存開銷

圖8 索引的查詢性能對比

為了支持適應性索引模式，本文在內(nèi)存中維護了相應的數(shù)據(jù)結(jié)構(gòu)。實驗最后分析了適應性索引模式的內(nèi)存開銷，結(jié)果如圖9所示。TreesInOct為數(shù)據(jù)集中2009年9月總共包含的樹的個數(shù)，Active Trees為本文在內(nèi)存中維護的樹的個數(shù)。從圖中可以看出，隨著時間的推移，Active Trees的個數(shù)雖然上升，但是上升的很緩慢，其明顯小于TreesInOct，并且不到TreesInOct的20%。這再一次表明了Zipf定律的適用性，即大多數(shù)查詢請求可以用一小部分查詢來表示。

圖9 索引的內(nèi)存開銷對比

5 結(jié)束語

由于微博消息更新速度快，含有的信息量少，傳統(tǒng)的搜索引擎不能滿足用戶對微博實時消息的搜索。為了響應用戶對實時消息的搜索，本文在部分索引技術(shù)的基礎(chǔ)上提出了一種適應性的微博消息索引模式。根據(jù)微博消息的轉(zhuǎn)發(fā)和回復等信息將消息組合成樹形結(jié)構(gòu)，通過對樹形結(jié)構(gòu)進行分析，將消息聚類成若干話題，在內(nèi)存中維護活躍的話題，并據(jù)此更改倒排索引的結(jié)構(gòu)。Twitter數(shù)據(jù)集實驗結(jié)果表明，本文提出的一種適應性索引模式大大降低了微博數(shù)據(jù)索引時的時間和空間開銷，并且其性能隨著時間的推移比較穩(wěn)定。適應性索引模式增加了索引動態(tài)維護的開銷，其響應時間要高于完全基于時間的消息檢索。本文未來的工作將通過并行化進一步降低查詢響應的時間，從而實現(xiàn)微博消息的實時準確檢索。

［1］Teevan J，Ramage D，Morris MR.TwitterSearch：A comparison of microblog search and Web search ［C］//Proceedings of the 4th ACM International Conference on Web Search and Data Mining，2011：35－44.

［2］LIAN Jie，ZHOU Xin，CAO Wei，et al.Sina microblog data retrieval［J］.Jtsinghua Univ （Sci ＆ Tech），2011，51（10）：1300－1305 （in Chinese）.［廉捷，周欣，曹偉，等.新浪微博數(shù)據(jù)挖掘方案 ［J］.清華大學學報 （自然科學版），2011，51 （10）：1300－1305.］

［3］Efron M.Information search and retrieval in microblogs ［J］.Journal of the American Society for Information Science and Technology，2011，62 （6）：996－1008.

［4］Agarwal A，Xie B，Vovsha I，et al.Sentiment analysis of twitter data［C］//Proceedings of the Workshop on Languages in Social Media.Association for Computational Linguistics，2011：30－38.

［5］Chen C，Li F，Ooi BC，et al.Ti：An efficient indexing mechanism for real－time search on tweets ［C］//Proceedings of ACM SIGMOD International Conference on Management of data，2011：649－660.

［6］Zhao X，Jiang J，He J，et al.Topical keyphrase extraction from twitter［C］//Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics，2011：379－388.

［7］Leskovec J，Backstrom L，Kleinberg J.Meme－tracking and the dynamics of the news cycle［C］//Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining，2009：497－506.

［8］Wu S，Li J，Ooi BC，et al.Just－in－time query retrieval over partially indexed data on structured P2Poverlays ［C］//Proceedings of ACM SIGMOD International Conference on Management of Data，2008：279－290.

［9］Budak C，Abbadi AEL.Information diffusion in social net－works：Observing and influencing societal interests［J］.PVLDB，2010，4 （12）：1－5.

［10］Gaonkar S，Li J，Choudhury R R，et al.Micro－blog：Sharing and querying content through mobile phones and social participation ［C］//Proceedings of the 6th International Conference on Mobile Systems，Applications and Services.ACM，2008：174－186.

［11］Shan D，Zhao W X，He J，et al.Efficient phrase querying with flat position index ［C］//Proceedings of the 20th ACM International Conference on Information and Knowledge Management.ACM，2011：2001－2004.

［12］Stirbu V，You Y.Experiences designing hypermedia－driven and self－adaptive Web－based AR authoring tools ［C］//Proceedings of the 3rd International Workshop on RESTful Design.ACM，2012：49－52.

［13］Silberstein A，Terrace J，Cooper B F，et al.Feeding frenzy：Selectively materializing users’event feeds［C］//Proceedings of ACM SIGMOD International Conference on Management of Data，2010：831－842.

［14］Java A，Song X，F(xiàn)inin T，et al.Why we twitter：Understanding microblogging usage and communities ［C］//Proceedings of the 9th Web KDD and 1st SNA－KDD Workshop on Web Mining and Social Network Analysis，2007：56－65.

［15］Sankaranarayanan J，Samet H，Teitler B E，et al.Twitter－Stand：News in tweets［C］//Proceedings of the 17th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems，2009：42－51.

［16］Chakrabarti S，Ramakrishnan G，Ramamritham K，et al.Data－based research at IIT Bombay ［J］.ACM SIGMOD Record，2013，42 （1）：38－43.

［17］Seo J，Croft WB，Smith DA.Online community search using thread structure［C］//Proceedings of the 18th ACM Conference on Information and Knowledge Management，2009：1907－1910.