【ADS】Inverted File Index

发表于 | 分类于 ， | | 阅读次数: 
1
2
3
4
5
6
7
8
9
while ( read a document D ) {
    while ( read a term T in D ) {
        if ( Find( Dictionary, T ) == false )
            Insert( Dictionary, T );
        Get T’s posting list;
        Insert a node to T’s posting list;
    }
}
Write the inverted index to disk;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
BlockCnt = 0; 
while ( read a document D ) {
  while ( read a term T in D ) {
    if ( out of memory ) {
      Write BlockIndex[BlockCnt] to disk;
      BlockCnt ++;
      FreeMemory;
    }
    if ( Find( Dictionary, T ) == false )
      Insert( Dictionary, T );
    Get T’s posting list;
    Insert a node to T’s posting list;
  }
}
for ( i=0; i<BlockCnt; i++ )
  Merge( InvertedIndex, BlockIndex[i] );


Distributed Index

  • Term-partitioned

  • Document-partitioned index

Measures for a Search Engine

  • How fast does it index
  • How fast does it search
  • Expressiveness of query language

Data Retrieval Performance Evaluation (after establishing correctness)

  • Response time
  • Index space

Information Retrieval Performance Evaluation

  • How relevant is the answer set?


Relevant Irrelevant
Retrieved $R_R$ $I_R$
Not Retrieved $R_N$ $I_N$

Precision: $P=R_R/(R_R+I_R)$

Recall: $R=R_R/(R_R+R_N)$

Exercises

ex1


Reference

https://blog.csdn.net/Woolseyyy/article/details/51559937