비트맵 인코딩 (압축)

비트맵 인코딩(영어: Bitmap encoding)은 데이터 압축 기법 가운데 하나로, 주어진 데이터에서 특정 값의 존재 여부를 비트 벡터(bitmap)로 표현하는 방식이다. 주로 0과 같이 반복되는 값이 많거나, 데이터가 희소(sparse)한 경우에 효율적이다.

개요

• 비트맵 인코딩은 값들의 위치 정보를 비트열로 표시하여 원본 데이터를 재현할 수 있도록 한다.
• 각 원소가 특정 값에 해당하면 1, 그렇지 않으면 0을 기록한다.
• 데이터의 실제 값 배열(values)과 비트맵 배열(bitmap indices)을 함께 저장하여 전체 데이터를 압축 표현한다.

예시: 원본 데이터: [0, 3, 0, 1, 0, 0, 2, 3, 0, 0]

• Values: [3, 1, 2, 3]
• Bitmap: [0, 1, 0, 1, 0, 0, 1, 1, 0, 0]

특징

• 단순한 구조로 인코딩 및 디코딩 속도가 빠름
• 데이터의 희소성이 높을수록 압축 효율이 좋아짐
• 범주형 데이터 인덱싱이나 희소 행렬 표현에 적합

장점

• 비트 연산을 통한 빠른 검색과 집합 연산 가능
• 인코딩 과정이 단순하고 계산 비용이 낮음
• 압축된 데이터에서 직접 연산 수행 가능

단점

• 희소율이 낮을 경우(즉, 0이 적을 경우) 저장 효율이 떨어질 수 있음
• 비트맵 자체가 길이가 데이터 전체 크기와 같으므로, 극단적으로 희소한 경우에는 다른 압축 기법(CSR, 런렝스 인코딩 등)이 더 효율적

응용

• 데이터베이스 인덱싱
• 희소 데이터 저장 및 검색
• 데이터 웨어하우스에서 다차원 속성 질의 최적화
• 머신러닝에서 텐서 및 행렬 압축

같이 보기

• 런렝스 인코딩
• 희소 행렬
• 데이터 압축
• 비트맵 인코딩 (인공지능)

참고 문헌

• Patrick O’Neil, Dallan Quass. Improved Query Performance with Variant Indexes. Proceedings of ACM SIGMOD, 1997.
• Surajit Chaudhuri, Umeshwar Dayal. An Overview of Data Warehousing and OLAP Technology. ACM SIGMOD Record, 1997.