Incremental Online Update of Tf-IDF Indices for Image Retrieval
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.