Index for efficient argmax(w.x) query ~ 20d
The query is called a 'top-k' query, and you can answer it quickly using the ranking cube approach. http://www1.se.cuhk.edu.hk/~hcheng/paper/vldb06_rankcube.pdf

The paper does not derive the time complexity.