42권 2호,
2월 2015
디지털 라이브러리
경로 예측 알고리즘의 빠른 투영 후보 선택을 위한 경로 단편 관리 구조
이 논문에서는 기존 경로 예측 알고리즘의 처리 속도를 향상시킬 수 있는 개선된 투영 후보 선택 알고리즘을 제안한다. 지금까지 다양한 사용자 이동 경로 예측 알고리즘이 개발되었으나 실시간 근거리예측 환경에 적합하지 않다. 이러한 문제점을 해결하기 위해 새로운 예측 알고리즘이 제안되었으나 몇 가지 문제점을 지닌다. 특히 보다 빠른 처리 속도를 제공할 수 있도록 개선되어야 한다. 기존 예측 알고리즘의 높은 처리 시간의 주된 원인은 투영 후보 선택 연산의 높은 시간 복잡도이다. 따라서 이 논문에서는 기존 투영 후보 선택 알고리즘의 처리 속도를 개선할 수 있는 새로운 경로 단편 관리 구조와 향상된 투영 후보 선택 알고리즘을 제안한다. 또한 비교 평가를 통해 이 논문에서 제안한 알고리즘이 효과적임을 보인다.
멀티 스레드 프로그램의 자료경합 탐지를 위한 수행 중 감시 도구
멀티 스레드 프로그램의 수행 중에 발생하는 자료경합과 원자성 위배 등과 같은 동시성 오류는 스레드들의 비결정적 수행으로 인해 다양한 수행 순서를 고려해야 하고 재생산 또한 어렵기 때문에 디버깅하기 어렵고 귀찮은 오류로 잘 알려져 있다. 이러한 자료경합을 디버깅하기 위해서는 스레드의 수행순서와 메모리 접근 및 동기화 정보 등과 같은 프로그램의 수행 중에 발생한 정보를 수집 및 분석해야 한다. 본 논문에서는 멀티 스레드 프로그램의 수행 중에 벡터 클록 시스템을 기반으로 스레드의 병행성과 접근사건들 간의 순서관계를 생성 및 유지함으로써 정확하면서도 효율적인 감시와 분석이 가능한 도구인 VcTrace를 제시한다. 제시된 감시 도구를 사용하여 멀티 스레드 기반의 응용 프로그램을 대상으로 수행중 발생한 스레드와 접근사건 등의 정보를 감시 및 유지하고, 자료경합을 탐지하는 기술과 접목하여 실용성을 분석한다.
주파수 영역에서의 계수 값 변환에 의한 공간 영역에서의 기하학적 변환과 이를 이용한 이미지 경량 암호화
대부분의 영상정보들은 데이터 양이 방대하기 때문에 압축되어 저장되고 전달된다. 이 때문에 영상정보의 변환을 위해서는 사전에 압축을 해제하여 공간정보를 추출한 뒤에 소정의 변환을 하고 다시 압축해야 하는 번거로움과 불편한 점이 있다. 본 논문에서는, JPEG등의 정지영상 압축이나 MPEG-4와 H.264 등의 영상 압축 표준에서 널리 사용되는 DCT 변환에 의한 영상정보의 주파수 영역의 계수 값들의 부호나 이들 간의 상대적 위치를 적절히 바꿈으로써 공간적 영역에서의 원하는 기하학적 변환이 이루어지는 규칙을 발견하고 정리하였다. 본 저자들은 주파수 영역에서의 계수 값 변환 효과가 공간적 영역에 어떻게 나타나는지 수학적으로 유도하고 실제 JPEG 압축 파일에 본 방식을 적용하여 이미지를 변환시켜 그 성능을 검증하였다. 이 방법은 압축을 완전히 해제하지 않고도 공간적 영역에서의 변환을 달성할 수 있기 때문에 대용량의 간단한 이미지 암호화를 위한 경량암호화 시스템에 응용될 수 있다.
데이터베이스 시스템의 원자성 쓰기 보장을 위한 스토리지 I/O 서브시스템
최근 데이터베이스 관리 시스템에서는 이중 쓰기 버퍼 기법의 단점을 보완할 수 있는 원자성쓰기 기법이 제시되었다. 원자성 쓰기 기법을 지원하기 위해서는 파일시스템과 I/O 스케줄러 등의 I/O 서브시스템과 SSD의 원자성 쓰기의 보장이 필요하다. 본 연구에서는 MariaDB의 데이터 쓰기의 기본 단위를 사용하여, 쓰기 단위 연속 블록 할당 기법, 플래그 전달을 통한 I/O 명령 병합 방지 기법, 원자성 쓰기를 지원하는 SSD를 통해 MariaDB의 원자성 쓰기를 지원하는 연구를 진행하였다. Tpcc-mysql와 SysBench를 사용하여 MariaDB에 제안된 기법을 적용한 결과, 원자성 쓰기 기법의 성능을 평가한 결과, 데이터베이스의 처리량이 이중 쓰기 버퍼 기법을 사용한 MariaDB 대비 약 40%～50% 향상된 것을 확인하였다.
하드웨어 캐시 파티셔닝과 소프트웨어 캐시 파티셔닝의 성능 비교
오늘날에는 코어당 클락 속도 발전이 한계에 부딪히게 되면서 멀티 코어 프로세서의 시대가 도래하였다. 최근에는 서버나 데스크톱 환경뿐만 아니라 모바일 환경까지 널리 보급되고 있다. 이러한 구조에서는 프로세스간 성능 간섭 현상이 발생하게 되는데, 이를 방지하기 위해서 사용되는 캐시 파티셔닝기법은 소프트웨어적인 방법과 하드웨어적인 방법 크게 두 가지로 나누어진다. 하지만 동적 캐시 파티셔닝시에 소프트웨어 캐시 파티셔닝 기법은 페이지 복사 오버헤드로 인해서 성능 향상을 기대하기 힘든데, 이에 반해서 하드웨어 캐시 파티셔닝은 이러한 페이지 복사에서 자유롭다는 장점이 있다. 이 논문에서는 상용 프로세서 중에서 하드웨어적으로 캐시 파티셔닝 기능을 제공하는 AMD Opteron 프로세서에서 소프트웨어적 캐시 파티셔닝 기법인 페이지 컬러링과 하드웨어 캐시 파티셔닝의 성능을 정적 캐시 파티셔닝 환경에서 비교해봄으로써, 하드웨어 캐시 파티셔닝의 동적 캐시 파티셔닝 활용 가능성 여부를 알아본다.
차세대 메모리의 접근 특성에 기반한 하이브리드 메인 메모리 시스템
최근 DRAM 기반의 메인 메모리 기술 발전이 한계에 봉착함에 따라 컴퓨터 시스템의 진보에도 어려움이 발생하고 있다. 이를 개선하기 위해 집적도가 높고 비휘발성을 갖는 차세대 메모리 기술이 등장하고 있으나 이들은 쓰기 속도가 느리거나 쓰기 횟수에 제한이 있는 등, 메인 메모리로 사용하기에는 아직 무리가 있다. 본 논문에서는 여러 차세대 메모리 기술들의 장점들을 조합하여 활용하는 하이브리드 메인 메모리 시스템, 즉 HyMN을 제안한다. HyMN은 차세대 메모리 기술을 쓰기적합램과 읽기적합램으로 분류하여 메인 메모리 시스템을 구성함으로써, 내구성이 양호하고, 고용량화가 용이하며, 비휘발성을 활용할 수 있는 시스템을 구현한다. 본 논문에서는 또한, 쓰기적합램이 어느 정도의 크기로 구성되어야 하는지를 보이고 정전 시 손실에 대한 복구비용이 없거나 미미한 HyMN이 일상적으로 프로세스를 실행할 때 실행 시간 성능이 DRAM으로만 구성된 시스템에 비하여 유사함을 검증한다.
스마트폰상의 지능형 개인화 서비스를 위한 강인한 파티클 필터 기반의 사용자 경로 예측
스마트폰내 GPS 및 다양한 센서 데이터를 이용하여 스마트폰 사용자의 이동 패턴을 학습하고, 이를 기반으로 사용자 목적지와 경로를 예측하여 사용자의 의도에 맞는 서비스를 제공하는 위치기반 지능형 개인화 서비스(Intelligent personal assistant) 연구가 활발히 진행 되고 있다. 위치기반 개인화 서비스의 지능성은 불완전한 센서 데이터로부터 사용자 이동 정보를 처리하여, 실시간으로 사용자의 경로를 예측하는 정확성과 효율성에 좌우된다. 본 논문은 불완전한 정보로부터 사용자의 경로와 목적지를 추론하는 동적 베이지안 네트워크 기반의 강인한 파티클 필터(Robust particle filter)를 제안한다. 제안한 강인한 파티클 필터 방법은 부정확하고, 불완전한 센서 정보를 보완할 수 있는 파티클 생성, 실시간에 계산 복잡도를 감소시키는 효율적인 스위칭 함수와 가중치 함수, 파티클의 정확도를 향상시키는 재표본화로 구성되며, 사용자의 목적지와 경로의 예측 정확성과 효율성의 성능을 향상시켰다.
지능형 자동차를 위한 조명 변화에 강인한 도로표지판 검출 및 인식
본 논문은 도로주행 영상에서 도로표지판을 인식하는 방법을 제안한다. 지능형 차량에서 얻어지는 도로표지판 영상은 일반적인 사물 영상과는 다른 두 가지 특징이 있다. 첫째는 대상이 되는 사물들은 종류가 제한적이고 형태가 단순한 도형인 경우가 대부분이다. 둘째는 일반적인 도로주행 영상은 다양한 조명 환경과 날씨 상태로 인해서 선명한 영상을 취득하기 어려운 점이다. 본 논문에서는 조명 변화가 심한 도로주행 영상에 대해서 효과적으로 특징을 추출하기 위해서 Modified Census Transform(MCT)을 개선한 특징추출 방법을 제안한다. 추출된 특징들은 히스토그램으로 쌓여지고 영상 전반에 걸쳐 아주 고차원의 기술자(Descriptor)로 변환되며, 변환된 수많은 기술자들은 가우시안 혼합 모델(Gaussian Mixture Model)을 활용한 Fisher-vector 방법에 의해서 저차원으로 변형하여 특징으로 사용한다. 본 논문에서 제안하는 방법은 일반적인 표지판 인식 방법에 비해서 조명변화에 강한 검출 결과를 보여주었으며, 실시간 검출 및 인식도 가능하였다.
L-V-C 통합 환경 실현을 위한 이기종 시뮬레이션 미들웨어 연동 방안
현대 사회에서는 새로운 기술이나 가설을 증명하기 위해 시뮬레이션을 사용한다. 특히, 군사훈련을 진행하거나 전쟁상황을 예측하기 위하여 국방 Modeling & Simulation(M&S)을 사용한다. 국방 M&S는 실제 환경에서 진행하는 Live Simulation, 가상환경에서 진행하는 Virtual Simulation, 그리고 워게임과 같은 Constructive Simulation으로 이루어지며 각각을 L체계, V체계, C체계라고 한다. L체계는 실제 환경을 전제하기 때문에 현실성이 높지만 예산 효율성이 떨어진다. 이와 반대로 V와 C체계는 현실성이 떨어지지만 예산 효율성을 높인다. 이러한 각 체계의 장단점을 바탕으로 세 가지 체계를 모두 연동한 L-V-C 통합 환경을 구축한다면 시뮬레이션의 질을 향상시킬 수 있다. 본 논문에서는 L-V-C 통합 환경을 구축하기 위해 이기종 시뮬레이션 미들웨어 간 연동하는 방안을 제시하고 서로 다른 미들웨어간의 연동 테스트 결과를 보인다.
Structural SVM 기반의 한국어 의미역 결정
의미역 결정은 자연어 문장의 서술어와 그 서술어에 속하는 논항들 사이의 의미관계를 결정하는 문제이다. 일반적으로 의미역 결정을 위해서는 서술어 인식(Predicate Identification, PI), 서술어 분류(Predicate Classification, PC), 논항 인식(Argument Identification, AI) 논항 분류(Argument Classification, AC) 단계가 수행된다. 본 논문에서는 한국어 의미역 결정 문제를 위해 Korean Propbank를 의미역 결정 학습 말뭉치로 사용하고, 의미역 결정 문제를 Sequence Labeling 문제로 바꾸어 이 문제에서 좋은 성능을 보이는 Structural SVM을 이용하였다. 실험결과 서술어 인식/분류(Predicate Identification and Classification, PIC)에서는 97.13%(F1)의 성능을 보였고, 논항 인식/분류(Argument Identification and Classification, AIC)에서는 76.96%(F1)의 성능을 보였다.
긍정 데이터 분포를 반영한 다중 인스턴스 지지 벡터 기계 학습
본 논문에서는 데이터 분포를 고려한 다중 인스턴스 지지 벡터 기계 학습 알고리즘을 제안한다. 기존의 방법은 긍정 가방 안에서 “가장 긍정”인 인스턴스만 고려하여 마진을 찾는다. 일반적으로 다중인스턴스로 표현된 데이터에서, 긍정 가방에 포함된 인스턴스들 중 실제로 긍정을 나타내는 인스턴스들은 자질 공간 상에서 서로 유사한 곳에 위치해 있다. 제안한 방법은 기존의 다중 인스턴스 지지 벡터 기계학습 알고리즘 중에서 긍정 인스턴스들의 교차점을 찾아 이 교차점과 거리를 계산하여 “가장 긍정”인 인스턴스를 선택한다. 긍정 인스턴스들의 교차점인 피벗 포인트를 구하는 방식은 두 가지이다. 먼저, 학습과정 중 추정된 긍정 인스턴스들의 중심점을 사용하는 방법과 학습 시작 시에 가장 긍정일 것으로 예상되는 긍정 인스턴스들의 중심점을 찾는 방법으로 나뉜다. 총 12개의 벤치마크 다중 인스턴스 데이터 셋을 통해 제안한 방법이 기존의 학습 알고리즘에 비해 더 좋은 성능을 보임을 보인다.
얼굴 인식을 위한 연립 대각화와 국부 선형 임베딩
국부 선형 임베딩(Locally Linear Embedding, LLE) [1]는 다양체 학습(manifold learning) 알고리즘 중 하나로 고차원 공간에 있는 데이터들 사이의 내적 값을 기반으로 임베딩하는 방법이다. LLE를 이용하여 임베딩 한 결과는 독특한 성질이 있는데, 고차원 공간 상에서 같은 평면에 있는 데이터들은 내적 값이 크기 때문에 저차원 공간에서도 가깝게 위치하도록 임베딩 되는 반면 수직으로 위치한 평면에 있는 데이터들은 내적 값이 0이 되기 때문에 서로 떨어진 위치에 임베딩된다. 한편, 한 사람의 얼굴에 다양한 각도에서 조명을 비추면서 촬영한 이미지들은 저차원의 선형 부분공간을 구성한다는 사실이 잘 알려져 있다 [2]. 이에 본 논문에서는 다른 평면에 위치하는 데이터들을 자연스럽게 분류하여 임베딩하는 LLE 알고리즘을 얼굴 이미지에 사용하여 효과적으로 얼굴 인식 문제를 해결할 수 있는 방법을 제안한다. 제안하는 방법은 LLE에 연립 대각화(Simultaneous Diagonalization, SD)를 적용한 방법으로, S연립 대각화를 적용하면 데이터들이 형성하는 평면이 수직이 되도록 바꿀 수 있기 때문에 LLE의 성질을 극대화 할 수 있다. 실험 결과, 연립 대각화를 적용하고 LLE를 적용하면 서로 다른 사람의 얼굴 이미지들이 겹치지 않고 뚜렷하게 구분되는 효과가 있음을 확인하였다.
대용량 데이터베이스에서 다차원 인덱스를 사용한 효율적인 다단계 k-NN 검색
본 논문에서는 다차원 인덱스 기반 다단계 k-NN 검색의 성능 향상 문제를 다룬다. 기존 다단계 k-NN 검색에서는 고차원 객체의 저차원 변환으로 인한 정보 손실로 k-NN 질의 결과 매우 큰 허용치(검색 범위)가 결정되어 범위 질의 결과로 많은 후보가 검색된다. 또한, 많은 후보는 후처리 과정에서 매우 많은 I/O 및 CPU 오버헤드를 발생시킨다. 본 논문에서는 이와 같은 고찰에 기반하여 범위 질의의 허용치를 줄여 후보 개수를 줄이고 이를 통해 성능을 향상시키는 방법을 제안한다. 먼저, k-NN 질의 결과로 결정된 허용치를 고차원 및 저차원 객체간 거리 비율로 강제 축소하여 범위 질의에 사용하는 허용치 축소 (근사적) 해결책을 제안한다. 다음으로, k-NN 질의 계수 k 대신 c?k 를 사용하여 얻은 보다 타이트 (tight)한 허용치로 범위 질의를 수행하는 계수 제어 (정확한) 해결책을 제안한다. 실제 객체 데이터를 사용하여 실험한 결과, 제안한 두 가지 해결책은 기존 다단계 k-NN 검색에 비해 후보 개수와 검색 시간 모두를 크게 향상시킨 것으로 나타났다.
센서 정보의 안정적인 이용을 위한 경로 예측 기반 센서 레지스트리 시스템
센서 레지스트리 시스템은 이기종 센서 네트워크 환경에서 센서 데이터의 즉시적 활용 및 끊김 없는 해석을 위해 개발되었다. 그러나 기존 센서 레지스트리 시스템은 불안정한 네트워크 상황에서 센서 데이터 해석을 위한 정보를 제공하지 못하며, 이로 인해 센서 데이터의 손실, 처리 결과의 부정확성, 서비스 품질 저하 등의 문제를 야기한다. 이 논문에서는 소프트웨어 관점에서 이러한 문제점을 해결할 수 있는 방안을 제시한다. 사용자의 이동 경로를 예측하여 사전에 센서 정보를 이동 단말기에 제공함으로써 불완전한 네트워크 접속 시점에 안정적으로 센서 정보를 활용할 수 있는 확장된 센서 레지스트리 시스템을 제안하고 실험 및 평가 결과를 보인다. 이 논문에서 제안한 확장된 센서 레지스트리 시스템은 센서 정보의 안정적 활용성 증가와 더불어 센서 기반 서비스 품질을 향상시킨다.
단일 수신기를 이용한 객체 위치추정 알고리즘 성능평가
객체에 대한 위치인식을 위해서는 3개 이상의 무선모듈이 설치된 환경에서 객체와 무선모듈간 PTMP 통신기반의 삼각측량법을 이용하는 것이 일반적이다. 따라서 무선통신 인프라가 사전에 구축된 공간에서만 적용 가능한 문제점이 있다. 이러한 문제점을 해결하기 위해 PTP 통신 방식이 제안되었으나 구체적인 검증부족으로 일반화하기에는 미흡한 문제가 있다. 본 논문에서는 기존의 PTP 통신 기반의 위치추정 알고리즘의 문제점을 분석하고 단일수신기가 다수 수신기를 대체할 수 있는 조건을 만족하는 고정객체 위치추정 알고리즘을 제안한다. 또한, 제안된 알고리즘 평가를 위해 CSS 무선통신 모듈을 이용하여 위치추정 시스템을 설계 및 구현한다. 그리고 구현된 시스템을 통한 시험 결과 10m × 16m × 1m의 실내환경에서 위치추정을 위한 최적 이동거리 간격이 3m임을 확인하였다.
iBeacon을 이용한 지하철 도착 알림 시스템
현재 스마트 디바이스의 활용도가 높아짐에 따라 사용자의 요구는 점점 복잡하게 되어가고 있다. 대부분의 IT 전문가들은 이러한 요구사항을 만족시키기 위해서 추가적인 기능들이 추가되어야 할 것으로 주장한다. 모바일 서비스 형태의 대부분이 위치 기반 서비스(LBS: Location-based Service)를 고려하기 때문에 이는 특히 중요한 연구로서 집중되고 있다. 일반적으로 Wi-Fi 기술은 위치 즉, 네트워크 존(Network Zone)이 변경됨에 따라 새로운 연결을 요구하기 때문에 위치 파악이 제한적일 수밖에 없다. 또한, GPS는 부정확한 실내 데이터를 가지기 때문에 실내 환경에서 LBS 서비스를 제공하는 것은 여전한 시스템적인 문제가 있다. 따라서 이러한 한계를 극복하기 위해 iBeacon 기술이 설계되고 Wi-Fi 혹은 GPS 대신에 LBS 서비스를 위해 사용되고 있다. Bluetooth 4.0 LE 기술 기반 iBeacon을 사용하여 우리는 현재의 사용자 위치와 지하철 도착 시간을 활용할 수 있는 다양한 mLBS(micro LBS) 서비스를 정확하고 알맞게 제공하기 위한 M-SAS(Mobile-Subway Alarm Service System)을 제안한다.
