In their paper Scalable Recognition with a Vocabulary Tree, Nister and Stewenius mention that after an offline training stage, new images can be inserted on-the-ﬂy into the database. However, at the end of the training stage the IDF is computed and normalized. My question is, how would you incrementally update such a database composed of inverted document frequencies?
Ok, apparently, it is not much different from an update of the mean, given the accumulated statistics (mode statistics). Basically, when the mean and the number of elements are known, the idf weights can be re-computed whenever a new element is inserted. This can be achieved in two ways:
- Allocate your tree with the maximum number of features. Keep all the elements inserted. Whenever a new insert occurs, re-compute TF-IDF over the entire set.
- Only keep the statistics which are required to update the weights. This way, an entire pass over the data is not necessary.
Normalization is again performed over the entire dataset once the idf is updated. Removal is not much different from the insertion, but one needs to use a suitable pointer-wise data structure if it is desired to have the computational complexity both for insertion and deletion.