Experimental Evaluation of Succinct Representations of JSON Documents

Abstract

현대 컴퓨터 시스템에서 생성되는 대용량의 데이터는 처리에 있어서 큰 문제가 되고 있다. 이 데이터는 직간접적으로 JSON, XML과 같은 플랫폼에 무관한 데 이터 교환 언어를 통해 저장된다. 본 논문은 메인 메모리에 적재된 파일의 RAM 사용량을 줄이고, 디스크에 저장된 데이터의 압축을 가능케 하는 JSON 문서의 간결한 표현 방식을 탐색하는 데 주안점을 두었다. 본 논문에서 제안하는 표현 방식은 JSON 문서가 구조 부분과 내용 부분으로 분리 가능하다는 아이디어에 기반을 두고 있다. 이 방법은 통상적으로 사용되는 포인터 방식의 구현이 아닌, 간 결한 트리 구조를 통하여 문서의 구조를 표현한다. 더불어 남은 데이터는 속성과 값의 배열 형태로 재배치된다. 속성들은 연속적인 배열에 중복된 항목들이 제거된 후 순차적으로 저장되며, 값들은 비트열로 인덱싱된 이종 배열로 표현된다. 구조와 내용을 분리하는 것은 간결한 트리의 노드와 그것이 표현하는 라벨-값 쌍을 직접적 으로 연결하는 것을 가능케 하여 포인터의 사용을 생략할 수 있게 한다. 이 방식은 C++ 언어를 이용하여 SJSON이라는 이름으로 구현되었다. 본 논문에서는 이 방 식과 널리 사용되는 JSON 분석기들을 여러 척도를 기준으로 비교하였으며, 이 방식에 대한 개선점을 언급한다. 실험 결과를 통해 본 연구에서 구현한 SJSON이 대중적으로 사용되는 라이브러리에 비해 최대 98%(임의로 생성된 데이터) 혹은 82%(실제 데이터) 적은 RAM 공간을 차지한다는 것을 보인다. 더불어 SJSON은 원본 문서에 비해 61%(임의로 생성된 데이터) 혹은 41%(실제 데이터) 적은 디스 크 용량을 사용하여 문서를 저장한다. 본 논문을 통해 구현된 JSON 분석 및 압축 라이브러리는 오픈소스화되어 온라인으로 공개되었다.

The massive amounts of data processed in modern computational systems is becoming a problem of increasing importance. This data is commonly stored directly or indirectly through the use of data exchange languages, such as JSON (JavaScript Object Notation) and XML (eXtensible Markup Language), for human-readable platform agnostic access. This thesis focuses on exploring succinct representations of JSON docu- ments as a means of achieving reduced RAM usage of files in main memory, and of permitting the compression of data files stored in disk. The representa- tions we propose are mainly based on the idea that JSON documents, as most data exchange formats, can be deconstructed into structure and raw data. In our method we represent the tree-like structure of the document with succinct trees, as opposed to the usual pointer-based implementation. Furthermore, the re- maining raw data is reorganized into arrays of attributes and values. Attributes are stripped of redundancies and stored sequentially in a simple contiguous ar- ray, while values are represented through a bit string indexed heterogeneous array. This deconstruction between structure and data allows for a straighforward connection between a node in the succinct tree and its corresponding label-value pair, dispensing pointers altogether. The scheme here proposed is implemented as the SJSON library in C++, and then evaluated with respect to a number of metrics comparing its per- formance with popular alternative JSON parsers. Future improvements to the representation are then presented. Empirical results show that SJSON is able to represent JSON files in main memory with up to 98% less space in RAM than popular libraries in synthetic datasets, and up to 82% in real world cor- pora. Moreover, SJSON reduces stored file sizes by up to 61% compared to the original document in synthetic datasets, and up to 41% in real world corpora. The succinct JSON parser and compression library developed in this thesis is open source and available online.