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 data structure uses space in n\cdot O\left({\epsilon^{-1}}\right)^{k} + O(nm) and has query time in O\left(k\right).