  In this work, we propose an efficient two-stage algorithm solving a joint
problem of correlation detection and partial alignment recovery between two
Gaussian databases. Correlation detection is a hypothesis testing problem;
under the null hypothesis, the databases are independent, and under the
alternate hypothesis, they are correlated, under an unknown row permutation. We
develop bounds on the type-I and type-II error probabilities, and show that the
analyzed detector performs better than a recently proposed detector, at least
for some specific parameter choices. Since the proposed detector relies on a
statistic, which is a sum of dependent indicator random variables, then in
order to bound the type-I probability of error, we develop a novel
graph-theoretic technique for bounding the $k$-th order moments of such
statistics. When the databases are accepted as correlated, the algorithm also
recovers some partial alignment between the given databases. We also propose
two more algorithms: (i) One more algorithm for partial alignment recovery,
whose reliability and computational complexity are both higher than those of
the first proposed algorithm. (ii) An algorithm for full alignment recovery,
which has a reduced amount of calculations and a not much lower error
probability, when compared to the optimal recovery procedure.
