Before revision:    Our first result achieves near-linear space and optimal query time  , and our second result achieves linear space and near optimal query time .
After revision:  Our first result achieves near-linear space and optimal query time , and our second result achieves linear space and query time O(m+k^{1+\epsilon .