On the amortized complexity of approximate counting

https://arxiv.org/abs/2211.03917

On the amortized complexity of approximate counting

(상각 복잡도 근사 계산)

Abstract

값 n까지의 카운터를 단순히 저장하는 것은 Ω(log n)비트의 메모리가 필요. Nelson과 Yu [NY22]는 Morris의 연구 [Mor78]를 따라, 쿼리 응답이 (1+ϵ)-근사값이며 확률적으로 최소 1-δ를 만족한다면 O(log(logn)+log(log(1/δ)+log(1/ϵ))비트만이 필요하며, 사실 이 경계는 최적이다. Morris의 원래 연구 동기와 현대 응용 프로그램은 하나의 카운터를 유지하는 것뿐만 아니라 k개의 카운터를 유지해야한다. 이로 인해 다음 질문이 생긴다. k개의 카운터를 유지하면서 개별 카운터의 비용보다 작은 비용으로 메모리를 사용할 수 있을까?, 즉, 이 문제는 개선된 상각 공간 복잡도 경계에서 어떤 이점이 있을까?

우리는 이 질문에 부정적으로 대답한다. 구체적으로, 우리는 거의 모든 파라미터 범위에 대해 하한 값을 증명하여, 여러 카운터를 저장할 때 메모리 사용량 면에서 상각을 통한 접근은 가능하지 않음을 보입니다. 우리의 주요 증명은 Braverman, Garg, Woodruff [BGW20]가 최근 소개한 "information cost" 이라는 특정 개념을 사용하여 스트리밍 알고리즘의 하한 값을 증명한다.

최소 비용 오메가 최적화 방식을 만족하는 k개의 카운터를 찾아 최적화 분석