해시 테이블을 이용한 레벨 셋 데이터의 효율적인 저장과 검색 (Efficient Store and Search of Level Set Data using Hash Table)

서지정보

· 발행기관 : 대한전자공학회
· 수록지 정보 : 전자공학회논문지 / 55권 / 8호 / 41 ~ 51페이지
· 저자명 : 정승한, 권오봉

초록

레벨 셋 메소드 기반의 반도체 식각 모사와 같은 대량의 데이터를 처리하는 분야에서 데이터를 저장하는데 해시 테이블과 같은 자료구조의 사용은 시간복잡도와 공간복잡도를 줄인다. 본 논문에서는 대량의 데이터를 사용하는 레벨 셋 메소드 전산모사에서 레벨 셋의 효율적인 저장과 빠른 접근을 목적으로 해시 테이블을 구성하기 위한 실험에 관하여 논한다. 고속 레벨 셋 메소드의 하나인 좁은 영역 레벨셋 메소드(Narrow Band Level Set method)는 좁은 영역에서만 레벨 셋을 계산하는 방법이다. 본 논문에서는 좁은 영역(Narrow Band)을 설정하고 이 영역의 레벨 셋을 해시 테이블에 초기화하고 검색, 연산, 저장하는 과정에서 필요로 하는 메모리양과 처리시간을 측정하는 실험을 하였다. 레벨 셋 메소드 처리가 해시 테이블의 탐색에 미치는 영향을 파악하기 위하여 해당 노드와 주위 노드의 합 연산을 하여 레벨 셋 메소드 연산을 모사했다. 로드 팩터를 이용한 해시 테이블 사이즈, 그리드 해상도를 변수로 하여 처리 시간, 메모리 사용량, 빈 슬롯의 개수 등을 측정하여 해시의 성능을 관찰하였다. 로드 팩터가 0.2~1 사이일 때 처리시간은 해시 테이블의 사이즈 변화에 크게 영향을 받지 않지만, 로드 팩터가 약 1.5이상부터는 해시 테이블의 저장 공간이 부족해짐으로써 처리시간이 증가하였다. 로드팩터를 감소시키면 메모리의 사용이 증가하고 처리시간이 감소하나 임계영역이 있어 어느 한계이상에서는 로드팩터를 감소시켜도 처리시간이 감소하지 않았다. 메모리의 사용량은 중간부분인 로드 팩터 약 0.5~2 사이에서 그 사용량이 최소가 되는 곳을 발견 할 수 있었다.

영어초록

The use of data structure such as hash table to store data in a large amount of data processing applications like semiconductor etching simulations based on level set methods, can reduce time complexity and spatial complexity. In this paper, we discuss an experiments for constructing a hash table for the efficient storage and quick access of level set in level set method. Narrow Band Level Set method, which is one of the fast level set methods, is a method of calculating a level set only in a narrow area In this paper, we set up Narrow Band, initialize the level set of this area into a hash table, and measure the amount of memory and processing time required in searching, calculating, and storing them. In order to examine the effect of the hash table, the level set method operation is simulated by summing a node value and the values of the surrounding nodes of it. The hash table performance was observed by measuring the hash processing time, the amount of memory usage, the number of empty slots by varying the load factor. The change in processing time when the load factor is between 0.2 and 1 is not greatly affected by the change in the size of the hash table. However, when the load factor is about 1.5 or more, the storage space becomes insufficient in the hash table, thereby increasing the processing time. As the load factor decreases, the amount of the used memory increase and the processing time decrease. But the saturation point exists, so if we decrease the load factor more than this point, the processing time does not decrease any more. The minimum amount of memory is between load factor about 0.5~2.

참고자료

· 없음