# Dynamic Bag of Words / Features

I'm trying to implement a Bag of Features for a set of images submitted in different moments by a set of users.

If the clusters change, then we need to recompute at LEAST all the "visual words" which elements has changed cluster.

For example, suppose that one SIFT descriptor d at time t1 belongs to cluster A. At t1+1 a query is submitted, and so the clusters change and now d belongs to cluster B. So we need to re-compute the "visual word" (vector) relative to d.

As you can imagine, this approach can be too much expensive (especially if query rate is high)!

My question is: there is a better model than the classic bag of words, or some dynamic clustering algorithm?

A "partially" dynamic solution:

A possible improvement could be dividing the application in two processes: one buffer the queries and at a certain point update the system (launching k-means and recomputing all the "visual words) while the other answer to the queries (keeping the static BoW). When the buffer process has finished the update it update the query process. But still, this solution is "partially" dynamic, since the "visual dictionary" will not updated (so while the buffer process is still buffering queries).

• I think you are describing an online (or an incremental) learning algorithm. With BoW, usually the vocabulary is calculated once and all the test instances are encoded accordingly. If you want to update the model with all queries, one approach could be to buffer them in a database, and update the vocabulary at a scheduled time (preferrably at night time where the workload is minimum). But you also need to be careful about "pranksters". imagine a user that constantly queries a plain white image. It might not be the worst thing in the world, but still might end up in more harm than good.
– jeff
May 29 '16 at 15:39
• @HalilPazarlamaI I was afraid that this was the only solution. Look at A "partially" dynamic solution: section May 29 '16 at 15:48
• Oh yes, if you want to update the vocabulary with each query, you will have to handle the consequences :) In both speed and accuracy, because since the k-means clustering you are using is probably non-deterministic at some stage, updating the vocabulary with each image might not be very desirable, it might even make the system worse in some cases. So maybe after you update with the buffer (of 1 or more images), you might want to check if the update actually improved the performance or not.
– jeff
May 29 '16 at 19:23