1、天网搜索平台PARADISE闫宏飞北京大学计算机系网络实验室2009/4/24信息检索前沿概述闫宏飞北京大学计算机系网络实验室2009/4/24Outline Issues: search engine and web mining Goal: Framework Principles: Related components (照应任务各部分关联) Implementation: Achievements （应用成果） Case study （具体到一事）Search Engine and Web Mining Crawling Full-text indexing Retrieving We
2、b archiving and Mining WebGraph: bowtie teapot Model: bag of words Infomall, CDAL: archive histrace Evaluation: manual automatic Platform: proprietary openOutline Motivation to Build PARADISE Design and Implement PARADISE Research Issues of ConcernCorpus (1/3) Shakespeares collected works A gzipped
3、tar-file 2039k http:/www.cs.su.oz.au/matty/Shakespeare/shakespeare.tar.gz RCV1, Reuters Corpus Volume 1. one year of Reuters newswire 1996-08-20 to 1997-08-19 contains about 810,000 Reuters English Language News stories. requires about 2.5 GB for storage of the uncompressed files. http:/trec.nist.go
4、v/data/reuters/reuters.html Corpus (2/3) CWT100GB, Chinese Web Test collection 2004年6月搜集，有5,712,710个网页，解压容量为90GB。 CWT200GB 2005年11月搜集，有37,482,913个网页，压缩容量为197GBhttp:/www.cwirf.org/Corpus (3/3)2008/10/15Hardware assumptionssymbol statistic valuesaverage seek time 5 ms = 5 x 103 sb transfer time per by
5、te 0.02 s = 2 x 108 s processors clock rate10 9 splowlevel operation 0.01 s = 108 s (e.g., compare & swap a word) size of main memory several GB size of disk space 1 TB or moreReuters RCV1 statistics symbolstatistic value N documents 800,000 L avg. # tokens per doc 200 Mterms (= word types) 400,000
6、avg. # bytes per token 6 (incl. spaces/punct.) avg. # bytes per token4.5 (without spaces/punct.) avg. # bytes per term7.5 tokens100,000,0004.5 bytes per word token vs. 7.5 bytes per word type: why? Documents are parsed to extract words and these are saved with the Document ID.I did enact JuliusCaesa
7、r I was killed i the Capitol; Brutus killed me.Doc 1So let it be withCaesar. The nobleBrutus hath told youCaesar was ambitiousDoc 2Index constructionTermDoc #I1did1enact 1julius1caesar1I1was1killed1i1the1capitol1brutus1killed1me1so2let2it2be2with2caesar2the2noble 2brutus2hath 2told 2you2caesar 2was2
8、ambitious2TermDoc #I1did1enact 1julius1caesar1I1was1killed1i1the1capitol1brutus1killed1me1so2let2it2be2with2caesar2the2noble 2brutus2hath 2told 2you2caesar 2was2ambitious2TermDoc #ambitious2be2brutus1brutus 2capitol1caesar1caesar2caesar2did1enact1hath1I1I 1i1it2julius1killed1killed1let2me1noble2so2t
9、he1the 2told2you2was1was2with2 Key step After all documents have been parsed, the inverted file is sorted by terms. We focus on this sort step.We have 100M items to sort.Scaling index construction In-memory index construction does not scale. How can we construct an index for very large collections?
10、Taking into account the hardware constraints Memory, disk, speed etc.Sort-based Index constructionAs we build the index, we parse docs one at a time. While building the index, we cannot easily exploit compression tricks (you can, but much more complex)The final postings for any term are incomplete u
11、ntil the end.At 12 bytes per postings entry, demands a lot of space for large collections.T = 100,000,000 in the case of RCV1 So we can do this in memory in 2008, but typical collections are much larger. E.g. New York Times provides index of 150 years of newswireThus: We need to store intermediate r
12、esults on disk.Use the same algorithm for disk? Can we use the same index construction algorithm for larger collections, but by using disk instead of memory? No: Sorting T = 100,000,000 records on disk is too slow too many disk seeks. We need an external sorting algorithm.Bottleneck Parse and build
13、postings entries one doc at a time Now sort postings entries by term (then by doc within each term) Doing this with random disk seeks would be too slow must sort T=100M recordsIf every comparison took 2 disk seeks, and N items could besorted with N log2N comparisons, how long would this take? 12-byt
14、e (4+4+4) records (term, doc, freq). These are generated as we parse docs. Must now sort 100M such 12-byte records by term. Define a Block 10M such records Can easily fit a couple into memory. Will have 10 such blocks to start with. Basic idea of algorithm: Accumulate postings for each block, sort,
15、write to disk. Then merge the blocks into one long sorted order.BSBI: Blocked sort-based Indexing (Sorting with fewer disk seeks)BSBI: Blocked sort-based IndexingRemaining problem with sort-based algorithm Our assumption was: we can keep the dictionary in memory. We need the dictionary (which grows
16、dynamically) in order to implement a term to termID mapping. Actually, we could work with term,docID postings instead of termID,docID postings . . . . . . but then intermediate files become very large. (We would end up with a scalable, but very slow index construction method.)SPIMI: Single-pass in-m
17、emory indexing Key idea 1: Generate separate dictionaries for each block no need to maintain term-termID mapping across blocks. Key idea 2: Dont sort. Accumulate postings in postings lists as they occur. With these two ideas we can generate a complete inverted index for each block. These separate in
18、dexes can then be merged into one big index.SPIMI-Invert Merging of blocks is analogous to BSBI.Distributed indexing For web-scale indexing (dont try this at home!): must use a distributed computing cluster Individual machines are fault-prone Can unpredictably slow down or fail How do we exploit suc
19、h a pool of machines?Google data centers Google data centers mainly contain commodity machines. Data centers are distributed around the world. Estimate: a total of 1 million servers, 3 million processors/cores (Gartner 2007) Estimate: Google installs 100,000 servers each quarter. Based on expenditur
20、es of 200250 million dollars per year This would be 10% of the computing capacity of the world!?!Google data centers If in a non-fault-tolerant system with 1000 nodes, each node has 99.9% uptime, what is the uptime of the system? Answer: 37% Calculate the number of servers failing per minute for an
21、installation of 1 million servers.Distributed indexing Maintain a master machine directing the indexing job considered “safe”. Break up indexing into sets of (parallel) tasks. Master machine assigns each task to an idle machine from a pool.Parallel tasks We will use two sets of parallel tasks Parser
22、s Inverters Break the input document corpus into splits Each split is a subset of documents (corresponding to blocks in BSBI/SPIMI)Parsers Master assigns a split to an idle parser machine Parser reads a document at a time and emits (term, doc) pairs Parser writes pairs into j partitions Each partiti
23、on is for a range of terms first letters (e.g., a-f, g-p, q-z) here j=3. Now to complete the index inversionInverters An inverter collects all (term,doc) pairs (= postings) for one term-partition. Sorts and writes to postings listsData flowsplitsParserParserParserMastera-f g-p q-za-f g-p q-za-f g-p
24、q-zInverterInverterInverterPostingsa-fg-pq-zassignassignMapphaseSegment filesReducephaseMapReduce The index construction algorithm we just described is an instance of MapReduce. MapReduce (Dean and Ghemawat 2004) is a robust and conceptually simple framework for distributed computing without having
25、to write code for the distribution part. They describe the Google indexing system (ca. 2002) as consisting of a number of phases, each implemented in MapReduce.MapReduce Index construction was just one phase. Another phase: transforming a term-partitioned index into document-partitioned index. Term-
26、partitioned: one machine handles a subrange of terms Document-partitioned: one machine handles a subrange of documents most search engines use a document-partitioned index better load balancing, etc.Schema for index construction in MapReduceSchema of map and reduce functionsmap: input list(k, v) red
27、uce: (k,list(v) outputInstantiation of the schema for index constructionmap: web collection list(termID, docID)reduce: (, , ) (postings list1, postings list2, )Example for index constructionmap: d2 : C died. d1 : C came, C ced. (, , , , , reduce: (, , , ) (, , , )有几个问题需要解决 很难找到合适的硬件设施，基于这些数据开展工作 存储，
28、运行，维护，. 缺少处理这些数据的有效的软件工具 分析，检索，评测，. 如何维护有state of arts算法的软件工具 模块替换，功能测试，性能测试，智能中文搜索引擎技术研究及平台构建 由一个平台平台, 四个任务组成的. 达到平台能够展示四个任务. 平台是: 一个开放式开放式智能化中文搜索引擎搜索引擎平台平台 任务是: 构建适用于中文互联网的文本内容抽取系统及网页文本内容结构化分析 基于内容的多媒体信息检索 基于自然语言理解的查询分析 基于用户属性挖掘的个性化检索 http:/ DesignPlatform for Applying, Researching And Developing
29、Intelligent Search EngineServersServers ServersServersServersServersServersServersServersServersServersServersServersServersServersServers ServersServersServersServersServersBare Metal MachinesAutomationData nodesTianwang jobs and evaluation jobsPARADISE索引设计介绍当前设计中的基本功能 Using faster single-pass inde
30、xing Highly compressed index disk data structures Various compress algorithm(*) Various invert index file format(*) index position ,freq value or impact value(*) Index field information,such as title,date Cache support(*)下一步设计的功能 Index various document format，such as word, pdf 使用MapReduce等技术的索引 多种切词
31、的实现与处理 增量索引与文档删除 Term vector存储 多segment的合并策略Inverted index Document-sorted index The pointers in each inverted list are stored in increasing document order Using d-gap Frequency-sorted index Inverted list are stored in decreasing term frequency score Impact-sorted index The pointers are ordered acco
32、rding to the impact value Impact value is a small integer representing the overall contribution of term t to the score of document d, include the factor used to normalize for document lengthProcessing query mode Document-at-a-time All inverted lists are simultaneously accessed |q|-way processing is
33、carried out to handle a query q of |q| terms Term-at-a-time Only on inverted list is accessed at any given time A sequence of |q|-1 binary operations are performed Not clear better than document-at-a-time processing Score-at-a-time All of the term lists are open for reading Processed in decreasing s
34、core contribution order rather than in increasing document number order Dynamic query pruningIndex levels Document numbers only Only support Boolean queries Document numbers and Score Score can be impact scores or frequent or both Support Boolean and ranked queries Document numbers, Score, Positions
35、 Support Boolean ,ranked, phrase (proximity queries)Types of index and support query modestypedsposOrganization Processing mode supportedDY-Document-sortTerm or docat-a-timeDSYY-Document-sortImpact or freq-sortTerm or docat-a-timeDSPYYYDocument-sortedTerm or doc-at-a-timescore-at-a-timeInterleaving
36、Pointer interleaving Each document number is immediately followed by the corresponding w or f value or pos value Term interleaving Keep various related parts of each inverted list in contiguous blocs Non-interleaving Using separate inverted file Each storing a particular type of information For dist
37、inct disk pointers maintained in each entry in the dictionaryBlock-interleaved indexes Each inverted list is built up as a sequence of one or more groups Within each group there are four or more k-blocksCache 是一个工具包，为一些模块提供cache功能 Cahce 策略与存储分开 有多种cahce策略 当前实现MRU策略 多种存储策略 基于STL map 采用模板实现，保证其通过性Docu
38、ment The logical representation of a Document for indexing and searching A Document is a collection of Fieldables A Fieldable is a logical representation of a users content that needs to be indexed or stored Fieldables have a number of properties that tell the index how to treat the content (like in
39、dexed, tokenized, stored, etc.)Compress 工具包，提供整形数字的解压缩 实现多种解压缩算法 采用工厂方法模式Analysis An analyzer builds TokenStreams, which analyze text It thus represents a policy for extracting index terms from text Typical implementations first build a Tokenizer, which breaks the stream of characters into raw Token
40、s One or more TokenFilters may then be applied to the output of the TokenizerPARADISE Implementationhttp:/ applicationPKU searchpdf literature search2008 Olympics searchmodulecrawlanalysis & indexsearchutilitycompressBuffer.thirdpartycmake,boost,zlib,tidy,openssl,berkeley dbdataTianwang Formatquery
41、logIPLocatortutorialCMake and Boost referenceBooks and papers courseInformation Retrieval Cloud Computing Distributed Systems Analysis and Index moduesmoduleRaw2Dpt, DptParseDocsanalysis and index sub modulesQuarkRecognizer cconv segtag html-purifier .Crawl ModuleCompress AlgorithmsSEWM2008中文Web信息检索
42、评测TEAMMacro-PrecisionMacro-RecallMacro-F1DLUT10.8888888888890.8695652173910.879120879121DLUT20.895522388060.8695652173910.882352941176SCU10.8461538461540.8768115942030.861209964413SCU20.8402777777780.8768115942030.858156028369SCUT10.8832116788320.8768115942030.88SCUT20.8897058823530.8768115942030.88
43、3211678832SCUT30.821192052980.8985507246380.858131487889SCUT40.7948717948720.8985507246380.843537414966SDU10.781250.9057971 014490.838926174497SDU20.7745664739880.9710144927540.861736334405RUC0.6701030927840.9420289855070.78313253012北京大学校内搜索2008 Olympics search目前关注研究点 网页去噪（相对成熟，改进较难） 网页文档真假性判断 索引压缩
44、信息检索的自动评测 倒排文档排序搜索引擎动态摘要算法 好的摘要应当做到不对用户产生误导，这种误导主要有两种情况： 原本与用户查询较相关的链接，用户阅读摘要后感觉不相关，从而忽略该链接。 原本与用户查询不相关的链接，用户阅读摘要后感觉相关，从而点击链接阅读原文。我们的算法 我们将“以查询为中心”解析为关键词出现“最多，最丰富”， 并且我们强调摘要段落完整性，我们认为一段话开头的完整性更为重要，必须从关键词开始向前延伸，以保证开头完整性。量化查询与摘要相关性3 分查询与摘要很相关，阅读摘要后决定打开链接或在摘要中已经发现查找内容2 分查询与摘要一定相关，阅读摘要后有打开链接的倾向1 分查询与摘要不太相关，不倾向打开链接0 分查询与摘要不相关，不会打开链接查询数： 30链接文档数：150有效链接： 149实验结果和数据放在：http:/ 本文算法公式（2）计算结果：0.973百度摘要公式（2）计算结果：1.033相比百度略优相比百度略优6%Q&A!
