  We give the first $\tilde{O}(\frac{1}{\sqrt{T}})$-error online algorithm for
reconstructing noisy statistical databases, where $T$ is the number of (online)
sample queries received. The algorithm, which requires only $O(\log T)$ memory,
aims to learn a hidden database-vector $w^{*} \in \mathbb{R}^{D}$ in order to
accurately answer a stream of queries regarding the hidden database, which
arrive in an online fashion from some unknown distribution $\mathcal{D}$. We
assume the distribution $\mathcal{D}$ is defined on the neighborhood of a
low-dimensional manifold. The presented algorithm runs in $O(dD)$-time per
query, where $d$ is the dimensionality of the query-space. Contrary to the
classical setting, there is no separate training set that is used by the
algorithm to learn the database --- the stream on which the algorithm will be
evaluated must also be used to learn the database-vector. The algorithm only
has access to a binary oracle $\mathcal{O}$ that answers whether a particular
linear function of the database-vector plus random noise is larger than a
threshold, which is specified by the algorithm. We note that we allow for a
significant $O(D)$ amount of noise to be added while other works focused on the
low noise $o(\sqrt{D})$-setting. For a stream of $T$ queries our algorithm
achieves an average error $\tilde{O}(\frac{1}{\sqrt{T}})$ by filtering out
random noise, adapting threshold values given to the oracle based on its
previous answers and, as a consequence, recovering with high precision a
projection of a database-vector $w^{*}$ onto the manifold defining the
query-space.
