대용량 텍스트 파일을 위한 분산 토큰 기반의 고속 정렬 알고리즘

Abstract

오늘날 정보화 시대에 이르러 매일 방대한 데이터가 누적되고 있다. 가정, 산업, 사회 전반에 걸쳐 하루에도 엄청난 새로운 데이터가 생성된다. 우리는 그러한 데이터들을 저장하고 검색하고 백업을 한다. 그 중 점점 더 중요해지고 있는 것이 원하는 정보를 찾는 검색 기능이라 하겠다. 이러한 검색 기능을 원활히 수행하기 위해서는 그 이전에 대용량 텍스트 파일(Huge Text File)의 정렬(Sorting) 및 인덱싱(Indexing)이 선행되어야 한다. 그러나 저용량의 텍스트 기반 파일의 경우 정렬하는 데에 큰 문제가 없으나 대용량 텍스트 기반 파일의 경우 정렬과 인덱싱에 많은 시간과 메모리가 필요하게 된다. 이미 우리는 많은 정렬 알고리즘을 알고 있다. 대표적으로 삽입, 버블, 선택, 퀵, 힙, 합병 정렬 등등이 있다. 하지만 이런 알고리즘들은 소량의 데이터를 정렬하는 데 유용할 수는 있으나 대용량 텍스트 기반 파일을 정렬하기에는 속도와 메모리 부족 현상에 직면하게 된다. 이 논문에서는 대용량 텍스트 기반 파일을 정렬함에 있어서 기존 정렬 알고리즘보다 훨씬 성능이 우수한 새롭고 창의적인 알고리즘을 제시하고자 한다. 본 논문에서 새롭게 제시할 알고리즘은 분산토큰링크드리스트 (DistributedTokenLinkedList)이다. 이것은 글자 하나가 노드(Node)의 단위가 된다. 차일드노드(ChildNode), 형제노드(SibilingNode), 데이터노드(DataNode)의 총 3개 타입 노드를 가진다. 차일드노드는 부모, 자식 관계를 가지며 형제노드는 이웃하는 노드와 동등한 관계를 가지며 데이터노드는 문자열의 오프셋(Offset) 정보를 저장하는 역할을 한다. 최종 정렬 데이터를 만드는 방법은 Root 노드로부터 시작하여 재귀적(Recursively)으로 모든 노드를 탐색(Trace)하면서 파일에 문자열을 씀(Write) 으로써 정렬된 데이터를 만들 수 있다. 본 논문에서 소개하고자 하는 분산토큰링크드리스트는 토큰링크드리스트 개념에 분산 개념을 접목한 것으로 대용량 텍스트 기반 파일을 부분적으로 읽은 후 정렬 파일을 여러 개 만든다. 그리고 최종적으로 여러 개의 파일을 하나의 파일로 병합(Merge)함으로써 메모리 한계에 봉착하지 않고 고속으로 대용량 텍스트 기반 파일을 정렬할 수 있다. 마지막으로 본 논문에서는 연구 배경과 정렬의 종류를 살펴보고 토큰링크드리스트와 메모리 한계를 극복한 분산토큰링크드리스트를 소개한다. 그리고 성능 평가와 결과 및 향후 과제를 살펴보고 논문을 마치고자 한다.

주제어 : 대용량 텍스트 파일, 정렬, 인덱싱, 분산, 토큰, 링크드리스트, 분산토큰링크드리스트