선택한 단어 수는 입니다.
최소 단어 이상 선택하여야 합니다.
최소 단어 이상 선택하여야 합니다.
선택한 단어 수는 30입니다.
최대 10 단어까지만 선택 가능합니다.
최대 10 단어까지만 선택 가능합니다.
문제 정의
- 또한 보다 향상된 I/O의 병렬성을 획득하는 범위질의 알고리즘을 고안하고 이를 K-최근접 질의에 적용하여 기존의 K-최근접 질의와 실험을 통해 비교한다. 마지막으로 제안하는 병렬 고차원 색인구조른최근 중요한 저장시스템으로 부각되고 있는 SAN 환경 메 어떯게 적용시킬 수 있는지에 대해 기술한다.
- 이 논문에서는 NOW니- SAN과 같은 병렽 환경에서 I/O의 병릴성괴- CPU 연산의 병렬성을 효과적으로 이용하는 병렬 고차원 색인 구조를 제안한디., 제안하는 병렬색인구조는 하나외 컴퓨터가 여러 디스크로부터 I/O의 병렬성을 취하고 다시 착각의 컴퓨터는 상호 협동작업을 동해 질의를 병렬로 처리하는 nP-nXmD 형태의 구조를 갖게 된다.
- 이 논문에서는 병렬환경의 장점을 최대한 이움하는병렬 고차원 색인 구조를 설계하고 이에 대한 성능 폄가를 수행하였다. 제안한 병릴 고차원 색인 구조에서 각 서버는 디스크 .
제안 방법
- 병렬 고차원 색인 구조를 제안한디., 제안하는 병렬색인구조는 하나외 컴퓨터가 여러 디스크로부터 I/O의 병렬성을 취하고 다시 착각의 컴퓨터는 상호 협동작업을 동해 질의를 병렬로 처리하는 nP-nXmD 형태의 구조를 갖게 된다. 또한 보다 향상된 I/O의 병렬성을 획득하는 범위질의 알고리즘을 고안하고 이를 K-최근접 질의에 적용하여 기존의 K-최근접 질의와 실험을 통해 비교한다.
- 트리에서는 범위질의와 최근접 질의에 대해서 세안하는 방법에서는 범위절의와 3개의 최근집 질의 방멉 모두에 대해서 디스크 접근수와 응답시간을 측 성하였다. MR-트리가 제안된 논분에서는 K-최근접 질의에 대한 언급은 없었지만 이 논문에서 실혐을 위해 기꼰적인 K-최근접 짚의틀 구현하여 실험하였다. 그 열과 MR- 트리나 제안하는 방법 모두 실데이타로 측정한 결과가 균등분포 데이타로 측.
- [22] 메서 제안한 벙렬 R-트리는 디스크 I/O의 병릴 성을 이용해 지리정보 시스템, 캐드 등의 응용에서 가상일반적인 질의 형태인 버위 질의의 성능개선을 시도했다. 다중 디스크를 시용하는 이유는 병렬 I/O를 통해 전제적인 VO 시간을 줄이고 또한 데이타의 양이 많아져 하나 외 뎌스;크메 저장하지 못하는 경우 이를 나누이 저장하려는 목적을 갖는다, [22]에서는 구성 가능한 병릴 R-트리의 구성방법으로 독립 R-트리, 수패노드, 멀티플렉스 R-토리 형태로 구분하고 실험을 통해 껄터플렉스 R-드리가 독립 R-트리나 수퍼노드보다 월등히 앞서는 것을 보며준다.
- 데이타는 10픈!개의 균동분포와 9차윈의 실데이타, 서버 수는 3, 더스크 수는 3, 6, 13토 하고 차원은 균쯩분포에 데해서는 1480차원까지 측정하고 실데이타는 9차원으로 고정하고 성능평가를 수행하였다 ;.림 37에서 그림 29까지는 균듷분포 테어하에 대해서 응답시간콰 디스크 접근 수를 측정한 것이다.
- 질의 처리 시 범위 질의 방법은 여러 노도의 병렬 입출력을 수행하는 방법을 제안한다. 그리고 K-회 근접 실위 방범은 긱- 서버에서 K-최근접 질의를 수행하는 방법과, 범위 질외의 병릴성을 이용하여 K-최근접질의의 성능을 향상시키기 위한 방법을 제안했다. 실험 결과 두 번쩨와 세 번째 방법이 첫 번째 방법보다 좋은 성능을 나타내는 것을 볼 수 있었다.
- 십여년 동한 매우 활발히 진행되었다. 기존에 제안된 고차원 색인 구조들을 분류해로변 TV-트리, X-토리, SS-트리, SR-트리, CIR-트리와 깉은 데이타 분할을 사용하는 색인 구조와 KDB-트리, hB-트리, LSDh-트리. BANG 화일, GRID 화임과 같이 곰깐분할을 사용하는 색인 구조들로 크게 니수어 볼 수 있다.
- 그리고 제안하는 방법이 기존의 병렬 다차원 색인구조보다 우수하다는 것을 보여주기 위해서 MR-트리와 비교하였다. 다른 병렬 색인구조가 많이 있지만 MR-트리가 비교적 최근에 제안되었으며 높은 성능을 얻을 수 있는 nP-nD형태인 점을 고려하여 선택하였다.
- 데이타는 10만개의 균등분포 네이타, 차원수는 20, 서버의 수는 3, 디스수는 15로 하고 페이지 크기를로 변화시키며 각 깉의 방법의 처리 성능을 측정하몄다. 그림 23에서 그림 26까지른 보면 페이지 크기가 증가할수록 디스크 접근수나 응답시간측면의 성능은 향상됨을 볼 수 있다.
- , 제안하는 병렬색인구조는 하나외 컴퓨터가 여러 디스크로부터 I/O의 병렬성을 취하고 다시 착각의 컴퓨터는 상호 협동작업을 동해 질의를 병렬로 처리하는 nP-nXmD 형태의 구조를 갖게 된다. 또한 보다 향상된 I/O의 병렬성을 획득하는 범위질의 알고리즘을 고안하고 이를 K-최근접 질의에 적용하여 기존의 K-최근접 질의와 실험을 통해 비교한다. 마지막으로 제안하는 병렬 고차원 색인구조른최근 중요한 저장시스템으로 부각되고 있는 SAN 환경 메 어떯게 적용시킬 수 있는지에 대해 기술한다.
- 그림 16은 응답 시간을 계산하는 에이다. 병렬 처리의 효과를 얻기 위해서 각 서버의 동작욜 순차적오루 실 햄하고 각 서버의 응답 시간을 계산헤서 가장 큰 응답시간을 병렬로 서버를 실햄헸을 때 최종 음답시간으로 한다. 그림 16에서와 같이 각 서버를 수행해서 응답시간음 얻으면 주 서버의 응답시간 RT1은 4이고 부 서버 1의 응답 시간 RT2는 5, 부 서버 2는 3이 된다고 가청했욜때 병렬환경에서 최종 응답시간은 5가 된다'
- 페이지 크기는 2-48Kbytese 변화시켰고 실험에 사용된 데이타는 10 -&)차원의 균둥분포와 9차원의 동영상으로뿌터 추출한실데이타를 각각 100Q00개씩 사용하였다. 서버의 개수는 3개로 고정하였고 전체 디스크 수는 3 - 1잉개까지 변화시켜 가면서 실험을 수행하였다.
- 성능평가 파라미터로는 페이지 크기, 서버의 개수, 디스크 수, 차원 수를 사용했고 성능평가 척도로 섬색수행시 디스크 접근수, 전체 노드수메 대한 디스크 접근 수 비율, 검색 응답시간을 측정했다. 표 1에서 성능평가 파라미터와 값온 보여준다.
- 실험결과를 차원을 변화시켰을 때, 디스크의 수를 변화시켰을 때, 페이지 크기를 변화 시켰을 때로 구분하여 정리했다. 그리고 제안하는 방법이 기존의 병렬 다차원 색인구조보다 우수하다는 것을 보여주기 위해서 MR-트리와 비교하였다.
- 노드 접근 비율이란 (총 디스크 접근수/ 색인구조외 총 노드- 수)를 의미한다. 응답시간(RT)은 디스 m I/O 시찬, CPU 시간(Tcpu) 결과 전송을 위한 동신 시간외 함요로 계산하였다. [25] 의 데이타를 참조하여 디스크 I/O 시간(TdiskIO)은 1/20, 000호토하고 통신속도(Tgw)는 1.
- 고차원 색인구조에 있어서 K-최근접 질의는 매우 중요하다. 이 논문에서는 세 가지 방법을 제시하고 실험을 통해서 가장 적절한 것을 선택한다.
- 따라시, 병렬 구조에 있어서 중요한 성길 들 중 죄소 활성 디스크(Minimum Load) 성질보다는 균등 활성 디스크 (uniSpread) 성질을 최대한 지원하는 것이 더 효과적이다. 제안된 구조는 하나외 노드들 읽기 위해서는 반드시 노드를 구성하는 페이지들이 존재하는 디스크들을 읽어야 하기 띠]문에 uniSpread성질을 최대화한 수 있게 되어 범위 길의 및 K-최근접 질의 처리시효 꾀.적이다.
- 실험 결과 두 번쩨와 세 번째 방법이 첫 번째 방법보다 좋은 성능을 나타내는 것을 볼 수 있었다. 제안된 방법뫼 성능을 평가하기 위해 시뮬레이션을 하였파. 시뮬레이션 결과 기존 병렬 색인 구조(MIE트리)보다 제안된 병렬 고차원 색인 구조가 성능이 무수함을 보몄고, 고차원의 데이타에 대해서도 효율적으로 색인할 수 있음을 보였다.
- 먼저 유사한 데이타는 서로 다른 디스크에 처장되는 디클러스터링 효과를 얻을 수 있다- 고차원 색인구조에서 한 노드에 저장되는 데이타들은 가장 유사한 것들이다. 제안하는 구조에서는 하나의 노드를 여러 디스크의 페이지메 나누어 서장하기때문에 자연스펍게 디를러스더링 효과를 얻는다, 누 번째, 트리의 하나외 노드 크기가 (그롭내의 디스m 개수 X 페이치 크기) 가 되므로 트리외 높이가 낮아진다. 노드의 는기기.
- 제안하는 방법에서는 이렇게 하지 않고 각 노드를 구성하는 페이지들외 I/O 순서를 조정하여 디스크 섭근수를 줄인다. 그림 9에서 그 에를 보여준다.
- 각 디스크 그룹 내에서 노드 분할 방법은 각 레벨에서 페이지의 수가 가장 작은 디스크에 할당을 해서 노드를 다른 디스크에 분산시켜 병렬성을 최대화한다. 질의 처리 시 범위 질의 방법은 여러 노도의 병렬 입출력을 수행하는 방법을 제안한다. 그리고 K-회 근접 실위 방범은 긱- 서버에서 K-최근접 질의를 수행하는 방법과, 범위 질외의 병릴성을 이용하여 K-최근접질의의 성능을 향상시키기 위한 방법을 제안했다.
- 첫 번째 방법은 각 서버에서 독립적으로 K-최근접질의를 수행하는 것이다. 질의가 들어오면 주 서버와 각각 외 부 서버에서 K-최근접 칠의믈 독립적으로 수행한 후 각 서버의 결과를 주 서버가 통합하여 글라이언드에게 반환한다.
- 페이지 크기는 4K, 데이타는 10만개의 균등 데이타, 서버의 수는 3, 총 디스크 수는 15로 고정한 상태에서 차원 을 10에서 80차원까지 승가시켜 가며 K-최근접 질의와 범위 질의의 디스크 접근수 및 응답시간을 측정하였다. 그림 17에서 그림 19까지는 차원에 따른 K-최근접 질의와 범위 질의의 디스크 접근수, 노드 접근 비을, 응답시간을 보여춘다.
- MR-트리는 가 서어가 여거 디스 교에 뜨리를 구성하는 형태가 아이다, 즉, 하나의 서버에는 하나의 디스크가 할당되어 전체적인 색인구조를 구성한다. 하지만 제안하는 방법은 하나의 서버가 임의 수이디스크를 가실 수 있어서 서버 수보다 디스크이 수가 딶욜 때 훨씬 유* 리하다 고래서 이 실험에서는 서버의 수를 3으로 고정하는 대신 디스크의 수를 3, 6, 15로 편화시키면서 성층을 측경하역 Mib트리와 비효하였다.
대상 데이터
- 실험에 사용된 플랫폼은 Sun Enterprise 250의 CPU 에 IGBytes의 주기억 공간을 가지고 있고 Solaris 2, 7 의 0$를 탑재하고 있으며 gcc 28을 컴파일러로 사용하몄다. 성능평가 파라미터로는 페이지 크기, 서버의 개수, 디스크 수, 차원 수를 사용했고 성능평가 척도로 섬색수행시 디스크 접근수, 전체 노드수메 대한 디스크 접근 수 비율, 검색 응답시간을 측정했다.
- 표 1에서 성능평가 파라미터와 값온 보여준다. 페이지 크기는 2-48Kbytese 변화시켰고 실험에 사용된 데이타는 10 -&)차원의 균둥분포와 9차원의 동영상으로뿌터 추출한실데이타를 각각 100Q00개씩 사용하였다. 서버의 개수는 3개로 고정하였고 전체 디스크 수는 3 - 1잉개까지 변화시켜 가면서 실험을 수행하였다.
데이터처리
- 실험결과를 차원을 변화시켰을 때, 디스크의 수를 변화시켰을 때, 페이지 크기를 변화 시켰을 때로 구분하여 정리했다. 그리고 제안하는 방법이 기존의 병렬 다차원 색인구조보다 우수하다는 것을 보여주기 위해서 MR-트리와 비교하였다. 다른 병렬 색인구조가 많이 있지만 MR-트리가 비교적 최근에 제안되었으며 높은 성능을 얻을 수 있는 nP-nD형태인 점을 고려하여 선택하였다.
이론/모형
- 제안한 병릴 고차원 색인 구조에서 각 서버는 디스크 .그룸을 관리하고, 각 디스드 그룹에 엔트리를 할당하는 방법은 가장 간단한 라문드 로빈 방법을 사용한다. 하나의 노드를 여러 디스크에 분산시켜 팬-아웃을 증가시키고 토리외 높이를 줄임으로서 첨색 성능 온 향상시킨다.
- 고차원으로 칼수록 다른디클러스터림 방법이 크게 효과른 보이지 못하고 라운드로빈 방법과 비교했을 때 크게 나은 성능을 보이지 못한다[14]. 또한 라운M 로빈 방법믄 계산에 대한 비용이 적게 들고 구현하기 쉬워 이 논문에서는 라운드 로빈 방법을 사용한다.
- 그림에서와 같이 엔트리 a, b7 c, d, e; f, g, h 가 차례로 삽입될 때 a는 첫 번째 디스크 교룹에 b는 두 번째 디스크 그룹, g는 세 번째 그룹메 차례로 할당된다. 삽입할 멘트리를 디스크 ri룹에 할당할 때는 라운드로빈 방법을 이욤한다. 고차원으로 칼수록 다른디클러스터림 방법이 크게 효과른 보이지 못하고 라운드로빈 방법과 비교했을 때 크게 나은 성능을 보이지 못한다[14].
성능/효과
- 따라서 통신에 디한 비용이 많이 발생하게 되므로 효율 척이지 않다. 두 번째 방법인 수펴노드 형태의 구성은 삭은 실의에 대해서도 거의 모든 디스크에 접근하기 때문에 전체 시스템의 성능을 저히, 시키는 문제점이 샘긴디L 따라서 독립적인 R-트리 형태로 구성하는 것이 통신비융음줄일 수 있으므로 가장 효율적이다.
- 제안된 방법뫼 성능을 평가하기 위해 시뮬레이션을 하였파. 시뮬레이션 결과 기존 병렬 색인 구조(MIE트리)보다 제안된 병렬 고차원 색인 구조가 성능이 무수함을 보몄고, 고차원의 데이타에 대해서도 효율적으로 색인할 수 있음을 보였다. 향후에는 디스크와 서버가 추가/삭제되는 경무 온라인으로 이를 처리하는 방법에 대해서 연구를 진행한다.
- 그리고 K-회 근접 실위 방범은 긱- 서버에서 K-최근접 질의를 수행하는 방법과, 범위 질외의 병릴성을 이용하여 K-최근접질의의 성능을 향상시키기 위한 방법을 제안했다. 실험 결과 두 번쩨와 세 번째 방법이 첫 번째 방법보다 좋은 성능을 나타내는 것을 볼 수 있었다. 제안된 방법뫼 성능을 평가하기 위해 시뮬레이션을 하였파.
- 그리고, KNN1 은 질의를 수행하기 위해 매번 노드를 접근할 때 마다 엔트리들을 정렬해야 하며 전체적으로 범위질의에 비해 보다 복잡한 계산이 필요하다. 이 계수!의 복잡성은 차원이 증가할수록 또 접근하는 노드의 수가 많을수록 더해지게 되어 CPU를 모렛동안 이용해야 한다, 이외에도 디스크 섭근수가 더 많다는 것이 종합적으로 착용해서 KNN1 방법이 다른 KNN 방법에 비해서 움답시칸 측면에서 휠씬 더 나빠지게 된다.
- 성늠이 향상되는 것을 톨수 있디. 이런 관지에서 > 때 제안하는 방법은 한 서버가 여러 디스크를 겁근할 수 있는 병렬 한경에서 훨씬 쫐은 성능을 말휘한다는 것읉 알 수 있다. 또한, 미스코믜 수가 15일 때 MR 느림와 제안하는 방법의 너스크접근수의 차이가 읗답시간외 차이보다 훨씬 더 큰 것율불 수 있다' 이것은 제안하는 범위 질위가 어러 노드른 보파 작온 수워 피스크 I/O믈 톰헤 읽어내는 방법욘 이웅해 디스크 접근수를 줄이고 있지만 계산헤야 느!는 양은 MR-토미얏} 시교해서 m게 다르지 많기 때문미다, 즉, 디스구 VO 횟수는 .
- 그림 20에서 그림 22까지를 보면 선체적으로 디스크의 수가 많을수록 디스크 접근 수나 웅답시간측면에서 성능이 향상되는 것을 볼 수 있다. 제안하는 방범에서 디스크의 수는 노드의 크기를 결셩하고 디스크 I/O의 병렬성을 향상시키므로 당연한 결과라 할 수 있다. 특이한 점이라면 교림 22의 응답시간에 대한 비교에서 역시 KNN1 의 응답시간이 가장 높게 나왔다.
- 제안하는 병렬 고차원 색인 구조는 무공유(Shared Nothing)와 디스크 공유(Shared Disk) 황경 모두에 젹용 가능하다. 무공유 환경에서는 각 서머가 다중 디스크를 갖는 환깅에 쉽게 적용할 수 있고 디스m 공유 환경에서는 그림 2에서와 갚이 각 서버가 접근할 수 있는 디스? i플 미리 할당하여 적용할 수 있다.
- 일반적으로 다차원 색인구조께서 변:포가 편중풜수록 질의 성능이 좀더 즣게 나타나는 것과 일치하는 현상이다. 투 방법의 비교 결과는 대체적으로 제안하는 방법이 우수하였다. 특히, 응답시감 측면에서 MR-트리의 K-최근접 칠의 가 기타 다른 질의 방법에 비해서 2-3배 정도 나쁘.
후속연구
- 그래서 유사성 즉정 척도는 노드 R, S가 있을 때 이 둘을 모두 접근하는 질의의 비율로 결정한다. 하지만, 이 연구에서 제시된 방법은 처리기에 대한 병렬성은 고려되지 않고 단지 I/O 시메 대해서만 병렬로 처리하기 때문에 성능향상에 있어서 한계가 있다. 또한 이 연구에서는 고차원의 데이타에 대한 고려가 되지 않았으며, 유사도 검색에 있어서 중요한 길 외 형태인 K-춰근접 질의에 대한 고려가 되지 않았다.
- 시뮬레이션 결과 기존 병렬 색인 구조(MIE트리)보다 제안된 병렬 고차원 색인 구조가 성능이 무수함을 보몄고, 고차원의 데이타에 대해서도 효율적으로 색인할 수 있음을 보였다. 향후에는 디스크와 서버가 추가/삭제되는 경무 온라인으로 이를 처리하는 방법에 대해서 연구를 진행한다.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.