ITPE * JackerLab

개요Count-min Sketch는 데이터 스트림에서 요소의 출현 빈도를 공간 효율적으로 추정할 수 있는 확률적 데이터 구조입니다. 특히 실시간 로그 분석, 트래픽 모니터링, 키워드 카운팅과 같은 빅데이터 환경에서 메모리 사용을 최소화하면서 근사적인 카운팅 결과를 빠르게 제공합니다.1. 개념 및 정의**Count-min Sketch(CMS)**는 여러 개의 해시 함수와 이중 배열 구조를 활용해 각 항목의 빈도를 추정하는 구조입니다. 오류가 허용되는 대신, 메모리 효율과 속도를 극대화한 것이 특징입니다.설계자: Cormode & Muthukrishnan (2005)자료구조 구성: d × w 크기의 카운터 배열 + d개의 해시 함수입력 모델: 데이터 스트림 환경 (insert-only or turnstile..

개요Cuckoo Filter는 Bloom Filter의 한계를 극복하기 위해 개발된 확률적 자료구조로, 빠른 멤버십 쿼리, 낮은 False Positive 확률, 그리고 효율적인 삭제(delete) 연산을 지원합니다. 인서트 실패 확률을 낮추면서도 메모리 사용량과 성능을 최적화하여, 데이터베이스, 네트워킹, 캐싱 시스템 등 다양한 분야에서 널리 활용되고 있습니다.1. 개념 및 정의 항목 내용 정의해시 기반 버킷에 작은 지문(fingerprint)을 저장하여 멤버십 쿼리 및 삭제를 지원하는 공간 효율적 확률적 자료구조목적빠르고 공간 절약적인 멤버십 테스트와 삭제 지원필요성Bloom Filter의 삭제 불가성과 False Positive 문제를 개선Cuckoo Filter는 특히 삭제와 동적 크기 조정이 ..

개요Bloom Filter는 주어진 요소가 집합에 속하는지를 빠르고 공간 효율적으로 검사할 수 있는 확률적 자료구조입니다. 일부 허위 긍정(False Positive)은 허용하지만, 허위 부정(False Negative)은 발생하지 않는 특성을 가지며, 대규모 데이터셋에서 빠른 membership query(멤버십 검사)가 필요한 다양한 분야(검색 엔진, 네트워크 라우팅, 데이터베이스 캐시 등)에서 널리 사용됩니다.1. 개념 및 정의 항목 내용 정의비트 배열과 다수의 해시 함수를 이용해 집합 멤버십을 테스트하는 공간 효율적 확률적 자료구조목적빠르고 적은 메모리 사용으로 존재 여부 검사필요성초대규모 데이터셋에 대해 공간-시간 복잡도 최적화 필요Bloom Filter는 메모리 제약이 큰 환경에서도 고속 검..