# $k$th element in data stream

In the streaming model how can i find the $$k$$th element (not $$k$$th most frequent) with erorr of at most $$\pm \epsilon$$ s.t. we return index $$i$$ that $$(1-\epsilon)k \leq i \leq (1+\epsilon)k$$ using the minimum memory required?
for eample, when $$k=\frac{1}{2}$$ we get the median.

• I'm not sure why your post was multiple-downvoted. Ideally downvoters would leave feedback on either improving the question or why they think it's a better fit on another site... – usul Feb 12 at 5:05