Introduction BSBI algorithm SPIMI algorithm Distributed indexing Dynamic indexing PV211: Introduction to Information Retrieval https://www.fi.muni.cz/~sojka/PV211 IIR 4: Index construction Handout version Petr Sojka, Hinrich Schütze et al. Faculty of Informatics, Masaryk University, Brno Center for Information and Language Processing, University of Munich 2023-03-01 (compiled on 2023-02-15 09:08:54) Sojka, IIR Group: PV211: Index construction 1 / 47 Introduction BSBI algorithm SPIMI algorithm Distributed indexing Dynamic indexing Overview 1 Introduction 2 BSBI algorithm 3 SPIMI algorithm 4 Distributed indexing 5 Dynamic indexing Sojka, IIR Group: PV211: Index construction 2 / 47 Introduction BSBI algorithm SPIMI algorithm Distributed indexing Dynamic indexing Take-away Two index construction algorithms: BSBI (simple) and SPIMI (more realistic) Distributed index construction: MapReduce Dynamic index construction: how to keep the index up-to-date as the collection changes Sojka, IIR Group: PV211: Index construction 3 / 47 Introduction BSBI algorithm SPIMI algorithm Distributed indexing Dynamic indexing Hardware basics Many design decisions in information retrieval are based on hardware constraints. We begin by reviewing hardware basics that we’ll need in this course. Sojka, IIR Group: PV211: Index construction 5 / 47 Introduction BSBI algorithm SPIMI algorithm Distributed indexing Dynamic indexing Hardware basics Access to data is much faster in memory than on disk. (roughly a factor of 10 SSD, 100+ for rotational disks) Disk seeks are “idle” time: No data is transferred from disk while the disk head is being positioned. To optimize transfer time from disk to memory: one large chunk is faster than many small chunks. Disk I/O is block-based: Reading and writing of entire blocks (as opposed to smaller chunks). Block sizes: 8KB to 256 KB Assuming an efficient decompression algorithm, the total time of reading and then decompressing compressed data is usually less than reading uncompressed data. Servers used in IR systems typically have many GBs of main memory and TBs of disk space. Fault tolerance is expensive: It’s cheaper to use many regular machines than one fault tolerant machine. Sojka, IIR Group: PV211: Index construction 6 / 47 Introduction BSBI algorithm SPIMI algorithm Distributed indexing Dynamic indexing Some stats (ca. 2008) symbol statistic value s average seek time 5 ms = 5 × 10−3 s b transfer time per byte 0.02 µs = 2 × 10−8 s processor’s clock rate 109 s−1 p lowlevel operation (e.g., compare & swap a word) 0.01 µs = 10−8 s size of main memory several GB size of disk space 1 TB or more Sojka, IIR Group: PV211: Index construction 7 / 47 Introduction BSBI algorithm SPIMI algorithm Distributed indexing Dynamic indexing RCV1 collection Shakespeare’s collected works are not large enough for demonstrating many of the points in this course. As an example for applying scalable index construction algorithms, we will use the Reuters RCV1 collection. English newswire articles sent over the wire in 1995 and 1996 (one year). Sojka, IIR Group: PV211: Index construction 8 / 47 Introduction BSBI algorithm SPIMI algorithm Distributed indexing Dynamic indexing A Reuters RCV1 document Sojka, IIR Group: PV211: Index construction 9 / 47 Introduction BSBI algorithm SPIMI algorithm Distributed indexing Dynamic indexing Reuters RCV1 statistics N documents 800,000 L tokens per document 200 M terms (= word types) 400,000 bytes per token (incl. spaces/punct.) 6 bytes per token (without spaces/punct.) 4.5 bytes per term (= word type) 7.5 T non-positional postings 100,000,000 Exercise: Average frequency of a term (how many tokens)? 4.5 bytes per word token vs. 7.5 bytes per word type: why the difference? How many positional postings? Sojka, IIR Group: PV211: Index construction 10 / 47 Introduction BSBI algorithm SPIMI algorithm Distributed indexing Dynamic indexing Goal: construct the inverted index Brutus −→ 1 2 4 11 31 45 173 174 Caesar −→ 1 2 4 5 6 16 57 132 . . . Calpurnia −→ 2 31 54 101 ... dictionary postings Sojka, IIR Group: PV211: Index construction 12 / 47 Introduction BSBI algorithm SPIMI algorithm Distributed indexing Dynamic indexing Index construction in IIR 1: Sort postings in memory term docID I 1 did 1 enact 1 julius 1 caesar 1 I 1 was 1 killed 1 i’ 1 the 1 capitol 1 brutus 1 killed 1 me 1 so 2 let 2 it 2 be 2 with 2 caesar 2 the 2 noble 2 brutus 2 hath 2 told 2 you 2 caesar 2 was 2 ambitious 2 =⇒ term docID ambitious 2 be 2 brutus 1 brutus 2 capitol 1 caesar 1 caesar 2 caesar 2 did 1 enact 1 hath 1 I 1 I 1 i’ 1 it 2 julius 1 killed 1 killed 1 let 2 me 1 noble 2 so 2 the 1 the 2 told 2 you 2 was 1 was 2 with 2 Sojka, IIR Group: PV211: Index construction 13 / 47 Introduction BSBI algorithm SPIMI algorithm Distributed indexing Dynamic indexing Scaling index construction How can we construct an index for very large collections? Taking into account the hardware constraints we just learned about . . . . . . memory, disk, speed, etc. Sojka, IIR Group: PV211: Index construction 14 / 47 Introduction BSBI algorithm SPIMI algorithm Distributed indexing Dynamic indexing Sort-based index construction As we build index, we parse docs one at a time. The final postings for any term are incomplete until the end. Can we keep all postings in memory and then do the sort in-memory at the end? No, not for large collections Thus: We need to store intermediate results on disk. Sojka, IIR Group: PV211: Index construction 15 / 47 Introduction BSBI algorithm SPIMI algorithm Distributed indexing Dynamic indexing Same algorithm for disk? Can we use the same index construction algorithm for larger collections, but by using disk instead of memory? No: Sorting very large sets of records on disk is too slow – too many disk seeks. We need an external sorting algorithm. Sojka, IIR Group: PV211: Index construction 16 / 47 Introduction BSBI algorithm SPIMI algorithm Distributed indexing Dynamic indexing “External” sorting algorithm (using few disk seeks) We must sort T = 100,000,000 non-positional postings. Each posting has size 12 bytes (4+4+4: termID, docID, term frequency). Define a block to consist of 10,000,000 such postings We can easily fit that many postings into memory. We will have 10 such blocks for RCV1. Basic idea of algorithm: For each block: (i) accumulate postings, (ii) sort in memory, (iii) write to disk Then merge the blocks into one long sorted order. Sojka, IIR Group: PV211: Index construction 17 / 47 Introduction BSBI algorithm SPIMI algorithm Distributed indexing Dynamic indexing Merging two blocks Block 1 brutus d3 caesar d4 noble d3 with d4 Block 2 brutus d2 caesar d1 julius d1 killed d2 postings to be merged brutus d2 brutus d3 caesar d1 caesar d4 julius d1 killed d2 noble d3 with d4 merged postings disk Sojka, IIR Group: PV211: Index construction 18 / 47 Introduction BSBI algorithm SPIMI algorithm Distributed indexing Dynamic indexing Blocked Sort-Based Indexing BSBIndexConstruction() 1 n ← 0 2 while (all documents have not been processed) 3 do n ← n + 1 4 block ← ParseNextBlock() 5 BSBI-Invert(block) 6 WriteBlockToDisk(block, fn) 7 MergeBlocks(f1, . . . , fn; f merged) Sojka, IIR Group: PV211: Index construction 19 / 47 Introduction BSBI algorithm SPIMI algorithm Distributed indexing Dynamic indexing Problem with sort-based algorithm Our assumption was: we can keep the dictionary in memory. We need the dictionary (which grows 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.) Sojka, IIR Group: PV211: Index construction 21 / 47 Introduction BSBI algorithm SPIMI algorithm Distributed indexing Dynamic indexing Single-pass in-memory indexing Abbreviation: SPIMI Key idea 1: Generate separate dictionaries for each block – no need to maintain term-termID mapping across blocks. Key idea 2: Don’t 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 indexes can then be merged into one big index. Sojka, IIR Group: PV211: Index construction 22 / 47 Introduction BSBI algorithm SPIMI algorithm Distributed indexing Dynamic indexing SPIMI-Invert SPIMI-Invert(token_stream) 1 output_file ← NewFile() 2 dictionary ← NewHash() 3 while (free memory available) 4 do token ← next(token_stream) 5 if term(token) /∈ dictionary 6 then postings_list ← AddToDictionary(dictionary,term(token)) 7 else postings_list ← GetPostingsList(dictionary,term(token)) 8 if full(postings_list) 9 then postings_list ← DoublePostingsList(dictionary,term(token) 10 AddToPostingsList(postings_list,docID(token)) 11 sorted_terms ← SortTerms(dictionary) 12 WriteBlockToDisk(sorted_terms,dictionary,output_file) 13 return output_file Merging of blocks is analogous to BSBI. Sojka, IIR Group: PV211: Index construction 23 / 47 Introduction BSBI algorithm SPIMI algorithm Distributed indexing Dynamic indexing SPIMI: Compression Compression makes SPIMI even more efficient. Compression of terms Compression of postings See next lecture Sojka, IIR Group: PV211: Index construction 24 / 47 Introduction BSBI algorithm SPIMI algorithm Distributed indexing Dynamic indexing Distributed indexing For web-scale indexing (don’t try this at home!): must use a distributed computer cluster Individual machines are fault-prone. Can unpredictably slow down or fail. How do we exploit such a pool of machines? Sojka, IIR Group: PV211: Index construction 26 / 47 Introduction BSBI algorithm SPIMI algorithm Distributed indexing Dynamic indexing Google data centers (2007 estimates; Gartner) Google data centers mainly contain commodity machines. Data centers are distributed all over the world. 1 million servers, 3 million processors/cores Google installs 100,000 servers each quarter. Based on expenditures of 200–250 million dollars per year This would be 10% of the computing capacity of the world! If in a non-fault-tolerant system with 1000 nodes, each node has 99.9% uptime, what is the uptime of the system (assuming it does not tolerate failures)? Answer: 37% Suppose a server will fail after 3 years. For an installation of 1 million servers, what is the interval between machine failures? Answer: less than two minutes Sojka, IIR Group: PV211: Index construction 27 / 47 Introduction BSBI algorithm SPIMI algorithm Distributed indexing Dynamic indexing 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. Sojka, IIR Group: PV211: Index construction 28 / 47 Introduction BSBI algorithm SPIMI algorithm Distributed indexing Dynamic indexing Parallel tasks We will define two sets of parallel tasks and deploy two types of machines to solve them: Parsers Inverters Break the input document collection into splits (corresponding to blocks in BSBI/SPIMI) Each split is a subset of documents. Sojka, IIR Group: PV211: Index construction 29 / 47 Introduction BSBI algorithm SPIMI algorithm Distributed indexing Dynamic indexing Parsers Master assigns a split to an idle parser machine. Parser reads a document at a time and emits (termID,docID)-pairs. Parser writes pairs into j term-partitions. Each for a range of terms’ first letters E.g., a–f, g–p, q–z (here: j = 3) Sojka, IIR Group: PV211: Index construction 30 / 47 Introduction BSBI algorithm SPIMI algorithm Distributed indexing Dynamic indexing Inverters An inverter collects all (termID,docID) pairs (= postings) for one term-partition (e.g., for a–f). Sorts and writes to postings lists Sojka, IIR Group: PV211: Index construction 31 / 47 Introduction BSBI algorithm SPIMI algorithm Distributed indexing Dynamic indexing Data flow masterassign map phase reduce phase assign parser splits parser parser inverter postings inverter inverter a-f g-p q-z a-f g-p q-z a-f g-p q-z a-f segment files g-p q-z Sojka, IIR Group: PV211: Index construction 32 / 47 Introduction BSBI algorithm SPIMI algorithm Distributed indexing Dynamic indexing MapReduce The index construction algorithm we just described is an instance of MapReduce. MapReduce is a robust and conceptually simple framework for distributed computing . . . . . . without having to write code for the distribution part. The Google indexing system (ca. 2002) consisted of a number of phases, each implemented in MapReduce. Index construction was just one phase. Another phase: transform term-partitioned into document-partitioned index. Sojka, IIR Group: PV211: Index construction 33 / 47 Introduction BSBI algorithm SPIMI algorithm Distributed indexing Dynamic indexing Index construction in MapReduce Schema of map and reduce functions map: input → list(k, v) reduce: (k,list(v)) → output Instantiation of the schema for index construction map: web collection → list(termID, docID) reduce: ( termID1, list(docID) , termID2, list(docID) , . . . ) → (postings_list1, postings_list2, . . . ) Example for index construction map: d2 : C died. d1 : C came, C c’ed. → ( C, d2 , died,d2 , C,d1 , came,d1 , C,d1 , c’ed,d1 ) reduce: ( C,(d2,d1,d1) , died,(d2) , came,(d1) , c’ed,(d1) ) → ( C,(d1:2,d2:1) , died,(d2:1) , came,(d1:1) , c’ed,(d1:1) ) Sojka, IIR Group: PV211: Index construction 34 / 47 Introduction BSBI algorithm SPIMI algorithm Distributed indexing Dynamic indexing Exercise What information does the task description contain that the master gives to a parser? What information does the parser report back to the master upon completion of the task? What information does the task description contain that the master gives to an inverter? What information does the inverter report back to the master upon completion of the task? Sojka, IIR Group: PV211: Index construction 35 / 47 Introduction BSBI algorithm SPIMI algorithm Distributed indexing Dynamic indexing Dynamic indexing Up to now, we have assumed that collections are static. They rarely are: Documents are inserted, deleted and modified. This means that the dictionary and postings lists have to be dynamically modified. Sojka, IIR Group: PV211: Index construction 37 / 47 Introduction BSBI algorithm SPIMI algorithm Distributed indexing Dynamic indexing Dynamic indexing: Simplest approach Maintain big main index on disk New docs go into small auxiliary index in memory. Search across both, merge results Periodically, merge auxiliary index into big index Deletions: Invalidation bit-vector for deleted docs Filter docs returned by index using this bit-vector Sojka, IIR Group: PV211: Index construction 38 / 47 Introduction BSBI algorithm SPIMI algorithm Distributed indexing Dynamic indexing Issue with auxiliary and main index Frequent merges Poor search performance during index merge Sojka, IIR Group: PV211: Index construction 39 / 47 Introduction BSBI algorithm SPIMI algorithm Distributed indexing Dynamic indexing Logarithmic merge Logarithmic merging amortizes the cost of merging indexes over time. → Users see smaller effect on response times. Maintain a series of indexes, each twice as large as the previous one. Keep smallest (Z0) in memory Larger ones (I0, I1, . . . ) on disk If Z0 gets too big (> n), write to disk as I0 . . . or merge with I0 (if I0 already exists) and write merger to I1, etc. Sojka, IIR Group: PV211: Index construction 40 / 47 Introduction BSBI algorithm SPIMI algorithm Distributed indexing Dynamic indexing LMergeAddToken(indexes, Z0, token) 1 Z0 ← Merge(Z0, {token}) 2 if |Z0| = n 3 then for i ← 0 to ∞ 4 do if Ii ∈ indexes 5 then Zi+1 ← Merge(Ii , Zi ) 6 (Zi+1 is a temporary index on disk.) 7 indexes ← indexes − {Ii } 8 else Ii ← Zi (Zi becomes the permanent index Ii .) 9 indexes ← indexes ∪ {Ii } 10 Break 11 Z0 ← ∅ LogarithmicMerge() 1 Z0 ← ∅ (Z0 is the in-memory index.) 2 indexes ← ∅ 3 while true 4 do LMergeAddToken(indexes, Z0, getNextToken()) Sojka, IIR Group: PV211: Index construction 41 / 47 Introduction BSBI algorithm SPIMI algorithm Distributed indexing Dynamic indexing Binary numbers: I3I2I1I0 = 23 22 21 20 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 Sojka, IIR Group: PV211: Index construction 42 / 47 Introduction BSBI algorithm SPIMI algorithm Distributed indexing Dynamic indexing Logarithmic merge Number of indexes bounded by O(log T) (T is total number of postings read so far) So query processing requires the merging of O(log T) indexes Time complexity of index construction is O(T log T). . . . because each of T postings is merged O(log T) times. Auxiliary index: index construction time is O(T2) as each posting is touched in each merge. Suppose auxiliary index has size a a + 2a + 3a + 4a + . . . + na = an(n+1) 2 = O(n2 ) So logarithmic merging is an order of magnitude more efficient. Sojka, IIR Group: PV211: Index construction 43 / 47 Introduction BSBI algorithm SPIMI algorithm Distributed indexing Dynamic indexing Dynamic indexing at large search engines Often a combination Frequent incremental changes Rotation of large parts of the index that can then be swapped in Occasional complete rebuild (becomes harder with increasing size – not clear if Google can do a complete rebuild) Sojka, IIR Group: PV211: Index construction 44 / 47 Introduction BSBI algorithm SPIMI algorithm Distributed indexing Dynamic indexing Building positional indexes Basically the same problem except that the intermediate data structures are large. Sojka, IIR Group: PV211: Index construction 45 / 47 Introduction BSBI algorithm SPIMI algorithm Distributed indexing Dynamic indexing Take-away Two index construction algorithms: BSBI (simple) and SPIMI (more realistic) Distributed index construction: MapReduce Dynamic index construction: how to keep the index up-to-date as the collection changes Sojka, IIR Group: PV211: Index construction 46 / 47 Introduction BSBI algorithm SPIMI algorithm Distributed indexing Dynamic indexing Resources Chapter 4 of IIR Resources at https://www.fi.muni.cz/~sojka/PV211/ and http://cislmu.org, materials in MU IS and FI MU library Original publication on MapReduce by Dean and Ghemawat (2004) Original publication on SPIMI by Heinz and Zobel (2003) YouTube video: Google data centers Sojka, IIR Group: PV211: Index construction 47 / 47