2008 | OriginalPaper | Buchkapitel
Fast Private Norm Estimation and Heavy Hitters
verfasst von : Joe Kilian, André Madeira, Martin J. Strauss, Xuan Zheng
Erschienen in: Theory of Cryptography
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
We consider the problems of computing the Euclidean norm of the difference of two vectors and, as an application, computing the large components (Heavy Hitters) in the difference. We provide protocols that are approximate but private in the semi-honest model and efficient in terms of time and communication in the vector length
N
. We provide the following, which can serve as building blocks to other protocols:
Euclidean norm problem:
we give a protocol with quasi-linear local computation and polylogarithmic communication in
N
leaking only the true value of the norm. For processing massive datasets, the intended application, where
N
is typically huge, our improvement over a recent result with quadratic runtime is significant.
Heavy Hitters problem:
suppose, for a prescribed
B
, we want the
B
largest components in the difference vector. We give a protocol with quasi-linear local computation and polylogarithmic communication leaking only the set of true
B
largest components and the Euclidean norm of the difference vector. We justify the leakage as (1) desirable, since it gives a measure of goodness of approximation; or (2) inevitable, since we show that there are contexts where linear communication is required for approximating the Heavy Hitters.