Inverted Index

Description of this Post

Slide 1

1 Outline

Slide 2

2 Outline

Slide 3

3 Full indexing architecture

Slide 4

4 Web graph

Slide 5

5 Forward index

Slide 6

6 Page attribute file

Slide 7

7 Page attribute file

Slide 8

8 Inverted index

Slide 9

9 Outline

Slide 10

10 Inverted index

Slide 11

11 Example

Slide 12

12 Document identifiers

Slide 13

13 Frequencies

Slide 14

14 Positions

Slide 15

15 Full inverted index

Slide 16

16 Summary

Slide 17

17 Outline

Slide 18

18 Simple indexer

Slide 19

19 What are the problems with this simple indexer?

Slide 20

20 Two-pass index

Slide 21

21 One-pass index with merging

Slide 22

22 Aardvark

Slide 23

23 Distributed indexing (MapReduce)

Slide 24

24 Summary

Slide 25

25 Outline

Slide 26

26 No merge

Slide 27

27 Incremental update

Slide 28

28 Immediate merge (in-memory)

Slide 29

29 Lazy merge

Slide 30

30 Page deletions

Slide 31

31 Summary

Slide 32

32 Summary

Slide 33

33 Additional References

Slide 34