  This paper identifies that a group of state-of-the-art
locally-differentially-private (LDP) algorithms for frequency estimation are
equivalent to the private Count-Mean Sketch (CMS) algorithm with different
parameters. Therefore, we revisit the private CMS, correct errors in the
original CMS paper regarding expectation and variance, modify the CMS
implementation to eliminate existing bias, and explore optimized parameters for
CMS to achieve optimality in reducing the worst-case mean squared error (MSE),
$l_1$ loss, and $l_2$ loss. Additionally, we prove that pairwise-independent
hashing is sufficient for CMS, reducing its communication cost to the logarithm
of the cardinality of all possible values (i.e., a dictionary). As a result,
the aforementioned optimized CMS is proven theoretically and empirically to be
the only algorithm optimized for reducing the worst-case MSE, $l_1$ loss, and
$l_2$ loss when dealing with a very large dictionary. Furthermore, we
demonstrate that randomness is necessary to ensure the correctness of CMS, and
the communication cost of CMS, though low, is unavoidable despite the
randomness being public or private.
