InformationRetrievalandMap-ReduceImplementations.ppt

Scalability Bottleneck Initial implementation: terms as keys, postings as values Reducers must buffer all postings associated with key (to sort) What if we run out of memory to buffer postings? Uh oh! [2,4] [9] [1,8,22] [23] [8,41] [2,9,76] [2,4] [9] [1,8,22] [23] [8,41] [2,9,76] 2 1 3 1 2 3 Another Try… 1 fish 9 21 (values) (key) 34 35 80 1 fish 9 21 (values) (keys) 34 35 80 fish fish fish fish fish How is this different? Let the framework do the sorting Term frequency implicitly stored Directly write postings to disk! Where have we seen this before? 2 1 3 1 2 3 2 1 3 1 2 3 Postings Encoding 1 fish 9 21 34 35 80 … 1 fish 8 12 13 1 45 … Conceptually: In Practice: Don’t encode docnos, encode gaps (or d-gaps) But it’s not obvious that this save space… Overview of Index Compression Byte-aligned vs. bit-aligned VarInt Group VarInt Simple-9 Non-parameterized bit-aligned Unary codes ? codes ? codes Parameterized bit-aligned Golomb codes (local Bernoulli model) Want more detail? Read Managing Gigabytes by Witten, Moffat, and Bell! Unary Codes x ? 1 is coded as x-1 one bits, followed by 1 zero bit 3 = 110 4 = 1110 Great for small numbers… horrible for large numbers Overly-biased for very small gaps Watch out! Slightly different definitions in different textbooks ? codes x ? 1 is coded in two parts: length and offset Start with binary encoded, remove highest-order bit = offset Length is number of binary digits, encoded in unary code Concatenate length + offset codes Example: 9 in binary is 1001 Offset = 001 Length = 4, in unary code = 1110 ? code = 1110:001 Analysis Offset = ?log x? Length = ?log x? +1 Total = 2 ?log x? +1 ? codes Similar to ? codes, except that length is encoded in ? code Example: 9 in binary is 1001 Offset = 001 Length = 4, in ? code = 11000 ? code = 11000:001 ? codes = more compact for smaller numbers? codes = more compact for larger numbers Golomb Codes x ? 1, parameter b: q + 1 in unary, where q = ?( x - 1 ) / b? r in binary, where r = x - qb