前言：中文期刊網精心挑選了海量數據范文供你參考和學習，希望我們的參考范文能激發你的文章創作靈感，歡迎閱讀。
海量數據范文1
當前，空間信息技術發展迅猛，以空間數據為主的空間信息挖掘和應用成為現代人類生產生活的一個重要特征。特別是遙感影像數據，由于其具有獲取方便、周期短、信息量大等特點而成為空間數據的重要組成部分。然而，由于遙感數據的數據量十分龐大，特別是對于具有不同來源、不同分辨率與不同時相的數據，其存儲與管理均十分困難，且由于其本身具有的稀缺性與機密性，在一定程度上限制了遙感影像數據的充分利用，因此，迫切需要對其進行有效的組織、存儲、管理和共享的研究。
研究表明，為實現影像數據的網絡服務，可以利用遙感影像元數據，采用流行的數據庫技術對遙感影像數據進行組織與管理，并完成基于XML的影像元數據的，實現用戶通過網絡對遙感影像數據的查詢、檢索與訪問，為影像數據的共享奠定了基礎，同時利用本體技術的優勢，建立起遙感影像信息本體。
影像數據的存儲管理
1.元數據的存儲管理
元數據為空間數據的存儲管理與共享提供了有效的手段，通過元數據信息，用戶可以在沒有真實數據的情況下，獲取有關數據的信息，從而為數據的共享與利用提供了可能。目前關于矢量空間數據的元數據標準已經制定，并形成了我國的地理信息國家標準，而關于遙感影像方面的元數據標準，尚處在研究之中，未形成一個普遍接受的標準。為此，國家遙感工程中心在ISO 19115.3 遙感影像元數據標準以及我國即將推出的地理信息元數據標準的基礎上，結合項目的實際情況，制訂了遙感影像元數據草案。該草案包括7個元數據集、6個公共數據類型和15個代碼表，從標識信息、數據質量信息、參照系信息、內容信息、覆蓋范圍、分發信息和遙感信息等方面對遙感影像數據進行了詳細的表述。
2.影像數據的存儲管理
由于遙感影像的數據量十分龐大，難以直接進行存儲，不利于后續的處理、提取、瀏覽與檢索，因此需要對其進行預處理，主要包括降采樣、影像壓縮與影像分割等內容。
影像分割是將遙感影像按照行列值分割為相同大小的數據塊（tile），并以tile作為影像存儲的基本單元。每個tile均以一條記錄的方式進行存儲，不同記錄通過編號進行排列。對于不能夠平分的，出現多余的行或列時，應將其單獨存放。當用戶對影像進行調用時，通過映射關系，只調用與用戶有關的tile集合即可，從而優化了數據的存儲、傳輸、瀏覽模式。
為減小影像的傳輸數據量和優化顯示性能，需建立影像金字塔（圖1），通過影像降采樣方法，建立一系列不同分辨率的影像圖層，每個圖層分割存儲，并建立相應的空間索引機制。常用的影像重采樣方法有雙線性差值、立方卷積等。
由于影像的數據量比較龐大，為減小影像的存儲空間，還需要對影像進行壓縮處理后存儲。當用戶調用數據時，首先對數據進行解壓縮處理，然后再返回給用戶。常用的圖像壓縮方法有JPEG、LZ77等。
3.影像數據庫結構設計
遙感影像數據庫主要可以分為影像元數據庫和影像數據庫兩部分（圖2）。影像元數據庫用于對遙感影像元數據標準中的數據集進行存儲與管理，影像數據庫用于對影像數據進行存儲和管理。元數據同影像數據通過ID字段進行一對一的關聯，保證了元數據與影像數據的一一對應，從而實現通過元數據可以惟一地查找相應的影像數據，而通過影像數據，又可以惟一地查看該影像數據的相關信息，實現了遙感元數據與影像數據的一體化管理。
影像數據網絡共享與服務
1.基于元數據的影像數據網絡共享
構建遙感影像元數據的主要目的是為了能夠實現影像數據的網絡與共享。因此元數據的網絡是影像數據的前提與基礎。
目前元數據的網絡大多采用XML技術。XML是一種元語言，是可以用于描述其他語言的語言。用戶可以根據需要，利用XML Schema（或者DTD）自行定義標記和屬性，從而可以在XML文件中描述并封裝數據。XML是數據驅動的，這使得數據內容與顯示相分離。XML可以在類似于Netscape Navigator或Microsoft Internet Explorer的瀏覽器中顯示，并通過因特網在應用之間或業務之間交換，存儲到數據庫中或從數據庫中取出。因此，XML是元數據最好的描述方式，能很好地滿足元數據在網上傳輸、交換的需要。
用戶通過網絡的元數據信息，可以初步了解遙感影像數據的相關信息，然后通過元數據的導航，實現對影像數據的查詢、瀏覽與檢索（圖3）。
2.基于本體技術的影像數據網絡服務
本體（ontology）是從哲學的一個分支――形而上學中的本體論（Ontology）發展來的一個名詞。本體論研究客觀事物存在的本質，與認識論（Epistemology）相對。即本體論研究客觀存在，認識論研究主觀認知。而本體的含義是形成現象的根本實體，因而，本體是概念化的明確說明。最早把本體引入計算機領域的是人工智能領域。
地理信息本體與地理信息分類編碼、地理信息標準術語表之間有著相似之處，本體論與分類學、術語學也存在一定的交叉。
然而，地理信息本體并不是地理信息標準術語表。地理信息本體提供了一組具有良好結構性的詞匯，而且出現在本體中的詞匯經過了嚴格選取，確保所選的詞匯是本領域中最基本概念的抽象與界定。概念與概念之間的關系采用相應技術(如謂詞、邏輯等)進行了完整的反映，而正是這些關系的反映使得基于本體的系統實現后能夠完成語義層面的一些功能。地理信息標準術語表僅僅是地理信息領域中各種詞匯的集合，相對本體而言還比較松散。
本體也不單純是一個詞匯的分類體系，即不是地理信息中的分類和編碼表。本體和地理信息的分類非常相似，尤其是把本體的理論應用于地理信息分類編碼時，這種相似性更為明顯?？偟恼f來，地理信息本體比分類編碼表中所反映的詞與詞之間的關系要豐富。
海量數據范文2
圍繞數據分析工作，市面上出現了眾多相關技術，幫助企業管理和分析多種多樣的龐大數據集。在這個高級分析技術的領域，由于IT服務產品的價格持續下降，用戶可以用更少的IT預算來獲取完善的服務、進行更多的信息分析，解決更復雜的問題。
隨著分析技術的飛速發展和商業智能手段的日益高明，CIO現在完全可以做到大規模、低成本地分析業務數據。這也意味著，企業可以充分利用一切可利用的機會，獲取更高的商業價值。
勇于接受海量數據
大數據是指龐大的數據集，尤其是那些未經組織、管理以適合傳統數據倉庫的數據集。雖然不是每一家公司都需要掌握處理龐大非結構化數據集的手段，但Verisk Analytics公司的CIO Perry Rotella認為，所有CIO都應該關注大數據分析工具。Verisk公司幫助金融公司評估風險，也幫助保險公司從理賠數據中識破欺詐，它在2010年的營收超過了10億美元。Verisk公司的業務是“從你事先未知的數據中找到一定的模式和關聯?！盧otella表示，企業的IT負責人應持數據越多越好的態度，并勇于接受海量數據。
HMS公司專門幫助客戶實施醫療保險和醫療補助計劃，同時也為企業控制醫療保健成本，其業務覆蓋美國40多個州的衛生和福利計劃以及130多個醫療補助管理型醫療保健計劃。在2010年，通過避免錯誤支付，HMS幫助客戶追回了18億美元的成本，省下了數十億美元的開銷。該公司的CIO Cynthia Nustad認為，大數據呈“爆炸式發展”的趨勢，“我們在努力獲取、跟蹤、分析大量資料，包括結構化數據和非結構化數據，盡管有時你可能都不知道自己在數據中到底要尋找什么。”
Hadoop是被談論最多的大數據技術之一，作為一個開源的分布式數據處理平臺，Hadoop最初被用來處理海量網頁搜索之類的任務。最近它與另外幾種所謂的“NoSQL”技術（包括CouchDB和mONGOdb）大行其道，正以新穎的方式管理大數據。
Hadoop能夠處理PB級數據，具體步驟是把海量數據的子集分配給上千臺服務器，然后由主調度器核對和整理每一臺服務器返回的處理結果。Hadoop既可以用來準備好數據以便分析，本身也可以作為一款分析工具來使用。如果企業沒有成千上萬臺備用服務器，可以向亞馬遜等云服務提供商購買服務，根據具體需要訪問Hadoop。
Nustad認為Hadoop有助于企業通過分析數據來識破欺詐和浪費現象，或許還可以用于分析多種格式的病人門診記錄。她表示，HMS確實在探究NoSQL技術的用途，但并非用于其龐大的醫療保險和醫療補助理賠數據庫，因為這些數據庫含有結構化數據，可以用傳統的數據倉庫技術來處理，而且為了大數據而棄用傳統的關系數據庫管理方法也不明智。
作為一家比較購物網站，Shopzilla每天積累的數據多達數TB。其CIO Mulkey說：“我們用Hadoop來處理過去用數據倉庫來處理的任務，更重要的是，它能讓我們做一些以前無法實現的、真正能滿足需求的分析工作?！币郧?，Shopzilla要為數據取樣和分類――處理這么多數據，工作量非常大?，F在借助Hadoop，Shopzilla就能分析原始數據，跳過中間步驟。
像Rotella和Mulkey這種有Hadoop實踐經驗的CIO，他們所在的公司甚至會將數據分析服務當做一項業務來出售。
提速
從IT架構改革開始
“分析速度提升將是一個更大的趨勢，而大數據技術只是這個趨勢當中的一部分?！笨纤髮W的CIO Vince Kellen認為，“我們需要用更高級的技術來分析海量數據，因為我們希望迅速地獲得分析結果。所以數據多少不重要，重要的是分析數據的效率?！?/p>
雖然幾十年來，數據庫一直通過緩存那些頻繁訪問的數據來提高性能，由于從磁盤獲取數據在一定程度上是個機械過程，所以速度要比在內存中處理慢很多?，F在看來，把龐雜數據全部裝入到一臺服務器或者多臺服務器的內存中要更切實可行，磁盤只用來作備份。
Rotella表示：“現在我可在幾秒鐘內執行分析任務，而五年前我們需要花整整一個晚上?！彼麄儗嫶髷祿M行預測性分析，通常需要經歷啟動查詢、尋找模式、進行調整等環節，然后再啟動下一個查詢，查詢的執行時間對于分析速度影響很大?！霸瓉?，我們運行模型比建立模型費時間，而現在建立模型比運行模型更費時間?！?/p>
列式數據庫服務器把數據庫傳統的組織方式顛倒過來。查詢只訪問相關的列，因而為評估幾個關鍵列的應用程序提升了性能。為了提高分析性能，硬件同樣很重要。保險和金融服務巨頭John Hancock的CIO Allan Hackney已經開始嘗試GPU加速的系統。他說：“可視化方面的運算與統計分析方面的運算非常相似，而GPU執行的運算速度比傳統的PC和服務器處理器快幾百倍。”
開源技術壓低成本
從某種程度上說，計算能力的增加得益于內存和存儲設備價格的不斷下跌，此外有了付費產品之外的選擇以及開源軟件也迫使廠商降低價格。
Ternent在加入Island One之前是Pentaho開源商業智能公司的技術副總裁，他積極倡導開源技術，“在我看來，開源為公平競爭創造了條件?！?/p>
Ternent表示，開源工具一度只適用于基本的報告，而現在，它們提供了最先進的預測分析功能?！艾F在幾乎所有領域都有開源廠商，這意味著誰有膽量用，誰就可以隨意使用開源工具?！?/p>
HMS的Nustad發現，不斷變化的經濟因素也在改變著IT架構方面的一些基本選擇。比如說，構建數據倉庫的一個傳統原因是在擁有計算功能的服務器上把數據整合起來。以前計算功能比較稀缺時，CIO會把分析任務從操作系統卸載下來，以免拖累日常任務的性能，現在就沒必要這么做了。由于省略了移動數據、格式化以及把數據裝入數據倉庫的步驟，CIO直接在操作應用上進行分析能更快地獲得結果。
不過Hackney表示，雖然現在的趨勢正朝著有利于降低管理成本的方向發展，但節省的成本經常被增加的存儲容量需求抵消?！斑@就像在原地跑步。雖然2011年John Hancock的存儲成本下降了2%到3%，但存儲使用量卻增長了20%?！?/p>
為員工設計終端界面
對Nustad而言，移動商務是必須的。因為即使出門在外也要查看各種報告，了解公司是否履行了服務級別協議。她還希望讓公司的客戶可以通過移動設備訪問自己數據，幫助他們監控和管理醫療保健開支。“這是一項客戶非常喜歡的功能。五年前，客戶不會要求提供這項功能，但現在他們對此非常關注?！?/p>
對于CIO來說，應對這個趨勢的關鍵不是提供復雜的分析功能，而在于為智能手機、平板電腦和觸摸屏設計用戶界面。Kellen覺得這問題很容易解決。
但Rotella并不這么認為?！耙苿佑嬎阌绊懼總€人。使用iPad和其他移動設備辦公的人越來越多，這個趨勢會讓員工使用企業計算資源的方式加速改變?！盧otella說，例如，Verisk開發了一種產品，可以讓理賠員在現場訪問分析結果，如此一來他們就能估算重置成本。這種方式可以充分利用分析結果，滿足那些有需要的人。
技術在迅速變化，這是讓CIO最感頭疼的事情。Rotella認為，“兩年前，我們沒有iPad；現在，大家出去都帶著iPad。由于移動設備操作系統有很多種，我們要努力了解如何才能最有效地利用自己的開發資源，避免進行重復的開發工作?！?/p>
Island One的Ternent表示，由于手機和平板電腦中瀏覽器的功能越來越強大，為每個移動平臺開發原生應用程序的呼聲也隨之減弱，“如果我只需針對移動設備為基于Web的應用程序更換皮膚，就不一定非要開發定制的應用程序了”。
分析混合型的
社交媒體
隨著Facebook、推特等社交媒體遍地開花，越來越多的公司想要分析這些網站的數據?，F在，市場上已經出現了新的分析應用軟件，包含語言處理、情感分析和網絡分析等統計方法，它們已不再屬于典型的智能商務“工具包”。
許多社交媒體的分析工具很新穎，常以服務的形式出售。一個突出例子是Radian6，該軟件最近被收入囊中。Radian6提供了一個儀表板，根據推特消息、Facebook公共帖子以及博客和討論板會話上的帖子和留言，可以列出了提到品牌的各種評價。營銷部門和客戶服務部門買來這類工具后，基本上不需要麻煩IT部門。
不過，肯塔基州大學的Kellen表示，對于這類工具，他還在觀望。他說：“我的任務是，確定這些技術中哪一種適合自己，然后再對相應的人員進行培訓?！?/p>
與企業一樣，肯塔基州大學也對監控其品牌評價很有興趣。Kellen表示，他也有興趣開發特定的應用程序，解決學校關注的具體問題，如學生流失等。例如，監控學生在社交媒體上的帖子可以幫助教職員工及早了解學生是否在學習上遇到了麻煩。戴爾公司的支持部門也會經常關注推特，以便及早發現是否有消費者發消息稱自己的戴爾筆記本電腦壞掉的情況。Kellen表示，IT開發人員應想方設法，把社交媒體分析工具生成的報警機制融入到企業系統中，以便迅速應對那些事件。
海量數據范文3
關鍵詞：網格；LHC；數據網格；海量數據
中圖分類號：TP393文獻標識碼：A文章編號：1009-3044(2008)35-2108-02
Mass Data Processing Applications of Grid Technology
WEN Quan-sheng, LUO Tai-peng
(Grid Research Center,Polytechnic University School of the People's Liberation Army Corps of Engineers,Nanjing 210007,China)
Abstract: Data Grid is the third revolution of the information technology after Internet and Web,and based on current data management technologies,Data Grid aims to integrate all kinds of resources in the network,such as storage resources,data resources,computing resources,etc.,and establish a unified architecture for data access,store,transfer and management,which offers a new way for mass data management.
Key word: grid;LHC;data grid;mass data
1 引言
目前，在越來越多的領域，例如高能物理、醫學、生物學、天文學等等，數據量正在呈現爆炸性增長。一般認為，當數據量超過普通桌面硬盤的存儲容量時，即可稱之為海量數據。因此這些領域的數據都可以稱作為海量數據。目前，許多領域所產生的數據總和已經達到 TB(terabyte)級，而 PB(petabyte)級的已經出現；不難想象，未來還有可能繼續增加。海量數據具有分布性、異構性等許多新的特征，對存儲資源、計算資源、網絡資源等都提出了極高的性能需求，為傳統的數據管理技術帶來了巨大的挑戰。自20世紀50年代開始，傳統的數據存儲管理方式經歷了人工管理、文件管理、數據庫管理幾個階段，數據存儲從簡單的磁帶、紙帶、卡片發展到現今的大容量服務器，數據管理從無專門的管理軟件發展至數據庫管理系統，數據的共享性不斷增強。但是面對信息爆炸時代的海量數據，現行的數據存儲管理方式仍然體現出了它的不足之處[1]：
1) 海量數據大多分布在不同的地理位置、不同的存儲設備以及不同的數據管理平臺，數據來自多個數據源，形式豐富多樣。而目前尚未有一種數據管理系統可以很好地同時處理數據的分布性和異構性。
2) 計算資源、存儲資源之間存在著相互交流與協作，如何將這些資源有效地整合在一起進行分配和調度，充分利用資源，真正達到共享目的，還存在很大的問題。
3) 如何能提供給用戶一個高效、快速而又方便地數據共享應用平臺也是一個亟待解決的問題。
2 海量數據的產生及特點
2.1 海量數據的產生
1) 生物和醫學：就我國而言 ，生命科學界對網格技術產生了強烈需求：首先是必須開發和應用全新的生物信息處理方法；另外，必須建立高效的超大規模數據信息處理系統[2]。
2) 天文學：虛擬天文臺是新世紀天文學研究的一個重要發展方向。它利用最先進的信息技術和網絡技術將各種天文研究資源以統一的服務模式透明的匯集在統一的系統中。因此，導致世界范圍內天文觀測的數據量以指數級別迅速增長。
3) 高能物理學： 北京譜儀BESIII (Beijing Electron Spectrometer III)是北京正負電子對撞機BEPC (Beijing Electron-Positron Collider)上的大型粒子物理實驗。它每年將產生640TB的數據。除了要求有高性能的海量數據存儲系統外，分析處理BESIII數據需要兩千個CPU[3]。
4) 在其他領域：例如信息檢索、計算幾何、全球氣候建模、大腦研究等等，所產生和需要分析處理的數據量也正在迅速膨脹。
2.2 海量數據的特點
通過對各個領域海量數據的生產、處理、加工、檢索等過程的綜合分析，我們發現海量數據有以下幾個共同的特點：
1) 資源的分布性：主要表現在數據資源的分布性和用戶的分布性。
2) 資源的異構性：主要是數據資源、存儲設備、管理系統、訪問協議的異構性。
3) 數據密集型應用不斷增多：例如前面提到的高能物理方面的研究，另外還包括氣候模擬研究(climatesimulation)，生物信息學方面的研究(bioinformatics)等等。
從以上看出，諸多因素共同導致了海量數據對存儲能力、計算能力、處理能力的許多新的高性能的需求。
3 網格技術及應用
3.1 數據網格（Data Grid）
網格就是一個集成的計算與資源環境，或者說是一個計算資源池。數據網格（Data Grid）是網格技術在數據管理方面的延伸，側重于數據的存儲、管理。它可以管理不同地域，不同來源，不同類型的存儲及數據資源，隱藏存儲介質、數據存儲方式、存儲位置等具體的物理細節，提供給網格用戶一個物理上分散、邏輯上集中的應用技術，使他們可以方便、快速、高效地訪問數據[4]。
它可以簡單地描述為：用戶向數據網格提交數據請求，網格接收請求后，查找符合要求的數據，并將找到的結果返回給用戶。整個過程由網格自動完成，對用戶完全透明，他不必關心數據的物理存儲位置，數據的存儲管理方式，因此簡化和方便和了用戶的使用。
3.2 歐洲數據網格（EuroDataGrid）
全球最大的粒子對撞機――歐洲大型強子對撞機（LHC），其加速器將產生的數據將是空前的：每秒產生100MB原始數據，每年將產生需記錄的事件約為1億個，每年產生的數據量就為15PB 。存儲這15PB數據量每年需要使用兩千萬張CD，分析則需要使用100萬臺當今最快的計算機處理器。
科學家們確信解決問題的唯一思想是將存儲和網絡資源全球分布，進行協作式處理和分析。在這個背景下，歐洲數據網格（EuroDataGrid）應運而生了，它成為實現這個“大科學”目標的基礎平臺。EuroDataGrid 要解決以下幾個方面的問題[5]：
1) EuroDataGrid 需要管理成千上萬的處理器和磁盤、千萬億字節（PB）的數據以及每秒萬億比特的網絡帶寬，保證系統的高可擴展性、低成本和易管理性；
2) 保證數據在不同的研究機構、不同的管理者以及不同的管理政策之間安全地分發、復制、緩存，并保持同步性和完整性；
3) 協調不同國籍、不同研究機構的科學工作者的工作，使他們能夠及時分析數據并匯總結果。
為了滿足以上的需求，EuroDataGrid 系統包含了以下幾個主要功能：負載調度和管理海量數據管理、網格監控、網格構造層的資源管理以及海量存貯管理等。
3.3 大型強子對撞機計算網格（LHC Computing Grid）
LCG（LHC Computing Grid）的目的是將若干參與該計劃的研究機構的計算資源整合為一個世界范圍的計算網格?，F在已發展為LCG-2。它主要是建立在EDG的基礎上，也就是在EDG的基礎上再封裝了一層，從而使得用戶的網格部署更加方便。LCG-2的基本構成部件有用戶界面、資源（RB）、伯克利數據庫信息索引（BDII）、計算資源（CE）、存儲資源（SE）等等[6]。
其主要功能體現在：
1) 海量數據管理：LCG-2的設計是基于歐洲數據網格（EDG），因此，它更加擅長于對海量數據進行管理。LCG-2的數據管理服務由EDG中的副本管理者（RM）和副本管理系統（RMS）提供。RM給用戶提供一個訪問RMS的單一接口。RMS提供的服務包括副本位置服務（RLS）和元數據目錄副本（RMC）。RLS：維護復制文件地位置信息，它由多個本地副本目錄（LRC）組成。RMC：存儲GUID和LFN直接的映射關系，維護其它的元數據信息。
2) 作業管理：LCG-2的作業管理是由負載管理系統（WMS）集中完成的。WMS負責接受提交的作業，并根據作業的要求和可用的資源將作業分配給合適的計算資源。因此，WMS必須先從BDII和RLS中查詢信息。其所提供的所有服務運行在資源（RB）機器上。
3) 信息服務：LCG-2中的信息服務基于OpenLDAP，采用Globus中的MDS來實現，提供了資源信息和資源狀態信息，信息按照層次結構進行。對于信息的描述，LCG-2采用了GLUE框架。
4) 層次信息服務平臺：LCG-2采用層次式信息服務的平臺。這種平臺避免了P2P方式的頻繁信息更新的缺陷，也避免了分布式管理流程過于冗長的特點，使得LCG-2的信息服務更加快捷。
LCG-2中使用了虛擬組織的概念，力圖以一種靈活、安全的方式實現共享資源。數據管理層次清晰，安全機制中對證書的處理尤為出色。它的不足之處在于安裝非常繁瑣，步驟復雜，缺乏詳細的幫助文檔[3.7]。
4 小結
隨著許多科學領域中數據量的急劇增加，海量數據集已經成為一種重要的數據資源。由于現存的數據管理方式已經不能滿足這種新的需求，在這種情況下，便產生了數據網格技術。它將為現今的海量數據管理帶來新的解決思路與方法。
作為是近年來國際上新興的一種重要信息技術，數據網格被稱為21 世紀的IT技術基礎設施，最終將改變人們對分布式資源的使用方式。相信隨著網格研究的發展，在網格應用需求的推動下，網格技術越來越成熟，功能也會越來越強大。
參考文獻：
[1] 甕正科,王新英.Oracle 8.x for Windows NT 實用教程[M].清華大學出版社,2000.
[2] 黃元南.生物網格的應用探索[J].中山大學信息科學與技術學院軟件世界,2005(4).
[3] 孫功星,陳剛.海量數據處理系統的設計和實現[J].高性能計算發展與應用,2008.
[4] 桂小林,網格技術導論[M].北京:郵電大學出版社,2005.
[5] 趙念強,鞠時光.網格計算及網格體系結構研究綜述[J].計算機工程與設計,2006(7).
海量數據范文4
關鍵詞：數據挖掘；PSO算法；關聯規則
中圖分類號：TP301.6 文獻標識碼：A
An availability measure of data mining on mass data
Chen Jian-guo
（College of Computer Science South-central University for Nationalities Wuhan 430074,China)
【Abstract】Through researching the measure of data mining on mass data in large database， this paper proposed an availability measure of data mining on mass data，this measure have achieved how to adopt the particle swarm optimization algorithm to partition the mass data optimization，and adopt an improved Apriori algorithm which resolve the shortcomings of Apriori algorithm, including generating a large number of candidate itemsets and scanning the database many times，so the new algorithm improves the speed and efficiency of data mining on mass data.
【Key words】data mining; Particle Swarm Optimization algorithm; association rule;
當今世界數據信息急劇膨脹，大型數據庫和對大型數據庫中海量數據進行挖掘越來越成為數據庫領域研究人員面對的更現實的問題?；诤Ａ康臄祿诰蛘谂d起，現在面對海量的數據，一般的挖掘軟件或者算法往往采用數據抽樣的方式進行處理，這樣誤差不會很高，可以大大提高數據挖掘的處理的效率和處理的成功率，但在采樣時要注意數據的完整性和防止過大的偏差[1]。這種方法對數據采樣要求比較高，而且可能出現在采樣率不很高的情況下丟失一些很重要的潛在信息。這樣就產生了一種對海量數據進行全盤分析的方法。將海量數據進行劃分，劃分為多個小的子數據庫，對每個子數據庫進行數據挖掘，再合并各子數據庫的挖掘信息[2]。如何對海量數據進行劃分，且要使這些數據得到最優劃分，即每個數據劃分到其最理想的子數據庫里面，這樣就聯系到了另一個重要的研究領域――多目標優化，在多目標優化領域中粒子群優化算法Particle Swarm Optimization(PSO)是其中一個解決多目標問題的非常優秀的算法[3]。
關聯規則是數據挖掘的重要研究方向之一，目前基于關聯規則的數據挖掘算法在處理小型數據庫時還可以表現較好的性能，然而在處理海量數據時隨著數據量的增加效率直線下降。Apriori算法是利用關聯規則進行數據挖掘中的一個最經典的算法，對Apriori算法進行研究分析，發現該算法具有產生大量候選項集和多次掃描數據庫的缺點，且該算法在對海量數據進行挖掘具有非常低的效率，甚至不切實際，但對其進行改進后在對小數據庫進行數據挖掘時可以表現很好的性能。本文擬采用粒子群優化算法對大型數據庫進行優化劃分，形成多個子數據庫，再在子數據庫基礎上采用改進后的Apriori算法進行局部挖掘，最后合并各個局部頻繁項集并生成關聯規則。
1. 算法介紹
1.1. 粒子群優化算法
粒子群優化算法是一種基于群智能的演化計算技術，該算法于1995年由Eberhart博士和kennedy博士提出[4][5]，是當前比較流行的仿生類算法。
PSO算法的基本思想：初始化一群隨機解作為隨機粒子，然后通過迭代找到最優解。在每一次迭代中，粒子通過跟蹤兩個“極值”來更新自己，第一個是粒子本身所找到的最優解，稱為個體極值pBest，另一個極值是整個種群目前找到的最優解，稱為全局極值gBest。在已知pBest和gBest的情況下，粒子根據以下公式來更新自己的速度和位置。
v[i]是粒子i的速度，w是慣性權重，present[i]是當前粒子i的位置，rand()是介于（0，1）之間的隨機數，c1，c2是學習因子。
粒子群優化算法的優勢在于概念簡單，收斂速度較快，所需調整的參數較少。它可直接采用實數編碼，算法結構簡單，容易實現同時又有深刻的智能背景，既適合科學研究，又特別適合工程應用。因此，粒子群優化算法一經提出便立刻引起了信息和進化計算科學等領域學者們的廣泛關注和重視，并在短短的幾年時間里出現大量的研究成果，形成了一個新的理論研究熱點，已被用于多種工程領域。該算法在函數尋優、聚類、人侵檢測和人工智能等領域具有很好的應用前景．
1.2. 改進型的Apriori算法
關聯規則挖掘是發現大型事務或關系數據集中項之間的關聯或相關。關聯規則挖掘由于它應用的領域廣泛從而得到了數據庫從業人員和研究人員的特別關注。最重要的關聯規則挖掘算法――Apriori算法由R . Agrawal和R . Srikant于1994年提出[6]，它是一個基于頻繁項集挖掘的經典算法。Apriori算法的核心方法是基于頻繁項集理論的逐層搜索的迭代方法，但其具有產生大量候選項集和掃描數據庫的次數太多的缺點。本文采用基于矩陣按位存儲的Apriori算法[7]，該算法只掃描一次數據庫，且操作的效率非常高。
設I={I1,I2,…,In}是1項的集合，任務相關的數據D是數據庫事務的集合，其中每個事務T是項的集合，使得T⊆I。每個事務有一個標識符，稱作TID。
定義1：每個項Ij的向量定義為：
1. 頻繁項集的生成
具體步驟如下：
(1) 根據定義1掃描數據庫生成矩陣D。
(2) 根據矩陣D生成1項候選集矩陣，掃描矩陣對所有1項候選集計數，生成頻繁1項集并用矩陣存儲，保存頻繁1項集的計數。
(3) 利用頻繁1項集矩陣生成候選2項集矩陣，對候選2項集計數，生成的頻繁2項集也用矩陣存儲，并保存頻繁2項集的計數。
(4) 頻繁k-1項集生成候選k項集時按照候選K項集生成規則生成，并用矩陣存儲候選k項集，按定義3對候選k項集進行計數，判斷其是否頻繁，生成頻繁k項集，用矩陣存儲頻繁k項集，并保存各頻繁k項集的計數。
(5) 如果頻繁k項集為空，則算法結束，否則，重復執行步驟4，。
2. 關聯規則的生成
對于每個頻繁項集L，產生L的所有非空子集，對于L的每個非空子集S，如果S的支持數與L的支持數之比大于最小置信度，則輸出規則“S=>L S”。
2. PSO算法實現的數據庫劃分
基本關聯規則挖掘算法雖然都不適合大型數據庫中海量數據的挖掘，但是在數據庫較小的情況下可以具有很好的效率．因此，本文考慮利用粒子群算法對大型數據庫進行劃分，再在子數據庫的基礎上應用改進的Apriori算法進行關聯規則挖掘，提高挖掘效率．在利用粒子群算法進行數據庫劃分的時，本文引人了K―均值聚類的思想．以下是對數據庫進行劃分的步驟：
對粒子的位置采用一維16位二進制編碼，“1”代表了該位記錄屬性為真，“0”代表了該位記錄屬性為假．
1)隨機初始化K個聚類中心Z0，將事務按最小距離原則分配給k個聚類中心，以Z0作為粒子的初始位置．根據當前位置，利用適用度函數計算公式計算適應值F0(X)，設置當前適應值為個體極值Pi，當前位置為個體極值位置Xi，根據當前各個粒子的個體極值Pi和個體極值位置Xi ，找出全局極值Pg和全局極值位置GX，且Pg=min（Pi）；
2)按照公式(1)和公式(2)，更新粒子的速度和位置，并把粒子的速度限制在Vmax內；
3)計算適應值F，并根據F得到當前各個粒子的個體極值Pi 和個體極值位置Xi。如果當前迭代次數n < 迭代次數nmax ，轉步驟2繼續執行；
4)找出全局極值Pg和全局極值位置GX．K個全局極值位置即新的K個聚類中心，根據當前全局極值位置GX，將事務按最小距離原則分配給新的k個聚類中心，轉到步驟2繼續執行；
由于在執行PSO聚類的過程中以每個模式樣本到聚類中心的距離之和達到最小為標準，因此，本文選取PSO算法的適應度函數為
其中k為聚類數目，Sj為第j個模式分類，Zj為第j個聚類中心，1
3. 基于PSO算法的關聯規則挖掘
該算法首先利用PSO算法將原始大數據庫進行聚類劃分為多個子數據庫，再結合改進型Apriori算法對子數據庫進行局部頻繁項集挖掘，最后合并各個子數據庫的挖掘結果．其具體步驟如下：
輸入：粒子數N，最大迭代次數nmax，聚類個數k，數據集D，最小支持數supmin ，最小置信度confmin ；
輸出：支持數大于supmin，置信度大于confmin的關聯規則模式；
1)利用PSO算法將原始數據庫D劃分為k個子數據庫{D1，D2，⋯，Dk}；
2)子數據庫D采用改進型的Apriori算法進行數據挖掘得到頻繁項集；
3)最后合并各個子數據庫{D1，D2，⋯，Dk}中頻繁項集．如果supD(X)大于支持數閾值supmin,，則為全局頻繁項集． 其中： ， 為項集X在數據集Di中出現的頻數。
4. 結論
本文提出的基于PSO算法的關聯規則挖掘方法不但繼承了改進的Apriori算法“高效性”的優點，同時也一定程度上克服了Apriori算法不適合于對海量數據進行關聯規則挖掘的缺點。運用以上方法，既使數據挖掘對海量數據進行整體挖掘成為現實，還能夠解決海量數據挖掘時間和空間復雜度過高的難點。
參考文獻
[1] 鄭吉平,秦小麟. 數據挖掘中采樣技術的研究[J].系統工程與電子技術,2005,27(11).
[2] 曹志宇，張忠林. 快速查找初始聚類中心的K―means算法[J].蘭州交通大學學報,2009,28(6)．
[3] 劉叢林,張忠林,曾慶飛. PSO算法在關聯規則挖掘中的應用[J].蘭州交通大學學報,2010,29(3).
[4] Kennedy J，Eberhart R．Particle swarm optimization[C]//Proceeding IEEE International of first Conference on Neural Networks．NJ：IEEE Press，1995：167―171．
[5] Kennedy R J，Eberhart R A new optimizer using particle swarm theory[C] //Proceeding of the 6th International of fi-rst Symposium on Micro Machine and Human science. NJ： IEEE Press，1995：39-43．
海量數據范文5
關鍵詞：鍵值；云計算；集群
中圖分類號：TP311 文獻標識碼：A 文章編號：1009-3044（2013）07-1491-03
在當今這個信息爆炸的時代，互聯網上的數據訪問量正以幾何級數的速度增長，提高對海量數據的訪問和處理的需求變得日益迫切?！霸朴嬎恪奔夹g的出現使得快捷高效完成TB乃至PB級的數據挖掘成為可能。Google公司以Map/Reduce為基礎，結合GFS、Bigtable已經成為全球互聯網搜索引擎的翹楚，而Google取得成功的關鍵恰恰是因為其是最早也是最成功的“云計算”理念的實踐者，但Google公司出于技術保護并沒有開放其云計算模型的實現細節。
Hadoop作為Apache組織中一個專注于DFS和Map/Reduce的開源項目，完成了對Google的MapReduce編程模型、GFS分布式文件系統等云計算模型核心技術的開源實現，使得全球數以萬計的開發者和眾多實力雄厚的軟件廠商開啟了基于Hadoop研發“云計算”模型和應用的技術浪潮。
1 Hadoop整合Cassandra的必要性
1.1 Hadoop的特性
Hadoop是Apache開源組織的一個能夠對行量數據進行分布式處理的軟件框架，源于Lucene和Nutch兩個開源項目，其核心技術是Map/Reduce和HDFS，分別是對Google的MapReduce和GFS的開源實現。基于Hadoop可以輕松的編寫可處理海量數據的分布式并行程序，并將其運行于由成百上千個節點組成的大規模計算機集群上。
Hadoop的主要特性包括：
1）Hadoop的Map/Reduce能夠運行在由數量龐大的商用服務器組成的大型集群上，可對TB級數據以可靠容錯的方式進行復雜分析運算和并行處理。
2）Hadoop的分布式文件系統HDFS是一個具有高度容錯性能的系統，它不但具有良好的錯誤檢測功能還可以快速自動的進行數據恢復。HDFS被設計可以存取TB級的數據，適合部署在由大量廉價計算機所組成的大規模集群上。
Hadoop的主要缺點是其雖然擁有自己的分布式文件系統HDFS，但HDFS的實時讀寫性能較差，在并發性和可擴展性方面也較為欠缺，這就使得長于運算能力的Hadoop迫切的需要找到一個能夠很好的支持并發處理并且擁有良好的實時存取能力和可擴展性的數據存儲系統。
1.2 Cassandra的特性
Cassandra最初是由Facebook開發的一套開源的分布式鍵值數據庫系統，它同時具備了Google BigTable的數據模型和Amazon Dynamo的完全分布式架構，具有良好的可擴展性，目前被很多大型的Web2.0網站所使用，是一種流行的分布式結構化數據存儲方案。
Cassandra的主要特性包括：
（1）數據具備最終一致性，集群整體的可用性高。
（2）分層數據壓縮，能夠有效地減少數據體積，同時也能減少磁盤I/O。
（3）高可用、可擴展，無中心節點設計使得單點故障不影響集群服務，集群性能可線性擴展。
Cassandra的主要缺點是其雖然支持Map/Reduce計算，但自身并沒有包含Map/Reduce功能，因此也就不具備自己對數據進行復雜分析運算的能力，需要借助于其他分布式計算工具才可以。
1.3 Hadoop與Cassandra取長補短
Cassandra是一個功能非常強大的海量數據存儲系統，但它的劣勢是缺乏對海量數據進行分析的能力，而Hadoop雖然提供了海量存儲的能力，但是數據存儲的特點是一次寫入、多次讀取，不支持數據的修改，因此無法實現實時讀寫。所以，可以將Cassandra存儲的能力與Hadoop Map/Reduce計算的能力進行整合。Cassandra提供底層的存儲，支持數據的實時讀寫，Hadoop提供批量計算的能力，將Cassandra中的數據批量加載到mapper和reducer中進行計算，得出最終的結果。
2 Hadoop整合Cassandra實施方案
Hadoop整合Cassandra就是兩者互相取長補短的過程，即將Hadoop Map/Reduce的計算能力和Cassandra的存儲能力進行結合。具體實施方案可以概括為，先將待處理的海量非結構化數據通過Hadoop Map/Reduce導入到Key-Value數據庫Cassandra中，以實現數據的實時存取，解決Hadoop的HDFS存儲能力欠缺的問題；然后，當需要對海量非結構化數據進行數據分析時再將Cassandra中存儲的數據作為輸入通過Hadoop Map/Reduce進行計算得出結果。這樣一來既發揮了Hadoop與Cassandra各自的優勢，又摒棄了二者的不足，從而相得益彰。
2.1使用Map/Reduce將Hadoop海量數據導入Cassandra中
通過Map/Reduce程序，可以將Hadoop分布式文件系統中的海量文件批量導入Cassandra中以實現實時存取。例如某通信系統需要記錄每個客戶的通話時長，所以客戶的通話時長（以秒為單位）數據實時寫入Cassandra系統中，并且數據分析人員可以在任意時刻啟動Map/Reduce分析程序，從Cassandra中讀取客戶的通話時長數據進行統計分析。
通信系統按照客戶某天某一小時劃分，客戶通信記錄文件CallRecord.txt文件格式如下：
18023509018 - 800
數據文件CallRecord.txt的每一行中，“”符號前是客戶使用的手機號，“”符號后是客戶使用該手機號的通話時長。存儲呼叫者通話時長的ColumnFamily可以采用Standard類型，Column排序規則為TimeUUIDType，Row的key為呼叫者的手機號碼，Column的值為通話時長。
Cassandra默認的ColumnFamily在Cassandra/conf/schema.example.txt文件中定義，也可自定義ColumnFamily即在Cassandra/conf目錄下新建schema.txt，內容如下：
create keyspace MyKeyspace1
with replication_factor = 1 …
2.1.1 編寫Map/Reduce程序
根據需求，在map過程中需要拆分CallRecord.txt文件中的數據，提取出呼叫者的手機號碼和對應通話時長。在map完成之后，關閉Thrift客戶端，釋放占用的資源。以下是MapReduce程序CallRecord.java的代碼組成：
1）編寫mapper函數
在mapper中，需要先初始化Thrift客戶端，設置使用的Keyspace，以將數據寫入Cassandra服務器中，實現邏輯如下：
tr.open（）；
cassandraClient.setKeyspace（“MyKeyspace1”）；
初始化Thrift客戶端后，在mapper函數中拆分輸入數據，找出呼叫者手機號碼和對應通話時長，構建需要插入Cassandra的Column，實現邏輯如下：
cassandraClient.insert（
ByteBuffer.wrap（mobileNum.getBytes（“utf-8”）），cp，c，ConsistencyLevel.ONE）；
在mapper函數執行完畢后，還需要將Thrift客戶端關閉，釋放占用資源。
super.close（）；
本程序只需編寫mapper函數即可，所以在Map/ Reduce程序的運行設置中將Reduce的個數設置為0，這樣就不會執行Reduce流程了。
conf.setNumReduceTasks（0）；
2.1.2 打包運行Map/Reduce程序
將CallRecord程序代碼打成JAR包，名為CallRecord.jar，入口類為CallRecord，然后就可以對以上這個Map/Reduce程序進行測試了。
2.2 將Cassandra中的數據作為Map/Reduce輸入
當需要對海量非結構化數據進行數據分析計算時，可以使用Map/Reduce程序將Cassandra中存儲的某個Keyspace下的Column中的所有數據作為Map/Reduce的數據輸入Hadoop，然后由Hadoop得出運算結果。以下是MapReduce程序CallCount.java的代碼組成：
2.2.1 編寫Map/Reduce程序
1）編寫mapper函數
mapper函數中輸入的數據為Row的Key，以及該Key對應的所有Column。在通話時長的統計中，只需要關注每一個Column的Value即可。
2.2.2打包運行Map/Reduce程序
將CallRecord程序代碼打成JAR包，名為CallCount.jar，入口類為CallCount，然后就可以對以上這個Map/Reduce程序進行測試了
3 整合Hadoop與Cassandra所遇到的主要問題
3.1 數據傳輸速率降低造成網絡阻塞
當數據達到海量級別的時候，應用請求的運算離它操作的數據越近效率就越高。因為這樣能降低網絡阻塞的影響，提高數據的傳輸速率和吞吐率。將運算移動到數據附近，比將數據移動到應用所在更好。整合Hadoop與Cassandra雖然解決了數據實時存取與分布式運算分析的問題，但在二者之間的數據相互傳輸勢必會降低整體運行的速率。
3.2 Hadoop與Cassandra版本兼容性問題
Hadoop與Cassandra的整合也會遇到各自不同的版本之間的兼容性問題。例如：Cassandra 0.6.X默認只能與Hadoop0.20.X進行整合，與Hadoop0.19.X整合就要修改Cassandra的源代碼支持才可以。
4 結束語
“云計算”時代的到來將勢必改變互聯網的服務運營模式，甚至是對整個IT領域的發展產生廣泛深遠的影響。在云計算技術浪潮席卷全球的今天，無論對于微軟、谷歌之類的IT巨頭還是廣大的中小軟件企業，這都是一個拓寬自身發展空間的絕佳機會。Hadoop作為當今分布式計算領域最為成功的開源框架，與可靠性和可擴展性俱佳的Cassandra鍵值數據庫相結合，發揮各自在分析計算與海量存取方面的優勢，將為在開源領域部署云計算應用開創一種全新的切實有效的技術模式。
參考文獻：
[1] 鄧倩妮，陳全.云計算及其關鍵技術[J].高性能計算與發展應用，2009，1（26）：2-6.
[2] 蘇翔宇. Key-Value數據庫及其應用研究[J].電腦知識與技術，2012.
海量數據范文6
關鍵詞： 分布式索引； 局部索引； 全局索引； 海量數據
中圖分類號：TP392 文獻標志碼：A 文章編號：1006-8228（2013）08-01-04
0 引言
信息檢索系統（IRS：Information Retrieval System）已成為人們日常生活和學習中經常會使用到的工具（如文獻檢索、網頁檢索等）。隨著數據規模的增大，信息檢索系統開始采用分布式系統架構來解決所面臨的大數據問題。由此而引出的索引如何在分布式系統之中組織與分布的問題即是分布式索引架構問題。全局索引架構（Global Index）與局部索引架構（Local Index）是兩種最主要的分布式索引架構，幾十年以來，大量的研究和實驗對它們的優缺點進行了詳細分析與比較。
全局索引架構針對整個數據集建立一個統一的索引，然后根據索引關鍵字的順序將索引切分成多個索引片段，每個索引片段存放在一個單獨的索引節點上。全局索引架構在執行一個檢索時所需要訪問的索引節點相對較少，但這也導致其每次讀取的數據量較大；由于數據的處理需要集中在中間節點上進行，全局索引架構網絡傳輸的數據量更大；所有的數據處理操作集中在中間節點上執行，在面對海量數據時這將成為全局索引架構不能滿足用戶需求的關鍵瓶頸；由于是針對整個數據集建立倒排索引，因此在全局索引架構在面對索引的更新與增量時相比局部索引架構難度更大。
分布式局部索引架構即是將大的數據集隨機或者按照一定的規則劃分成多個小數據集，針對每個小數據集建立單獨的索引塊，一般一個索引塊會存放在一個單獨的索引節點上。局部索引架構的每個索引節點獨立的完成檢索，因此具有較好的容災容錯性能；在索引更新及增量時，由于其每個索引節點相互獨立，因此更新與增量的影響范圍較?。挥捎谒饕濣c返回給中間節點的數據都是經過處理的，因此相比全局索引架構而言局部索引架構網絡傳輸的數據量更小。局部索引架構的缺點在于檢索的開銷較大，其每一個檢索條件都會被發送到所有索引節點上去執行。
混合索引架構結合了全局索引架構與局部索引架構的優點，但高度的數據冗余造成了極大的數據膨脹，在大多數的應用當中這一點通常無法被用戶接受；同時副本數量過多也導致數據的更新與增量難度更大。由于混合索引架構的明顯缺陷，我們在后面的文章中將不再對其進行分析。
1 相關工作
分布式索引架構的研究從上世紀九十年代初開始，但早期有關分布式索引架構[1，2，5，7，9]的研究由于存在數據量較少、硬件環境限制、應用場景不同等問題，導致大家的研究結果有很大的分歧，對于當前海量數據背景下分布式索引架構研究的參考意義不大。Cambazoglu等在2006年通過實驗結果[8]說明局部索引架構有較快的響應速度，而全局索引架構的吞吐率較好，這和我們的觀點是一致的，但實驗的結果是在較少的數據集上取得的（30GB），因此沒有說明全局索引架構在響應時間上問題的嚴重性。
文獻[3，4，7]等都是針對全局索引架構進行優化，他們或者考慮如何減少網絡傳輸的數據量[3，6]，或者使用新的數據處理方式[4]，但都沒有從根本上解決全局索引架構的時間延遲問題，而且用于實驗的數據量都相對偏小，沒有以海量數據為應用背景。
2 理論及分析
在介紹本文方法之前，先說明將用到的數據結構。倒排索引記錄是Key-Value結構的，其中Key是檢索關鍵字，Value是由數據項組成的有序集合。數據項的格式為（ID，score），其中ID表示某個檢索對象的編號（例如文檔編號），該檢索對象中含有檢索關鍵字Key，Value中的數據項都是依據ID排序的；score表示檢索關鍵字Key在該檢索對象中相關性的大小。實際應用之中檢索關鍵字在一個檢索對象中的相關性信息比較復雜，我們在模擬實驗中簡單的使用一個浮點型的非負數值score表示。
2.1 實現全局索引的關鍵步驟
在全局索引架構下對用戶檢索的處理步驟如下。
⑴ 用戶提交檢索條件，檢索條件中含有一個或多個檢索關鍵字Key，中間節點分析檢索條件并將各個不同的檢索關鍵字Key發到其相對應的索引節點；
⑵ 收到檢索關鍵字Key的索引節點即在倒排索引中檢索對應的倒排記錄并將檢索結果返回給中間節點，檢索結果即是倒排記錄中Value；
⑶ 中間節點會收到多個檢索結果（Value），這些檢索結果都是以ID排序的數據項集合，中間節點以ID對這些數據項集合求交集，交集中數據項的相關性值（score）是原來各個集合中有相同ID的數據項的相關性值（score）之和；
⑷ 檢索對象返回給用戶時一般需要分頁，中間節點依據相關性值（score）的大小對交集中的數據項進行排序，相關性值（score）大的數據項對應的檢索對象會先返回給用戶，具體返回的檢索對象需要依據數據項中的ID查找得到。
磁盤讀取、網絡傳輸等不是本文研究的重點。本文主要的關注點在于數據的處理過程，全局索引架構對數據的處理主要是在中間節點上完成的。假設：
A.在一個用戶檢索里面會有m個檢索關鍵字（k1、k2…km）；
B.每個關鍵字ki所對應的Value是由ni個數據項組成的串，設；
C.最終的交集里面有R個數據項。
根據假設，可知中間節點上求交集過程的計算操作次數約為n。如果對交集依據相關性大小進行全排序的話，其時間復雜度為o（Rlog2R），但是一般情況下R較大，而用戶可能只需要查看最相關的幾個文檔，這樣我們既可以將相關性值（score）大的結果找出來并先返回給用戶，而不需要對全部的結果集進行排序。具體操作上可以在求交集的過程中將相關性值（score）大于某個閾值的數據項存在一個桶里，求交集完成后只要先將桶里面的數據項依據其相關性值（score）的大小進行排序即可，桶里面的數據項數量是應用通過閾值控制的，一般遠小于R。閾值一般由數據的規模和每次返回給用戶的檢索對象數量決定。
假設：
D.桶里面等待排序的數據項數量為R'。
則可以將全局索引架構中間節點的計算操作次數tgm表示為：tgm=m+n+R'log2R'。
關鍵字的個數m大多數情況下都是個位數，相比較而言可以忽略不計；在海量數據背景下，n的大小可能是幾千萬、幾億，而存在桶里等待排序的數據項的個數一般只有幾百、幾千，因而n要遠大于R'log2R'，因此也可以簡單地認為：tgm≈n。
2.2 實現局部索引的關鍵步驟
局部索引架構對用戶檢索的處理過程相比全局索引架構而言，在求交集等關鍵步驟上實現了并行化，其具體的處理過程如下。
⑴ 用戶提交檢索條件，中間節點將檢索條件發到每一個索引節點上；
⑵ 局部索引架構索引節點所執行的操作與全局索引架構整個系統所執行的操作相同，包括檢索條件的分析、檢索關鍵字查詢、檢索結果求交集、根據相關性值（score）對交集排序等，只不過這些操作都是本地執行，最后索引節點將按相關性值排序后的檢索結果返回給中間節點；
⑶ 中間節點接收各個索引節點的檢索結果，這些檢索結果都是以相關性值大小排序后的數據項集合，中間節點依據相關性值（score）的大小對這些數據項集合進行歸并排序，同樣，相關性值大的數據項對應的檢索對象將優先返回給用戶。
除使用2.1小節的假設條件外，這里再補充兩個假設：
E.分布式信息檢索系統中有N個索引節點；
F.每次返回給用戶的結果集中數據項的個數為M。
這里需要說明的一點是，M的值并不是分頁后一個頁面所展示的檢索對象的數量，一般而言M是一個頁面所展示檢索對象數量的倍數，比如10倍，用于應對用戶可能的翻頁，而且M小于R'。
局部索引架構索引節點所執行的操作與全局索引架構整個系統所執行的操作相同，參考2.1小節的分析，可以將局部索引架構索引節點的計算操作次數tli表示如下：
該表達式不一定準確，因為不可能每個索引節點在處理檢索時的時間復雜度都是一樣的，實際上由于局部索引架構中數據的劃分是隨機的，具有較好的負載均衡，雖然會有偏差，但是可以接受。
與全局索引架構一樣，局部索引架構的索引節點也可以設置閾值，從而只需對桶里的R'個數據項進行排序，索引節點在給中間節點返回數據時，不必返回全部R'個數據項，只需返回前M個相關性值（score）較大的數據項即可。中間節點會收到N個數據項集合，每個集合M個元素，同樣，中間節點也只需歸并求出前M個相關性值（score）較大的數據項即可。
中間節點使用二路歸并算法對N個數據項集合進行歸并排序，因為多線程并行處理時二路歸并是最優的。局部索引架構中間節點的計算操作次數tlm1可以表示如下：
tlm1的計算表達式是在線程并發度足夠大的情況下取得的，實際的線程并發度是由中間節點CPU總的核心線程數目決定的，假設：
G.中間節點核心線程數目為L。
中間節點共需要運行N-1個線程，則更為精確計算操作次數tlm2可以表示如下：
在實際計算中，計算處理程序獨占整個CPU是最優的情況，這種情況很難達到，所以tlm2的表達式中增加了一個系數eL和一個常數因子bL，并且有eL?1成立。具體eL和bL的值可以通過實驗數據計算得到。
由于系統吞吐率、數據到達中間節點有先后等因素，可以考慮在中間節點上不使用多線程并行，而只是簡單的串行執行即可，這樣得到的中間節點計算操作次數tlm3可以表示如下：
tlm3=M*（N-1）
由于索引節點對檢索的處理都是并行的，因此只需考慮單個索引節點即可，結合中間節點上計算操作的執行次數，則局部索引架構下整個計算過程的計算操作次數tltx可表示如下：
tltx=eltxtli+tlmx+bltx（x=1，2，3）
當tli=tlmx時，即中間節點與索引節點的計算操作次數相同時，但是由于二者計算過程的具體實現不同導致實際測得的計算時間是不同的，因此引入上述表達式中的平衡因子elt以及常數blt。平衡因子elt及常數blt可以結合實際的測量數據，利用線性回歸模型求出來，在2.3小節有更為詳細的分析。
分析比較全局索引架構與局部索引架構的計算操作，可以發現在海量數據背景條件下，局部索引架構明顯優于全局索引架構。同時也應該看到，針對同一個檢索，局部索引架構使用的索引節點更多，一般情況下局部索引架構相比全局索引架構在處理一個檢索時的開銷更大。
2.3 分析局部索引的簇的大小
將局部索引架構的計算操作次數tlt看成N的函數，即：
以執行時間復雜度最小值為目標，對于給定的n值（數據規模），可以求出最優的N值（機群規模），該結論對于在具體應用當中確定分布式機群的規模有參考價值。
對于平衡因子eltx（x=1，2，3）需要結合試驗數據利用線性回歸模型求解，這里先給出具體的回歸模型。實驗時取tlmx=tli（x=1，2，3），即局部索引架構索引節點與中間節點的計算操作次數相同，分別將二者的實際執行時間記為tlmx（x=1，2，3）和Tli，elmx是Tlmx與tlmx的相關系數（x=1，2，3），eli是Tli與tli的相關系數，bli和blmx（x=1，2，3）都是常數因子，則回歸模型可表示如下（x=1，2，3）：
根據條件tlmx=tli（x=1，2，3），由上面的數學模型可得：
計算機的實際計算時間和算法時間復雜度的關系是線性的，所以文章中使用的是線性回歸模型。
2.4 數據擴展和索引架構的選擇
僅就計算的執行時間分析，可以看出在海量數據背景下（即n的值較大時），局部索引架構在計算執行時間上相對于全局索引架構有明顯的優勢；但當數據量較小時（即n的值較小時），這個優勢并不明顯；可以預見當n變小到一定程度時，全局索引架構與局部索引架構的執行時間數據就會相同，這時n的值對于根據數據規模的大小決定采用哪一種索引架構具有一定的參考價值；當n的值再變小時，局部索引架構的表現可能會比較差。
以上分析看似合情合理，但從另一個角度來考慮的話，就會發現問題并非如此。我們把局部索引架構索引節點的個數N考慮進來，那么關于執行時間Y的方程就有兩個自變量（n與N）。由于局部索引架構索引節點的計算操作與全局索引架構中間節點的計算操作相同，取N為最優值，那么當數據規模變?。╪的值變?。┑揭欢ǖ脑葧r，N一定會變為1，那么此時因為只有一個索引節點，全局索引架構與局部索引架構就完全的相同了，因此計算的執行時間也必然相同。
通過上面的分析可以發現，在N取最優值的情況下，當全局索引架構與局部索引架構的執行時間相同時，局部索引架構就會退化為全局索引架構。
實際應用之中的情況可能會不同，計算執行時間的最優值并不是用戶最為重要的目標，由于全局索引架構相對比較節省資源，所以在滿足應用需求的情況下用戶可能更愿意使用全局索引架構。
3 結束語
本文以海量數據為背景條件，研究了信息檢索系統中分布式索引組織架構問題。通過分析說明了面對海量數據時分布式局部索引架構是信息檢索系統的必然選擇，分布式全局索引架構由于不可接受的時間延遲問題而被排除。本文對海量數據背景下分布式索引架構問題的研究成果不僅僅適用于一般信息檢索系統，對于數據庫的多條件聯合查詢、相似性搜索中的度量空間索引等也有一定的參考意義，雖然應用環境與具體的問題都不相同，但索引的分布式架構組織問題是相同的。未來的工作我們希望可以在完善的實驗環境下將分布式索引架構的其他關鍵因素納入考慮范圍，例如磁盤讀取、網絡傳輸等。由于全局索引架構在檢索成本上占有優勢，我們下一步的工作還包括優化全局索引架構的處理模式，目標是通過優化滿足用戶的需求。本文所有的討論與實驗都是基于現有的軟、硬件環境，相信在未來，隨著計算機軟、硬件技術的發展，我們解決這些問題將會更加的便利。
參考文獻：
[1] RIBEIRO-NETO， B. AND BARBOSA， R. Query performance for tightly coupled distributed digital libraries.In Proceedings of the ACM Digital Libraries， Pittsburgh， PA， I. Witten， R. Akscyn， and F. M. S. III， Eds. 1998. ACM Press，182-190
[2] A. MacFarlane， J. McCann， and S. Robertson. Parallel search using partitioned inverted files. In Proceedings of the 7th International Symposium on String Processing and Information Retrieval， pages 209-220， La Coruna， Spain， September 2000. IEEE Computer Society.
[3] Zhang J， Suel T. Optimized inverted list assignment in distributed search engine architectures[C]. Parallel and Distributed Processing Symposium， 2007. IPDPS 2007. IEEE International. IEEE，2007：1-10
[4] Moffat A， Webber W， Zobel J， et al. A pipelined architecture for distributed text query evaluation[J]. Information Retrieval，2007.10（3）：205-231
[5] Badue C， Baeza-Yates R， Ribeiro-Neto B， et al. Distributed query processing using partitioned inverted files[C]. Proc. SPIRE，2001：10-20
[6] Kayaaslan E， Aykanat C. Efficient query processing on term-based-partitioned inverted indexes[R]. Technical Report BU-CE-1102， Bilkent University， Computer Engineering Department， 2011. Also available at： http：// cs. bilkent. edu. tr/tech-reports，2011.
[7] Xi W， Sornil O， Luo M， et al. Hybrid partition inverted files：Experimental validation[M]. Research and Advanced Technology for Digital Libraries. Springer Berlin Heidelberg，2002：422-431
