k-NN: for each query, find k nearest training points; predict the majority class.
Simple but powerful baseline. No training phase — but every query searches all training points (O(n) per query without index). Vector databases solve this with ANN indexes.