선택한 단어 수는 입니다.
최소 단어 이상 선택하여야 합니다.
최소 단어 이상 선택하여야 합니다.
선택한 단어 수는 30입니다.
최대 10 단어까지만 선택 가능합니다.
최대 10 단어까지만 선택 가능합니다.
문제 정의
- 그러나 SHJ 알고리즘은 편중된(skewed) 공간 데이타에 대한 조인 연산 시 해쉬버킷의 빈번한 오버플로우가 발생하며 이를 처리하기 위해 버킷을 재분할해야 하므로 버킷 이용 효율이 감소되는 문제점을 가지고 있다. 따라서 이 논문에서는 SHJ 알고리즘의 문제점을 해결할 수 있는 Spatial Hash Strip Join(SHSJ) 알고리즘을 제안한다. 알고리즘의 기본 개념은 조인 연산 시 버킷 오버플로우를 허용하는 것을 전제로 하며, 해당 버킷의 조인 연산 단계에서 오버플로우가 발생한 버킷에 대해서는 SSSJ 알고리즘을 사용하고, 그렇지 않은 버킷에 대해서는 내부 메모리 plane-sweep 알고리즘을 사용하는 Spatial Hash Strip Join(SHSJ) 알고리즘을 적용한다.
- 본 절에서는 인덱스가 존재하지 않는 편중 데이타의조인 문제를 해결하기 위해 기존의 SHJ 알고리즘의 단점을 개선한 SHSJ 알고리즘을 제안한다. 그림 4는 SHJ 알고리즘을 사용한 두 입력 테이블의 버킷 분할과정을 도시한 것이다.
- 이 논문에서 실험 평가의 비교 대상 알고리즘으로는 SHJ와 SSSJ 알고리즘을 선택하였으며, 두 알고리즘 모두 인덱스가 존재하지 않는 입력 테이블의 조인 연산을 처리하기 위한 알고리즘이다.
- 이 논문에서는 인덱스가 존재하지 않는 두 입력 테이블에 대해 효율적인 공간 조인 연산을 수행할 수 있는 SHSJ 알고리즘을 제안하였다. 상이한 편중도를 갖는 입력 테이터에 대한 조인 연산시 빈번한 버킷 오버플로우 발생으로 인해 성능 저하를 초래하는 SHJ 알고리즘의 단점 보완에 SHSJ 알고리즘을 이용할 수 있다.
- 이와는 별도로 두 입력 테이블의 공간을 규칙적으로[11, 12] 혹은 불규칙적으로[1] 분할하고 분할의 결과로 정의된 버킷으로 객체를 할당하는 기법이 있다. 이 절에서는 이 논문에서 제안한 알고리즘의 관련 연구로서 SHJ 알고리즘과 SSSJ 알고리즘에 대해 기술한다.
제안 방법
- 2.1 절과 2.2절에서 입력 테이블에 인덱스가 존재하지 않을 경우 사용되는 조인 알고리즘을 기술하였다. SHJ 와 SSSJ 알고리즘은 인덱스가 존재하지 않는 대부분 경우 조인 연산 성능이 우수하다、하지만, 입력 데이타가 전체 데이타 영역 중 특정 지역에 편중되어 분포할 경우 기존 SHJ 알고리즘의 경우 잦은 버킷 분할이 요구되며 버킷 영역의 겹침(overlap) 영역이 증가 한다.
- 이때 초기 버킷 영역은 버킷의 중심점으로 정의되며 객체 삽입 시 그 영역의 갱신이 요구된다. 각 입력 객체의 버킷 할당 기준은 기존의 SHJ 알고리즘과 동일하지만 버킷 오버플로우가 발생할 경우 버킷 분할을 하지 않고 버킷 용량을 초과하여 입력되는 데이타를 연결 리스트를 사용하여 동일버킷 영역에 계속 삽입하는 방법을 사용한다.
- Nested Loop Join(INLJ)[6] 방법이다. 기본 개념은 인덱스가 존재하지 않는 테이블의 각 객체를 R-tree로 구성된 테이블에 대해 윈도우 질의를 수행하는 방법으로 처리한다. 또한 인덱스가 존재하지 않는 테이블에 대해 R나xee를 구성하는 Seeded-Tree Join (STJ) 알고리즘이 있다[7, 8].
- SSSJ 알고리즘의 초기 정렬 수행 후 조인 문제를 해결하기 위해 직접 plane-sweepe- 시도한다, RJ 알고리즘에서의 수직 분할 단계는 단지 plane-sweep 알고리즘의 수행에서 요구되는 sweeping 구조가 메인 메모리의 크기보다 클 경우에만 수행된다. 대안으로, 보증된 신뢰 범위를 갖는 데이타 집합의 겹침을 측정하기위해 랜덤 샘플링을 사용할 수 있고, 그 후 이 정보를 사용해서 입력에 대한 분할 여부를 결정하게 된다. 초기 정렬 후 sweeping 구조가 메인 메모리 적재가 가능하다고 가정하고 단순한 내부 plane-sweep 알고리즘을 시작한다.
- plane sweep 알고리즘은 조인을 위한 두 버킷이 메모리를 초과하면 처리가 불가능하므로 메모리를 초과한 버킷을 여러 strip으로 분할하여 plane sweep 알고리즘을 적용할 수 있도록 확장한 SSSJ 알고리즘을 사용한다. 따라서 본 논문에서는 기존 SHJ 알고리즘의 단점을 해결하기 위해서 SHJ 알고리즘의 버킷 분할이 요구될 경우 버킷 영역을 분할하지 않고 버킷 조인 단계에서 메모리 크기를 초과하는 버킷의 조인 시 2.2 절에서 기술한 SSSJ 알고리즘을 이용하여 처리하는 SHSJ 알고리즘을 제안하며 이 알고리즘의 설계 및 알고리즘은 다음 장에서 기술한다.
- 마지막으로, 버퍼 크기는 512, 1024, 2048 그리고 4096 bytes로 각각 다르게 주어지고 각 버퍼 크기에 대한 각 알고리즘의 조인 성능 특성을 분석한다. 입력 테이블의 크기와 편중도를 평가 항목으로 사용할 때 테이블의 크기에 대한 영향만을 고려하기 위하여 버퍼 크기는 512 bytes로 고정한다.
- 소요되는 총 수행 시간을 사용한다. 본 실험 평가에서 입력 데이타에 비해 메인 메모리의 크기가 너무 커서 모든 데이타가 메모리에 상주 가능하므로 동시에 메모리에 적재될 수 있는 데이타의 크기를 2M bytes 로제 한하였다.
- 하지만 버킷 재분할 방법은 편중 데이타의 경우 빈번한 버킷 오버플로우로 인해 오버헤드가 크다는 단점을 가지고 있다. 본 장에서는 이 문제를 효율적으로 처리할 수 있는 SHSJ 알고리즘을 설계한다.
- 알고리즘을 제안하였다. 상이한 편중도를 갖는 입력 테이터에 대한 조인 연산시 빈번한 버킷 오버플로우 발생으로 인해 성능 저하를 초래하는 SHJ 알고리즘의 단점 보완에 SHSJ 알고리즘을 이용할 수 있다. 기존 SHJ 알고리즘에서는 버킷 오버플로우 처리를 위해 버킷을 입출력 버퍼에 적재가 가능하도록 분할시키는 반면에 SHSJ 알고리즘은 버킷 오버플로우가 발생하면 버킷 영역을 분할하지 않고 기존 버킷 영역을 유지하면서 오버플로우가 발생한 공간 객체들을 연결 리스트를 사용하여 동일 영역의 버킷을 연결하여 처리하였다.
- 데이타를 사용하였다. 이 논문에서는 공간 질의 처리 단계 중 여과단계에 중점을 두었으므로 Tiger/ line 데이타의 도로와 수로에 대한 데이타를 추출한 후 이 데이타들을 MBR 객체로 변환하여 조인 연산에 이용한다. 표 1은 실험에서 사용할 Tiger/line 데이타 중에서 4개의 주에 대한 도로와 수로에 대한 MBR 객체수와 그 용량을 나타낸다.
- 입력 데이타 집합인 RI 주의 도로와 수로의 데이타에대해 표 2에서 정의한 것과 같이 버퍼 크기를 512, 1024, 2048, 4096 bytes로 변경하면서 SHJ, SSSJ와 SHSJ 알고리즘의 성능을 평가한다. 표 5는 버퍼 크기가 각각 다를 경우 동일한 데이타에 대한 조인 수행 결과 분할된 버킷의 수, 중복 저장된 객체의 수, 해쉬 테이블을 구성한 후 입력 데이타 집합에 대한 크기의 변화를 나타낸다.
- 입력 테이블의 크기는 표 1에 나타낸 것처럼 입력 데이타집합의 크기가 서로 다른 네 개 주의 객체 집합을 사용하여 평가한다. 입력 객체의 편중도 실험을 위해 표 1의 Rhode Island 주에 대한 데이타 집합을 Rhode Island 주 전체 영역 기준으로 8개의 동일한 공간으로 분할한다.
- 표 2와 같이 각 입력 테이블의 편중도를 각각 25%, 50%, 75% 그리고 90%의 비율로 주어지고, 버퍼는 512 bytes, 입력 데이타를 RI 주의 데이타를 사용하여 평가한다.
대상 데이터
- 본 실험은 Intel Xeon 550MHz CPU, 1GB RAM, 40GB 하드디스크의 Solaris 8 환경에서 수행하였으며 SHSJ 알고리즘의 구현을 위해 GNU C 컴파일러 (gilbc 2.95.3)를 사용하였다.
- 실험 데이타로는 표준 평가 데이타 중 하나인 Tiger/ line[15] 데이타를 사용하였으며, 이 가운데 Connecticut (CT), New Jersey(NJ), New York(NY) 그리고 Rhode Island(RI)이 4개 주에 대한 도로(roads)와 수로(hydro- graphic) 데이타를 사용하였다. 이 논문에서는 공간 질의 처리 단계 중 여과단계에 중점을 두었으므로 Tiger/ line 데이타의 도로와 수로에 대한 데이타를 추출한 후 이 데이타들을 MBR 객체로 변환하여 조인 연산에 이용한다.
데이터처리
- 본 절에서는 4.1 절의 실험 데이타로 SHJ, SSSJ와 SHSJ 알고리즘을 적용하여 조인 연산 결과를 바탕으로 각 알고리즘의 성능을 비교 분석한다.
이론/모형
- (4)는 Stepl과 2에서 생성된 두 해쉬 테이블에 대해 동일한 영역을 갖은 해쉬 버킷의 데이타를 버퍼 사이즈만큼 메인 메모리로 읽어 들인 후 plane-sweep 알고리즘을 사용하여 조인 연산을 수행한다. 이때 입력 테이블의 객체들에 대한 버킷 할당 과정에서 오버플로우가 발생하지 않는 버킷은 내부 메모리 plane-sweep 알고리즘을 사용하고 오버플로우가 발생한 버킷은 SSSJ 알고리즘을 사용하여 조인 연산을 수행한다.
- 이 문제점은 기존 SHJ 알고리즘의 버킷 조인 시 두 조인 버킷이 동시에 메모리에 상주 가능하여 내부 plane sweep 알고리즘을 사용하도록 제한하고 있기 때문이다. plane sweep 알고리즘은 조인을 위한 두 버킷이 메모리를 초과하면 처리가 불가능하므로 메모리를 초과한 버킷을 여러 strip으로 분할하여 plane sweep 알고리즘을 적용할 수 있도록 확장한 SSSJ 알고리즘을 사용한다. 따라서 본 논문에서는 기존 SHJ 알고리즘의 단점을 해결하기 위해서 SHJ 알고리즘의 버킷 분할이 요구될 경우 버킷 영역을 분할하지 않고 버킷 조인 단계에서 메모리 크기를 초과하는 버킷의 조인 시 2.
- 그림 4에서 보는 것처럼 두 입력 데이타 집합의 분포가 매우 상이하게 편중되어 있으므로 그림 4(a)에서와 같이 대부분의 데이타들이 좌측 상단에 분포하는 반면 그림 4(b)에서는 우측 하단에 집중되어 분포하고 있다. 그림 4에서 해쉬 버킷의 용량을 5로 정의 했을 때 두 번째데이타 집합을 버킷에 할당시 버킷 bB, 6는 오버플로우가 발생하며 이 문제를 해결하기 위한 기존 연구인 SHJ 알고리즘에서는 버킷 재분할 기법(bucket repartitioning method)을 사용한다. 먼저 그림 5는 그림 4(b) 에서 두 번째 테이블의 객체들을 버킷 할당 시 오버플로우가 발생한 버킷 b%을 나타내며, 숫자는 입력 데이타의 삽입순서이다.
- 기존 SHJ 알고리즘에서는 버킷 오버플로우 처리를 위해 버킷을 입출력 버퍼에 적재가 가능하도록 분할시키는 반면에 SHSJ 알고리즘은 버킷 오버플로우가 발생하면 버킷 영역을 분할하지 않고 기존 버킷 영역을 유지하면서 오버플로우가 발생한 공간 객체들을 연결 리스트를 사용하여 동일 영역의 버킷을 연결하여 처리하였다. 두 번째 입력 데이타 집합이 해쉬 버킷에 입력되면 동일한 영역을 갖는 해당 버킷 쌍에 대한 조인 연산을 위해 SSSJ 알고리즘을 사용했다.
- 입력 테이블의 크기와 편중도를 평가 항목으로 사용할 때 테이블의 크기에 대한 영향만을 고려하기 위하여 버퍼 크기는 512 bytes로 고정한다. 또한, 편중도에 대한 평가와 버퍼 크기에 대한 평가를 위해 RI 데이타를 사용한다.
- i (같은 영역을 갖는 버킷)의 부합에 의해 수행된다. 만약 한 버킷이 메모리에 적재가능하면 그 버킷을 메인메모리로 읽어오고 다른 한 버킷의 객체들은 적재된 객체에 대해 단일 스캔 방식으로 처리되며 이 방법은 I/O 비용을 최적화한다, 만약 조인을 위한 두 버킷의 객체가동 시에 메모리로 적재하여 조인 연산이 가능하면 조인성능이 우수한 plane-sweep 알고리즘[13]을 이용하거나, 한 버킷의 객체를 벌크 로드 R-treeH4]를 생성하여 INLJ 알고리즘을 사용하여 조인 연산을 수행한다.
- 이러한 단점을 개선하기 위해 SHSJ 알고리즘에서는 버킷 분할 단계에서 버킷 오버플로우 발생 시 버킷을 재분할하지 않고 동일 영역으로 삽입하는 방법을 사용한다. 버킷 조인 단계의 처리를 기존 SHJ 알고리즘과 유사하지만 버킷 용량을 초과하여 입력된 버킷의 조인 연산 시에는 Plane-sweep 알고리즘 대신 조인 연산 시 I/O 성능이 우수한 SSSJ 알고리즘을 사용한다. 따라서 기존 SHJ 알고리즘의 버킷 할당과정에서 버킷 분할 처리와 이로 인해 중복 저장되는 객체가 증가하는 문제점을 개선할 수 있다.
- 도시한 것이다. 버킷의 객체들을 메모리에 적재 가능한 4개의 스트립으로 분할하고 각 스트립에 대해 내부 plane-sweep 알고리즘을 사용하여 공간 조인 연산을 수행하는 전략을 사용한다.
- 따라서 이 논문에서는 SHJ 알고리즘의 문제점을 해결할 수 있는 Spatial Hash Strip Join(SHSJ) 알고리즘을 제안한다. 알고리즘의 기본 개념은 조인 연산 시 버킷 오버플로우를 허용하는 것을 전제로 하며, 해당 버킷의 조인 연산 단계에서 오버플로우가 발생한 버킷에 대해서는 SSSJ 알고리즘을 사용하고, 그렇지 않은 버킷에 대해서는 내부 메모리 plane-sweep 알고리즘을 사용하는 Spatial Hash Strip Join(SHSJ) 알고리즘을 적용한다. SHSJ 알고리즘과 기존 SHJ 알고리즘의 성능을 비교 평가하기 위해서 실세계 데이타를 사용하여 실험하였으며, 평가 항목으로는 입력 데이타 집합의 크기, 데이타의 편중도 및 조인 연산 시 사용되는 버퍼 크기이며 두 알고리즘의 성능 평가 요소로는 조인 연산 시 요구되는 디스크 페이지의 접근 횟수와 조인 연산의 총 수행 시간을 사용한다’
- 그림 9에서 (1)은 첫 번째 입력 테이블에 대한 초기해쉬 버킷 영역을 정의하고 (2)는 각 입력 객체를 버킷 영역과 할당 기준에 따라 하나의 해쉬 버킷에 삽입하는 과정이다. 이 단계에서 초기 해쉬 버킷 영역을 정의하기 위해 기존의 SHJ 알고리즘에서 사용했던 bootstrap seedingtl] 방법을 사용한다. 이때 초기 버킷 영역은 버킷의 중심점으로 정의되며 객체 삽입 시 그 영역의 갱신이 요구된다.
- 사용하여 조인 연산을 수행한다. 이때 입력 테이블의 객체들에 대한 버킷 할당 과정에서 오버플로우가 발생하지 않는 버킷은 내부 메모리 plane-sweep 알고리즘을 사용하고 오버플로우가 발생한 버킷은 SSSJ 알고리즘을 사용하여 조인 연산을 수행한다. (5)에서는 (4) 의 결과로 얻어진 객체의 MBR 쌍 중에서 중복되는 결과 쌍을 제거하는 단계이다 이 과정이 필요한 이유는 Step3에서 두 번째 입력 테이블의 객체 할당 시 겹침이 발생한 모든 버킷으로 할당하였으므로 처리 결과인 MBR 쌍들은 중복이 발생할 수 있으며 중복된 MBR 쌍은 질의 처리 결과에서 원하는 값이 아니므로 중복객체 쌍을 제거하는 과정이 요구되기 때문이다.
성능/효과
- SSSJ의 경우 스트립 분할 시 여러 스트립에 포함되는 객체가 증가하므로 위와 같은 결과가 나온다. 그러나 SHSJ 알고리즘의 경우 편중도가 높을 경우 버킷 오버플로우가 발생하더라도 버킷을 분할 처리하지 않기 때문에 디스크 접근 횟수의 증가율이 작으며 편중비율이 높을수록 SHJ와 SSSJ 알고리즘 보다 디스크 접근 횟수가 감소됨을 알 수 있다.
- SHJ 알고리즘의 경우 표 5에서와 같이 버퍼 크기가 작을수록 분할이 발생하는 버킷이 급격히 증가하게 되므로 중복 저장되는 객체의 수는 버퍼가 512 bytes인 경우 4096 bytes일 경우보다 약 70% 정도 증가한 반면 SHSJ 알고리즘의 경우 증가폭이 훨씬 작다. 그림 14는 버퍼 크기에 대한 조인 수행 시간을 나타내며, 버퍼 크기가 작을 경우, 빈번한 버킷 오버플로우가 요구되는 SHJ 알고리즘보다 SHSJ 알고리즘이 효율적인 성능을 갖는 반면, 버퍼의 크기가 4096 bytes로 클 경우에는 SHJ 알고리즘도 버킷 분할이 요구되는 수가 적으므로 SHJ와 SHSJ 알고리즘은 유사한 조인 성능을 갖는다 반면, SSSJ 알고리즘의 경우 버퍼 크기가 클수록 우수한 성능을 나타내면 특히, 버퍼 크기가 2048, 4096 bytes인 경우 SHSJ 알고리즘 보다 성능이 우수하다.
- 버킷 조인 단계의 처리를 기존 SHJ 알고리즘과 유사하지만 버킷 용량을 초과하여 입력된 버킷의 조인 연산 시에는 Plane-sweep 알고리즘 대신 조인 연산 시 I/O 성능이 우수한 SSSJ 알고리즘을 사용한다. 따라서 기존 SHJ 알고리즘의 버킷 할당과정에서 버킷 분할 처리와 이로 인해 중복 저장되는 객체가 증가하는 문제점을 개선할 수 있다.
- 그러나 버퍼 크기가 입력 데이타 집합의 크기보다 충분히 클 , 경우는 기존 SHJ 알고리즘과 유사한 성능을 갖는다. 또한 입력 데이타 크기가 버퍼에 비해 작을 경우 SSSJ 알고리즘이 SHSJ 보다 성능이 우수했으며 버퍼 크기가 큰 경우 SHSJ와 SSSJ 알고리즘은 유사한 성능을 나타내었다. 따라서 이 논문에서 제안한 SHSJ 알고리즘은 공간 객체들의 영역이 편중되어 있거나 인덱스가 존재하지 않는 입력 테이블로 구성된 GIS 어플리케이션에서의 공간 질의에 효율적으로 이용될 수 있을 것이다.
- 실험 결과로서 SHSJ 알고리즘은 기존 SHJ와 SSSJ 알고리즘에 비해 입력 데이타 집합의 크기가 클수록, 그리고 조인 연산 수행에 소요되는 버퍼의 크기가 작을수록 높은 성능을 나타냈다. 그러나 버퍼 크기가 입력 데이타 집합의 크기보다 충분히 클 , 경우는 기존 SHJ 알고리즘과 유사한 성능을 갖는다.
후속연구
- 또한 입력 데이타 크기가 버퍼에 비해 작을 경우 SSSJ 알고리즘이 SHSJ 보다 성능이 우수했으며 버퍼 크기가 큰 경우 SHSJ와 SSSJ 알고리즘은 유사한 성능을 나타내었다. 따라서 이 논문에서 제안한 SHSJ 알고리즘은 공간 객체들의 영역이 편중되어 있거나 인덱스가 존재하지 않는 입력 테이블로 구성된 GIS 어플리케이션에서의 공간 질의에 효율적으로 이용될 수 있을 것이다.
- 향후 연구 과제로는 SHSJ 알고리즘과 기존 PBSM, seeded-tree 알고리즘 각각에 대한 성능 비교와 더불어 입력 테이블에 인덱스가 존재할 경우 기존 RJ 알고리즘과의 성능 분석이 필요하다.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.