Succinct 표현은 n개의 이산 객체를 O(n) 비트만을 사용하여 저장하는 공간 효율적인 방법으로, 일반적으로 succinct 표현은 이산 객체에 접근하기 위해 비트 스트링에 대한 효율적인 rank와 select 함수를 필요로 한다. 현재 다양한 연구들에 의해 1차원 비트 스트링의 rank와 select 함수는 o(n) 비트의 보조 자료 공간을 사용하여 O(1) 시간에 수행되고, 실용적인 구현이 가능하다. 반면에, 2차원 비트 행렬에 대한 연구는 아직 초기단계이다. 본 논문에서는 2차원 비트 행렬 상에서의 rank 및 select 함수를 새롭게 정의하고 처음으로 o($n^2$) 비트만을 사용하여 O(logn) 시간에 rank 질의를, 그리고 O($log^2n$) 시간에 select 질의를 수행할 수 있는 방법을 제안한다.
Succinct representation is a space-efficient method to represent n discrete objects using O(n) bits. Generally, in order to access the discrete objects, succinct representation requires efficient rank and select functions for a bit-string. By various researches, both rank and select functions for a one-dimensional bit-string take O(1) time with o(n) bits of extra space, and practical implementations have also been proposed. However, little effort has been made on rank and select functions for a two-dimensional bit-matrix. In this paper, we newly define rank and select functions for a two-dimensional bit-matrix and propose the first algorithm that takes O(logn) time and O($log^2n$) time for rank and select functions, respectively, with o($n^2$) bits of extra space.
