Before revision:  Our data structure uses space in n\cdot O\left({\epsilon^{-1}}\right)^{k} + O(nm) and  query time in O\left(k\right).
After revision:  Our first data structure achieves a (5+\epsilon) approximation factor, uses space in n\cdot O\left({\epsilon^{-1}}\right)^{k} + O(nm) and query time in O\left(k\right).