Supervised machine learning algorithms normally work by preprocessing a training dataset and outputting a compact model (e.g. a bunch of regression coefficients) that can quickly give an approximate answer for a new input. At that point, the original dataset can be discarded - the model serves as a proxy for it.
I'm curious about what are algorithms called that also give approximate answers for new inputs, but have access to the entire training dataset on each query? E.g. one obvious algorithm in this class is nearest neighbor search: scan the training dataset, find the most similar point(s) to the query, return (a weighted average of) their outputs.
I'm not so much concerned about the complexity, I just want to know about this problem space from a theoretical standpoint:
- What is this class of algorithms called?
- What are some other interesting algorithms in this family?
- Can they be better in quality (even if much slower) than traditional machine learning models?