Recommend tags for documents I'm working on a unusual issue (for me) and I need some advice.

My goal is to have a recommendation algorithm that propose tags for a document, based on all the previously tagged documents. For example, if I upload each month an invoice from "stackoverflow", and I apply each time the same tags ("stackoverflow" and "invoice" for instance), the algorithm should recognize the document as similar to previous stackoverflow invoices and suggest the same tags to the user.

I was thinking about extracting some features of the document ( text, sender's email...), compare the similarity with previous documents and suggest the tags of the most similar documents.

The tags are user-defined, and thus not a finite set, so the algorithm should learn continuously. This is my issue, because I will have to store all the documents in a database and evaluating the similarity between a new document and all the previous ones will eventually be very expensive as the number of documents in my database grow.

On the other side, incremental learning algorithms can learn continuously without a massive database, but don't support an non-finite set of output classes.

So, as I see it, I have 2 options :


massive database with all documents, and evaluating similarity
between a new document and each document in the database : not very
scalable, possibly time-expensive
re-train from scratch a classification algorithm every time a new document is uploaded : I will still have a massive database, but training can be done in the background. This is the best of the 2 options, but I'm wondering if there could be a better way.


Any advice about more appropriate algorithm would be greatly appreciated. If it matters, I work with Python.
This is where Word Embedding play an amazing role. If you want to solve the problem you have at hand with Natural Language Processing approach, what you can do is learn vector representations for these documents and store them with the labels i.e tags for that text. 

You can then use the similarity of vector representations between documents, to predict the tags. 

This way, your computation is not intensive at all and you can keep retraining as and when you get more data.