大規(guī)模可擴展索引技術(shù)的研究和系統(tǒng)實現(xiàn) 碩士論文

69頁共計28835字
摘 要
隨著互聯(lián)網(wǎng)的發(fā)展，原始的數(shù)據(jù)庫系統(tǒng)無法滿足大數(shù)據(jù)量相關(guān)性檢索的需求。從而基于倒排表的索引系統(tǒng)越來越多的應(yīng)用在各項服務(wù)中。但是索引系統(tǒng)和數(shù)據(jù)庫系統(tǒng)一樣，有著較為復(fù)雜的內(nèi)部邏輯和外部行為，如何創(chuàng)建我們需要的索引系統(tǒng)，如何優(yōu)化我們的索引系統(tǒng)，是困擾很多索引系統(tǒng)構(gòu)建者和使用者的難題。
本文的研究范疇是用于信息檢索的索引系統(tǒng)，通過一個真實的索引系統(tǒng)——Paradise索引系統(tǒng)，本文從三個方面進行分析和研究：對索引系統(tǒng)進行功能模塊上的分析；對索引系統(tǒng)開發(fā)和使用中的性能問題的研究和分析；對一個實際系統(tǒng)的系統(tǒng)實現(xiàn)的詳細。具體為：
1) 索引系統(tǒng)的模塊分析
本文詳細分析了作為一個復(fù)雜系統(tǒng)的索引系統(tǒng)，其創(chuàng)建和使用都受到很多條件的制約。本文分析了索引系統(tǒng)的常見的需求，比如如何對原始的文檔集合進行分析，如何設(shè)計索引內(nèi)部文檔的表示能力，索引如何創(chuàng)建，如何存儲等，劃分了一系列基本的功能模塊。
2) 索引系統(tǒng)的性能分析
因為索引系統(tǒng)的目的是快速的響應(yīng)檢索需求，所以效率問題一直是索引技術(shù)的核心問題。在模塊功能分析的基礎(chǔ)之上，本文進一步分析了索引創(chuàng)建和檢索中常見的性能問題，提出了基本的解決方案。同時，對于如何對索引系統(tǒng)進行整體的和局部的量化分析，引入了DQ法則，嘗試給出一個指導(dǎo)實踐的經(jīng)驗公式。
3) Paradise索引系統(tǒng)的實現(xiàn)分析
對于問題的分析，需要一個具體的系統(tǒng)進行實踐。在深入研究天網(wǎng)搜索引擎已有的索引系統(tǒng)和相關(guān)索引系統(tǒng)基礎(chǔ)上，同時在大量閱讀了相關(guān)專業(yè)文獻之后，我們進行了分析和研究，設(shè)計實現(xiàn)了863課題支持的Paradise項目的索引系統(tǒng)。本文以系統(tǒng)的基本模塊和重要接口為核心，分析了系統(tǒng)的基本框架能力以及如何進一步對系統(tǒng)進行擴充。
目錄
摘 要 3
Abstract 4
目錄 5
第一章 緒 論 6
1.1 索引系統(tǒng)背景 6
1.1.1 互聯(lián)網(wǎng)服務(wù)系統(tǒng) 6
1.1.2 Data / Query 法則 7
1.1.3 需求快速查詢的場景 7
1.2 和數(shù)據(jù)庫系統(tǒng)的比較 8
1.2.1 數(shù)據(jù)庫系統(tǒng)的能力 8
1.2.2 索引系統(tǒng)和數(shù)據(jù)庫系統(tǒng)的異同 8
1.3 索引系統(tǒng)的簡單用例 9
1.3.1 索引系統(tǒng)基本模塊 10
1.3.2 索引系統(tǒng)基本流程 10
1.4 本文的主要工作 11
1.4.1 本文的主要研究點 11
1.4.2 本文的主要創(chuàng)新點 11
1.5 本文組織結(jié)構(gòu) 11
第二章 索引系統(tǒng)分析 12
2.1 索引核心模塊分析 12
2.1.1 分析模塊 12
2.1.2 文檔表示模塊 12
2.1.3 存儲模塊 15
2.1.4 索引創(chuàng)建 15
2.1.5 存儲鏡像的邏輯視圖 18
2.1.6 索引檢索 19
2.2 大規(guī)模索引專有模塊 20
2.2.1 壓縮模塊 20
2.2.2 緩存模塊 26
2.3 動態(tài)索引 28
2.3.1 版本控制 29
2.3.2 內(nèi)存索引 31
2.4 分布式索引 31
2.4.1 可用性和可靠性與DQ法則 32
2.4.2 索引切分和索引冗余 34
2.4.3 針對可用性和效率的解決方案 35
2.4 本章小結(jié) 35
第三章 索引優(yōu)化 36
3.1 索引創(chuàng)建的優(yōu)化 36
3.1.1 創(chuàng)建時期內(nèi)存壓縮 36
3.1.2 動態(tài)索引二路歸并的塊合并時機 37
3.1.3 大索引多路歸并方法 38
3.2 索引檢索效率的優(yōu)化 39
3.2.1 檢索時效率分析 39
3.2.2 使用塊狀壓縮和跳查來降低CPU使用 39
3.2.3 使用緩存機制來降低IO 43
3.3 索引常數(shù) 44
3.3.1 單機的服務(wù)能力上限 44
3.3.2 整體服務(wù)優(yōu)化 45
3.3.3 單機索引常數(shù) 46
3.4 本章小結(jié) 46
第4章 Paradise索引系統(tǒng)框架 48
4.1 系統(tǒng)目的 48
4.1.1 面向搜索引擎服務(wù) 48
4.1.2 可擴展性，可實驗性 48
4.2 基本模塊詳細分析 48
4.2.1 分析模塊 49
4.2.2 文檔表述模塊 50
4.2.3 存儲模塊 51
4.2.4 壓縮模塊 52
4.2.5 緩存模塊 53
4.2.6 索引模塊 54
4.3 索引創(chuàng)建流程用例分析 57
4.4 索引提供的檢索接口用例分析 59
第五章 總結(jié)和展望 63
5.1 本文總結(jié) 63
5.2 進一步工作 63
參考文獻 65
致謝 68

關(guān)鍵詞：信息檢索，索引系統(tǒng)，索引優(yōu)化，倒排表
參考文獻
[1] 彭波. (2004). 搜索引擎檢索系統(tǒng)的效率優(yōu)化與效果評估研究. 北京大學(xué).
[2] Zobel, J. and Moffat, A, Inverted files for text search engines, ACM Computing Surveys (CSUR), 2006, ACM New York, NY, USA
[3] Witten, I. H., Moffat, A. & Bell, T. C. (1999), Managing Gigabytes: Compressing and Indexing Documents and Images, second edn, Morgan Kaufmann, San Francisco, California.
[4] Zhu, M. and Shi, S. and Li, M. and Wen, J.R., Effective top-k computation in retrieving structured documents with term-proximity support, Proceedings of the sixteenth ACM conference on Conference on information and knowledge management, 2007, ACM New York, NY, USA
[5] Strohman, T., DYNAMIC COLLECTIONS IN INDRI, Technical report, Center for Intelligent Information Retrieval, 2005
[6] Strohman, T. and Croft, W.B. Low Latency Index Maintenance in Indri, OSIR 2006
[7] Frakes, W.B. and Baeza-Yates, R., Information retrieval: data structures and algorithms, 1992, Prentice-Hall, Inc. Upper Saddle River, NJ, USA
[8] Brown, E.W. and Callan, J.P. and Croft, W.B. Fast incremental indexing for full-text information retrieval, Proceedings of the 20th International Conference on Very Large Data Bases, 1994
[9] Scholer, F. and Williams, H.E. and Yiannis, J. and Zobel, J., Compression of inverted indexes For fast query evaluation, Proceedings of the 25th annual international ACM SIGIR conference on Research and development in information retrieval, 2002, ACM Press New York, NY, USA
[10] Zobel, J. and Moffat, A. Adding Compression to a Full-text Retrieval System, Software - Practice and Experience, 1995
[11] Williams, H.E. and Zobel, J., Compressing Integers for Fast File Access, 1999, Br Computer Soc
[12] Scholer, F. and Williams, H.E. and Yiannis, J. and Zobel, J., Compression of inverted indexes For fast query evaluation, Proceedings of the 25th annual international ACM SIGIR conference on Research and development in information retrieval, 2002, ACM Press New York, NY, USA
[13] Zukowski, M. and Heman, S. and Nes, N. and Boncz, P., Super-Scalar RAM-CPU Cache Compression, Proceedings of the International Conference of Data Engineering (IEEE ICDE), Atlanta, GA, USA, 2006
[14] Baeza-Yates, R. and Gionis, A. and Junqueira, F. and Murdock, V. and Plachouras, V. and Silvestri, F., The impact of caching on search engines, Proceedings of the 30th annual international ACM SIGIR conference on Research and development in information retrieval, 2007, ACM Press New York, NY, USA
[15] Long, X. and Suel, T., Three-Level Caching for Efficient Query Processing in Large Web Search Engines, World Wide Web, 2006, Springer
[16] Lempel, R. and Moran, S., Predictive caching and prefetching of query results in search engines, Proceedings of the 12th international conference on World Wide Web, 2003, ACM Press New York, NY, USA
[17] Saraiva, P.C. and de Moura, E.S. and Ziviani, N. and Meira, W. and Fonseca, R. and Riberio-Neto, B., Rank-preserving two-level caching for scalable search engines, Proceedings of the 24th annual international ACM SIGIR conference on Research and development in information retrieval, 2001, ACM Press New York, NY, USA
[18] Eric W. Brown, Fast evaluation of structured queries for information retrieval,SIGIR’95:Proceedings of the 18th annual international ACM SIGIRconference onResearch and development in information retrieval (NewYork, NY, USA),ACM Press, 1995, pp. 30–38.A
[19] Nicholas Lester, Justin Zobel, and Hugh E. Williams, In-place versus re-build versus re-merge: index maintenance strategies for text retrieval systems, Proceedings of the 27th conference on Australasian computer science, Australian Computer Society, Inc., 2004, pp. 15–23.A
[20] N. Lester, A. Moffat, and J. Zobel, "Fast on-line index construction by geometric partitioning",Proceedings of the ACM CIKM Conference on Information and Knowledge Management, A. Chowdhury, N. Fuhr, M. Ronthaler, H.-J. Schek, and W. Teiken (eds), Bremen, Germany, November 2005. pp. 776-783.
[21] Stefan Büttcher, Charles L. A. Clarke, and Brad Lushman. Hybrid Index Maintenance for Growing Text Collections. Proceedings of the 29th ACM Conference on Research and Development on Information Retrieval (SIGIR 2006). Seattle, USA, August 2006.
[22] Zobel, J., Moffat, A. & Ramamohanarao, K. (1998), “Inverted files versus signature files for text indexing”, ACM Transactions on Database Systems 23(4), 453–490.
[[29] Carmel, D. and Cohen, D. and Fagin, R. and Farchi, E. and Herscovici, M. and Maarek, Y.S. and Soffer, A., Static index pruning for information retrieval systems, 2001, ACM Press New York, NY, USA
[30] Carmel, D. and Amitay, E. and Herscovici, M. and Maarek, Y. and Petruschka, Y. and Soffer, A., Juru at TREC 10-Experiments with Index Pruning, Proceedings of NIST TREC, 2001
[31] S Büttcher, CLA Clarke, A document-centric approach to static index pruning in text retrieval systems, Proceedings of the 15th ACM international conference on Information and knowledge management, 2006, ACM Press New York, NY, USA
[32] Performance of Compressed Inverted List Caching in Search Engines, 2008, World Wide Web.
[33] Brewer, E.A., Lessons from Giant-Scale Services, IEEE INTERNET COMPUTING, 2001
[34] Guo, R. and Cheng, X. and Xu, H. and Wang, B., Efficient on-line index maintenance for dynamic text collections by using dynamic balancing tree, Proceedings of the sixteenth ACM conference on Conference on information and knowledge management, 2007