Practical Encodings for Range Top-2 Queries and Compressed RAM

Abstract

In this thesis, we design various compressed/succinct data structures. Also, we implemented our data structures from the practical view and conducted experiments to evaluate data structures. Experimental results show that our data structures are time- and space-efficient. Also, our data structures show simpler substructures that enable software engineers to utilize and maintain easily. In this thesis, we consider the following two problems: (1) range Top-2 encodings, and (2) dynamic compressed strings supporting access and update operations. Given an array of elements from a total ordering, a Top-2 query returns the first and second largest elements within a given query range. The Top-2 encoding problem encodes a given input array to support Top-2 queries efficiently. In the dynamic compressed string problem, we would like to maintain a string in compressed form while supporting access and update operations efficiently. For the Top-2 encoding problem, we designed two approaches. The first implementation is based on an alternative representation of Davoodi et al.'s data structure, which supports queries efficiently. Our data structure not only gives improved practical space and time efficiency, but also gives simpler substructures compared to Davoodi et al.'s data structure, which uses tree-covering. The other implementation is based on an RT2Q encoding on a 2 × n array. Our data structure uses less construction time while being competitive in terms of space. For the second problem, we designed two implementations based on the compressed RAM of Jansson et al., and Grossi et al., respectively. For this problem, we designed a data structure that is simpler than the data structures. Also, since our substructures are simpler to implement, we have room for further optimization. Experimental results show that our data structure supports operations efficiently while keeping the space proportional to the entropy of the input.

본 논문에서는 다양한 공간 효율적인 자료구조에 대해 다룬다. 또한, 본 논문에서는 이 자료구조들을 실용적 관점에서 구현하고 실험을 통해 그 성능을 평가하였다. 본 논문에서 제안하는 자료구조는 우수한 공간과 시간 효율성에 더해서, 동일한 이론적 성능을 보여주며 더 간단한 보조 자료구조를 갖는다. 간단한 보조 자료구조는 소프트웨어 엔지니어들이 지속적인 유지보수를 수행할 수 있도록 도와준다. 본 논문은 다음 두 가지 문제를 고려한다. (1) 구간 Top-2 인코딩, (2) 접근, 변경 연산을 지원하는 동적 문자열. 순서를 갖는 원소들로 이루어진 배열에서, Top-2 질의는 주어진 질의 범위 안에서 첫 번째와 두 번째 원소를 반환한다. 또한, Top-2 인코딩 문제는 Top-2 질의를 효율적으로 지원하기 위해 주어진 배열을 인코딩하는 문제이다. 동적 압축 문자열 문제는 문자열을 압축된 상태로 유지하면서, 접근 연산과 변경 연산을 효율적으로 지원하는 문제이다. 구간 Top-2 질의 문제를 위해서, 본 논문은 두 가지 실용적 구현을 제안한다. 첫 번째 구현은 구간 Top-2 질의에 대해 효율적으로 답변하는 Davoodi. et. al.의 자료구조에 기반을 둔다. 본 논문에서는 Davoodi. et. al.의 자료구조를 변형하여 Davoodi. et. al.의 자료구조와 거의 동일한 이론적 성능을 가지며 더 단순한 보조 자료구조를 가지는 구현을 제안하였다. 또한, 해당 자료구조 구현은 개선된 공간과 시간 효율성을 보여준다. 본 논문의 다른 구현은 2 x n 행렬에서의 Top-2 인코딩에 기반을 둔다. 해당 자료구조 구현은 개선된 인코딩 시간과 비슷한 공간 효율성을 보여준다. 동적 압축 문자열 문제를 위해서, 본 논문은 두 가지 실용적 구현을 제안한다. 각각의 구현은 Jansson et al.의 Compressed RAM 연구와 Grossi et al.의 연구에 기반을 둔다. 이 문제에서, 본 논문은 이전 연구들보다 더 간단한 자료구조를 제안한다. 또한, 본 논문의 자료구조가 가지는 구현의 용이성은, 최적화의 여지를 더 많이 가지게 한다. 실험 결과는 본 논문의 자료구조가 입력 문자열의 엔트로피에 비례하는 공간 사용을 유지하면서, 효율적인 연산을 지원하는 것을 보여준다.