대규모 추천 엔진을 위한 새로운 분산 그래프 데이터 저장 시스템

편집용지(모양) : 사용자정의 폭L 190, 길이: 260 위:17.5, 아래 17.5 dhfmsWHr: 20, 왼쪽:20, 머리말:10, 꼬릿말 : 0

저자명: 글자모양 : 돋움, 크기:11, 장평:90, 자간: 5

문단모양 : 문단위:10, 문단안래:10, 줄간격 : 130%

한글제목 : 글자모양 : 휴먼명조, 크기:17, 장평:90, 자간: -7 문단모양 : 문단위:10, 문단안래:10, 줄간격 : 130%

저자명*

영문제목: 글자모양 : 견명조, 크기:15, 장평:90, 자간: -7

문단모양 : 문단위:10, 문단아래:10, 줄간격 : 130%

A New Distributed Graph Data Storage System for Large-Scale Recommender Engines

영문저자명: 글자모양 : 휴먼명조, 크기:10, 장평:90, 자간: 5

문단모양 : 문단위:10, 문단아래:10, 줄간격 : 130%

저자가 3명 이상일 경우 마지막저자는 , and로 표기

게재논문양식(저자정보있음)

* 투고논문은 저자정보 삭제하여 제출

o*, o**, and o***

지원기관표기

연구지원문구: 글자모양 : 휴먼명조, 크기:9.2, 장평:90, 자간: 5 문단모양 : 문단위, 문단아래:0, 줄간격 : 130%

요  약

최근 들어 중요성이 강조되고 있는 온라인 추천 시스템들은 폭발적으로 증가하는 방대한 양의 웹 데이터를 처리하기 위한 보다 효과적인 데이터 저장 모델을 요구하고 있다. 그러나 추천 시스템에서 널리 사용되는 협업필터링(collaborative filtering)을 효과적으로 수행하면서 방대한 양의 데이터를 처리할 수 있는 데이터 저장 모델에 대한 연구는 아직 미미한 실정이다. 본 논문에서는 대규모 추천 시스템에서 요구되는 데이터 저장 모델을 위해 새로운 형태의 분산 그래프 데이터 저장 시스템을 제안한다. 제안하는 분산 그래프 데이터 저장 시스템은 대규모의 추천 엔진이 보다 빠르게 추천항목을 구성하기 위한 인덱스를 포함하고 있다. 우리는 관계형 데이터 모델과 같은 기존 데이터 모델 기반의 추천엔진들을 클라우드 컴퓨팅 환경에서 구현하고 이들과의 비교 성능 평가를 실시하여 추천 엔진의 성능을 개선하였음을 보인다.

요약본문: 7줄~8줄이내 글자모양 - 휴먼명조, 크기 :9.2, 장평:90, 자간:-6 문단모양: 문단위:0, 문단아래:0, 여백왼쪽:10, 오른쪽여백:10 줄간격 : 150%

Abstract

영문요약문: 7줄 이상 글자모양 - 영문:Times New Roman, 크기 :9.2, 장평:90, 자간:-6 단모양: 문단위:0, 문단아래:0, 여백왼쪽:10, 오른쪽여백:10

줄간격 : 150%

With the explosively increasing online data, recommender systems are more and more important. Therefore, increasing e-commerce data presents new challenges for storing and querying large amounts of data to online recommendation systems. However, there are few researches about processing a lot of online data in order to improve the performance of large-scale recommendation systems. This paper proposes a new graph data storage model for the large-scale recommendation system. In addition, the proposed graph data storage model includes new type of the index in order to rapidly compose recommendation lists. Also, we perform comparison experiments with existing data model. And we prove that our distributed graph data model has better performance with large-scale recommendation systems than other data models like the relational data model.

Keywords: 영문으로만 작성

약자를 제외하고는 모두 소문자로 작성하고, 개수는 반드시 4~6개로 작성

글자,문단: 영문요약과 동일

Keywords

distributed graph database, recommender systems, collaborative filtering, cloud computing

대규모 추천 엔진을 위한 새로운 분산 그래프 데이터 저장 시스템

Journal of KIIT. Vol. 23, No. 0, pp. 00-00, 00 00, 2025. pISSN 1598-8619, eISSN 2093-7571

각주(저자소속) : 글자모양: 휴먼명조, 크기:8.2, 장평:100, 자간:-8, 줄간격:125%

ORCID ID

* 00대학교 00과 - ORCID: https://orcid.org- (클릭하면 사이트로 이동됨)에서 등록후 기입 ** 00대학교 00학과 교수(교신저자) - ORCID:	□ Received: 00 17, 2024, Revised: 00 20, 2024, Accepted: 00 15, 2025 □ Corresponding Author: 00 Dept. of Korea Tel.: + , Email: 0000

Ⅰ. 서  론

각장제목: 글자모양: 휴먼고딕,

크기:11, 장평:90, 자간:-6 단모양:여백왼쪽:0, 오른쪽여백:0

문단위, 문단아래: 0

줄간격: 150%, 장제목 위아래 한줄위아래 한줄띄기

가운데정렬

서론부터 단을 2단으로 작업합니다.

바탕글 : 본문내용 - 글자모양: 휴먼명조, 크기:10, 장평:90, 자간:-6 단모양: 문단위:0, 문단아래:0, 여백왼쪽:0, 오른쪽여백:0 들여쓰기:10 줄간격:150%

웹의 눈부신 발전은 온라인 쇼핑과 같은 전자상거래나 영화와 음악과 같은 콘텐츠들의 소비들을 활성화 시키며 인간 생활을 더욱 풍요롭고 윤택하게 만들어 가고 있다. 그러나 폭발적인 온라인 데이터의 증가는 원하는 정보를 얻고자하는 사용자들과 이들 사용자를 대상으로 하는 사업자들에게 다양한 형태의 많은 불편함과 문제점들을 야기 시키고 있다. 예를 들어, 전자상거래 영역에서의 기업들은 사용자들이 온라인 쇼핑을 하면서 만들어내는 다양한 형태의 많은 히스토리 데이터를 마케팅 목적으로 처리하기 위한 어려움을 겪고 있다. 반대로, 사용자들은 정보의 홍수 속에서 자신이 찾고자하는 정보나 콘텐츠를 찾아내는데 불편함을 느끼고, 자신의 정보 욕구를 효과적으로 충족해내지 못하고 있다. 맞춤화나 개인화 서비스가 인터넷 쇼핑몰이나 웹 콘텐츠 서비스 제공자에게 있어 중요한 성공요인으로 여겨지면서 추천 시스템에 대한 필요성과 관심이 더욱 증대되었다[1][2]. 추천 시스템은 앞서 기술된 정보의 과부하(Information overload)로 인해 야기되는 문제점들을 해결하고 개인화 서비스가 가능하게 한다는 장점을 가지고 있다. 일찍이 학계에서는 다양한 형태의 추천 알고리즘들이 연구되고 소개되었으며, 현재에도 활발히 진행되고 있다. 또한 Amazon, Netflix등 추천 시스템을 도입한 상거래 사이트들은 추천 시스템의 필요성과 중요성을 입증한 대표적인 성공 사례라 할 수 있다[3][4]. 대표적인 추천 기법인 협업 필터링(CF, Collaborative Filtering)은 보다 효과적으로 사용자의 선호도를 예측하여 추천 항목을 구성할 수 있는 것으로 알려져 있다 [5]. 그러므로 거의 대부분의 추천 시스템에서 협업 필터링 알고리즘을 사용하고 있을 뿐만 아니라, 추천 시스템의 성능을 높이려는 대부분의 연구들도 협업 필터링 기법을 확장한 형태로 새로운 추천 기법들을 제안하고 있다. 따라서 추천 시스템에서 협업 필터링은 매우 핵심적이며 중요한 요소라 할 수 있다.

그러나 추천시스템에서도 히스토리 데이터와 같은 저장하고 처리해야할 사용자 데이터가 증가함에 따라 성능이 저하되는 문제점에 직면하게 된다. 특히, 추천 시스템의 성능을 좌우하는 협업 필터링은 사용자간 유사도를 기반으로 추천 항목을 구성하는 특성을 가지고 있다. 결과적으로 추천 항목을 구성하기 위하여 유사도 계산을 해야 할 데이터가 증가 할수록 전체 추천 시스템의 성능이 떨어 질 수밖에 없는 것이다.

추천 시스템의 성능을 높이려는 대부분의 기존 연구들은 추천 항목에 대한 정확도를 높이려는 연구가 대부분이다[6]-[8]. 즉, 증가하는 데이터의 양을 고려하여 추천 시스템의 성능을 높이려는 연구는 아직 까지 미미한 실정이다. 따라서 본 논문에서는 대규모 추천 시스템의 추천 성능을 보다 효과적으로 높이기 위한 분산 그래프 데이터 모델을 제안한다. 우리는 기존의 관계형 데이터 모델 보다 그래프 데이터 모델이 대규모 추천 시스템에서 보다 효과적으로 적용 될 수 있음을 파악하고 대규모 추천 시스템에서 요구되는 데이터를 분산 환경의 그래프 데이터베이스에 저장한다. 또한 대량의 사용자 데이터를 처리함에 있어서 추천 항목에 대한 정확도를 유지하고 검색 시간을 단축하기 위해 새로운 형태의 인덱스 기법을 적용한다. 이를 위해 본 논문에서는 [9]에서 제안된 유사 사용자 색인을 분산 환경에 실제 적용하여 대규모 추천 엔진의 성능을 높일 수 있음을 보이고자 한다. 본 논문의 기여도를 나열하면 다음과 같다. 첫째, 증가하는 추천 시스템의 중요성과 필요성에 부응하여 현재까지 연구 사례가 없던 대규모 추천 엔진을 위한 데이터 저장시스템을 정의하고 구현하였다. 둘째, 실제 분산 환경에서의 성능 평가를 통해 추천 시스템의 성능이 개선되었음을 보였다.

본 논문의 구성을 다음과 같다. 2장은 관련연구로 추천 시스템의 필요성과 중요성에 대하여 논하고 추천 시스템의 대표적 추천 기법인 협업 필터링에 대해 기술한다. 또한 최근의 NoSQL의 중요성이 커짐으로 인하여 그 관심이 증폭되고 있는 그래프데이터베이스를 소개하며, 분산 그래프데이터베이스의 최근 연구 동향을 살펴본다. 3장에서는  본 논문에서 제안하는 분산 그래프 데이터 저장 모델에 대해 자세하게 기술한다. 4장에서는 기존 데이터 저장 모델과 제안 저장 모델을 기반으로 작동하는 추천 시스템들을 클라우드 환경에서 구현하고 이를 기반으로 실시한 성능 평가에 대해 논한다. 마지막으로 5장에서는 결론에 대해 기술하고 본 연구가 갖는 한계점 및 향후 연구에 대하여 기술한다.

Ⅱ. 관련 연구

소제목: 2.1 등으로 표기  글자모양:중고딕, 크기 :11, 장평:90, 자간:-6 단모양: 문단위:0, 문단아래:0,

여백왼쪽:0, 오른쪽여백:0 왼쪽정렬,

들여쓰기:0 줄간격:150%

2.1 추천 엔진과 협업 필터링

구글이나 네이버등과 같은 사이트들의 일반적인 검색 엔진과 달리 추천 시스템은 개인 사용자의 성향이나 선호도 등을 고려하여 보다 개인화된 정보 서비스를 제공하는데 그 목적이 있다. 따라서 1990년대에 본격적으로 시작된 추천 시스템에 대한 연구들은 지금까지도 꾸준히 발전 해 오고 있으며, 그 중요성과 필요성이 계속적으로 증가함에 따라 앞으로도 더욱 발전할 것으로 예상된다. 추천 시스템을 위한 개인화 기법으로는 크게 규칙 기반 필터링(Rule-based filtering), 학습 에이전트, 마지막으로 협업 필터링기법으로 정의 할 수 있다. 이 중 협업 필터링은 추천 시스템 분야에서 가장 성공적인 추천 기법으로 거의 모든 추천 시스템에 적용되고 있다. 협업 필터링의 핵심은 추천 대상이 되는 사용자와 유사한 다른 사용자들을 찾고, 이들 유사 사용자 집단에서 높이 평가된 아이템을 추천 하는 것이다.

기존의 많은 추천 시스템 관련 연구들은 주로 협업필터링 기법을 확장하여 선호도 예측의 정확도와 추천 능력을 향상시키기 위한 기법들을 제안하였다. 대표적으로 Saewar은 데이터의 희박성(Sparcity)으로 인한 추천 성능 저하를 해결하기 위한 추천 기법을 제안하였으며, Kim은 K-means 클러스터링 기법을 협업 필터링기법에 적용하여 추천 정확도를 높이 고자 했다[5]-[8]. 최근까지 진행되고 있는 추천 시스템 관련 연구들 역시 개인 사용자에게 보다 적합한 추천 서비스를 제공하기 위해 협업 필터링 기법을 확장한 다양한 형태의 추천 기법들을 제안하고 있다. 결론적으로, 추천 시스템의 성능을 높이려는 대부분의 기존 연구들은 추천 항목에 대한 정확도를 높이려는 연구가 대부분이다. 즉, 증가하는 데이터의 양을 고려하여 추천 시스템의 성능을 높이려는 연구는 아직 까지 미미한 실정이다.

2.2 NoSQL

소셜 네트워크 서비스 등의 등장으로 급속히 증가하는 비정형 데이터의 처리와 저장을 지원하는 데이터베이스들을 통칭하여 NoSQL(Not only SQL)라 부른다[10]-[12]. NoSQL은 테이블기반의 기존의 관계형 데이터가 아닌 다양한 형태의 데이터를 효율적으로 처리할 수 있는 구조와 유연성을 갖춘 분산 데이터베이스 관리 시스템이라 할 수 있다[11].  NoSQL은 데이터 저장 모델에 따라 컬럼 패밀리 스토리지, 문서 기반 스토리지, 키/밸류 기반 스토리지, 마지막으로 그래프 데이터베이스로 나뉜다. 컬럼 패밀리 스토리지 기반 NoSQL의 대표적인 사례인 빅테이블은 구글의 다양한 서비스에서 사용되고 있으며 대량의 데이터 저장과 처리에 용이하다고 알려져 있다[13]. 문서기반 NoSQL로는 SNS의 대표 성공 사례인 트위터에서 사용하고 있는 Mongo DB와 Couch DB등이 있다[15][16]. 키/밸류 기반 NoSQL에는 페이스북의 카산드라(Casandra)가 대표적인 사례이다. 그래프 기반 NoSQL은 앞서 나열한 NoSQL들과 달리 아직 까지 비즈니스 영역에서 활발하게 시장이 활성화되지 않고 있으며 적용 사례 또한 흔하지 않다. 그러나 최근 들어 그래프 데이터베이스는 소셜 네트워크 서비스나 추천 시스템등 데이터간 연관성이 중요하게 고려되는 영역에서 가장 적합한 저장 데이터 모델로 알려지면서 그래프데이터베이스와 관련된 연구들이 활발히 진행되고 있다. 대표적인 사례로 Neo Technology 사의 Neo4j가 손꼽힌다[18].

2.3 분산 그래프 데이터베이스

분산 컴퓨팅 분야는 지난 수년간 꾸준히 연구되어오고 있으며 분산 시스템의 성능을 높일 수 있는 많은 기법들이 제안되어왔다. 최근 [00]에서는 전체 시스템의 부하를 고루 분산하여 시스템의 신뢰성을 높이는 분산 기법이 제안되었다. 그러나 분산 그래프 데이터베이스의 경우 최근에 들어서야 활발히 연구되는 단계이므로 아직 까지 해결해야할 이슈들이 많다고 할 수 있다.

그래프 데이터베이스는 매우 다양한 영역의 데이터를 네트워크 구조를 갖는 그래프에 저장하고 이들 데이터에 대한 고수준의 접근성을 제공한다. 그래프 데이터베이스는 기본적으로 노드와 노드간 관계를 의미하는 에지, 그리고 노드에 저장된 데이터와 이들 데이터간 관계를 기술하는 속성으로 구성된다. 또한 다양한 탐색 알고리즘 적용을 통해 그래프 상에서의 질의를 처리하게 된다.

그래프 데이터베이스는 기존 NoSQL과 뚜렷히 구별되는 특성들을 지닌 것으로 알려져 있다. 특히, 그래프 데이터베이스는 다른 NoSQL들과 달리 데이터 규모나 가용성보다 데이터 간 연관성이나, 데이터 간 관계 분석 등에 사용 목적이 있다고 할 수 있다. 실제로 그래프 데이터베이스는 생물정보학, 추천 엔진, 그리고 소셜 네트워크나 클라우드 분석등 데이터 간 관계를 데이터 자체보다 중요하게 여기는 분야에서 사용된다. 그러나 시스템의 가용성과 데이터 규모 등을 고려하지 않는 기존의 그래프 데이터베이스는 방대한 양의 웹 데이터를 처리하기에 많은 한계점을 지니고 있다.

또한 그래프 데이터베이스 상에서의 검색은 질의어에 부합하는 속성을 갖는 노드나 노드간 특정 관계를 찾아내는 것을 목적으로 한다. 검색의 효과적인 수행을 위해서 다양한 형태의 인덱스 기법들을 그래프 데이터베이스에 적용할 수 있다. 그러나 일반적으로 사용되는 기존 인덱스 기법들과 달리 데이터 자체를 나타내는 노드 정보뿐만 아니라 데이터간 관계를 의미하는 에지 정보 또한 고려하여 색인을 수행하여야 한다. 그래프 데이터베이스 기반의 검색과 색인 기법들은 비교적 생물정보학 분야에서 활발히 진행되어왔다. 그러나 SNS나 전자 상거래 등에서 발생하는 웹 데이터를 저장하고 처리하는데 이들 기법들을 적용하기에는 적합하지 않다. 그러므로 웹에서 발생하는 비정형 데이터를 처리하고 저장하는 그래프 데이터베이스에 적합한 검색 기법과 색인 기법에 대한 연구가 필요한 실정이다.

최근 들어 그래프 데이터베이스에 대한 관심이 증폭되면서 관련 연구도 활발히 진행되고 있다. 이들 대부분은 앞서 기술한 문제점을 해결하기 위한 분산 기반의 그래프 데이터베이스에 관한 연구들이다. 대표적으로 Li-Young은 대규모 소셜 컴퓨팅을 위한 분산 그래프 데이터 저장 시스템을 제안하였다. 그의 연구에서는 Front end, Middleware, 그리고 Backend Store의 3개 층으로 구성된 분산 시스템을 구현하고 소셜 컴퓨팅에서 널리 사용되는 페이지랭크 등의 알고리즘들을 적용해 봄으로써 분산 그래프 데이터 저장 시스템이 시스템의 성능을 높일 수 있음을 보였다. 상용화된 대표적인 분산 그래프 데이터베이스로는 마이크로소프트사의 Trinity를 꼽을 수 있으며 오픈 소스 프로젝트로는 Titan등이 있다. 이밖에도 클라우드 환경에서 대규모 데이터를 효과적으로 처리하기 위한 연구들도 있다. 그러나 이들 상용 SW나 관련 연구 대부분은 계속적으로 증가하는 대량의 그래프 데이터를 저장하는데 주로 초점을 두고 있다. 따라서 그래프에 속한 데이터간 연관성 분석과 같은 대규모 시스템의 성능을 높이기 위한 컴퓨팅 기법에 대한 연구 사례는 아직 까지 미미하다.

Ⅲ. 대규모 추천 엔진을 위한 분산 그래프 데이터 저장 시스템

기존의 많은 추천 시스템들의 추천 기법들은 관계형 데이터베이스에 저장된 데이터들을 토대로 작동되었다. 그러나 테이블 간 조인 연산을 요구하는 관계형 데이터베이스는 추천 시스템의 성능 저하를 야기 한다고 알려졌다[12]. 또한 방대한 양의 웹 데이터를 토대로 하는 추천 기법이 효과적으로 적용되기 위한 분산 그래프 데이터 저장 모델의 필요성이 증대되고 있지만 이와 관련된 연구는 아직 알려진 바가 없다. 따라서 본 논문에서는 그래프 데이터베이스 기반의 대규모 추천 엔진을 위한 분산 그래프 데이터 저장 시스템을 제안한다.

본 연구에서는 관련연구에서 소개된 Li-Young의 [00]에서 제안한 3개 층의 분산 저장구조를 확장하여 추천 시스템에 적합한 새로운 분산 저장 구조를 정의 한다. 즉, 소셜 컴퓨팅에 특화된 Li-Young의 분산 저장구조와 달리, 본 연구에서는 대규모 추천 시스템의 적합하게 작동될 수 있도록 유사 사용자 인덱스를 고안하여 분산 저장 시스템의 성능을 높이고 각 파티션에 추천 엔진을 포함하였다.

그림 1. 대용량 추천 시스템을 위한 분산 그래프 데이터 저장 시스템 구조

Fig. 1. Architecture of distributed graph data storage system for large-scale recommender systems

그림 1은 본 논문에서 제안하는 대규모 추천 엔진을 위한 분산 그래프 데이터 저장 모델 기반 시스템의 전체구조를 나타낸다. 전체 구조는 크게 세 개의 단계인 Front end, Middleware, 그리고 Backend Store로 구성된다. 먼저, Front end 단계는 사용자와의 인터페이스를 구현하는 단계로, name server와 유사 사용자 노드에 대한 색인인 유사 사용자 인덱스로 구성된다. name server는 사용자로부터 노드 아이디(Node identification)를 키워드로 하는 질의어를 전달받아 해당 질의어에 부합하는 노드들의 저장 위치를 similar user index로부터 가져온다. 유사 사용자 인덱스는 본 연구의 토대라 할 수 있는 [9]에서 제안된 색인기법으로 그래프 데이터베이스 기반의 추천 시스템의 성능을 보다 효과적으로 개선할 수 있음을 보였다.

그림 2는 [9]에서 제안된 유사 사용자 인덱스의 구조를 보인다. 유사 사용자 인덱스는 B-트리를 기반으로 구현되었으며 말단에는 각 특정 사용자 노드와 유사한 사용자 노드들의 노드 위치 정보가 저장 되어 있다. 협업 필터링 기법은 특정 사용자와 비슷한 성향을 가진 유사 사용자들을 기반으로 추천 목록을 구성한다. 전체 그래프에서 유사 사용자 노드들을 찾아 이를 따로 인덱스에 포함하기 위해 [9]에서는 협업 필터링 알고리즘을 분석하여 유사 사용자로 추출될 확률적 요소들을 정의하고 이를 기반으로 유사 사용자 노드들을 인덱스로 미리 구성하였다.

그림, 표, 식과 글사이는 한줄을 띄웁니다.

그림과 표 안은 영문표기만 가능합니다.

그림캡션: 글자모양: 중고딕, 크기 :9, 장평:90, 자간:-6 단모양: 문단위:0, 문단아래:0, 여백왼쪽:0, 오른쪽여백:0 왼쪽정렬, 들여쓰기 : 0 줄간격 :130%, 가운데정렬

그림 2. 유사 사용자 색인

Fig. 2. Similar user index

표 1. 실험 데이터 세트

Table 1. Experimental data sets

Data type Number of data	User	Movie content	Evaluation points
2,000	1,500	500	54,032
4,000	3,000	1,000	84,000
6,000	4,000	2,000	354,003
8,000	5,000	3,000	754,004
9,940	6,040	3,900	1,000,209

표캡션: 글자모양:중고딕, 크기 :9, 장평:90, 자간:-6 단모양: 문단위:0, 문단아래:0, 여백왼쪽:0, 오른쪽여백:0

왼쪽정렬, 들여쓰기 : 0

줄간격 :130%, 왼쪽정렬

표 1은 5개의 실험 데이터 세트를 보인다. 평가 점수는 사용자 A가 영화 콘텐츠 B에 대해 직접 부여한 평가 점수로 그래프 데이터베이스에서는 사용자 노드와 콘텐츠 노드의 관계를 구성하는 에지의 속성 값으로 나타낼 수 있다.

4.3 성능 평가

제안한 분산 그래프 데이터 저장 시스템의 성능 평가를 위해서 본 연구에서는 관계형 데이터베이스 기반의 추천 엔진과 제안 저장 시스템 기반의 추천 엔진을 구현하고 이들 각각의 추천 알고리즘의 수행 시간을 측정한다. 제안 기법과 RDB 기반의 추천 엔진의 성능은 매우 뚜렷한 차이를 보인다. 특히, 데이터의 크기가 커져감에 따라 RDB 기반의 추천 엔진 경우, 추천 항목 구성 시간도 비례하여 증가하는 반면, 제안 시스템 기반의 추천 엔진은 데이터 크기의 상관없이 비교적 일정한 추천 항목 구성 시간이 걸리는 것을 보였다.

식은 왼으로 정렬 식번호는 오른으로 정렬.

[eqn: hat{f} (x,y)`=`median` _{(s,t)` IN Sxy} ` LEFT { g`(s,t) RIGHT }]           (1)

Ⅴ. 결론 및 향후 과제

폭발적인 온라인 데이터의 증가는 원하는 정보를 얻고자하는 사용자들과 이들 사용자를 대상으로 하는 사업자들에게 다양한 형태의 많은 불편함과 문제점들을 야기했다. 이러한 문제점들을 해소하기 위한 목적으로 등장한 다양한 형태의 추천 시스템들 역시 히스토리 데이터와 같은 저장하고 처리해야할 사용자 데이터가 증가함에 따라 성능이 저하되는 문제점에 직면하게 되었다.

본 논문에서는 대규모 추천 시스템의 추천 성능을 보다 효과적으로 높이기 위한 새로운 분산 그래프 데이터 모델을 제안하였다. 이를 위해 대량의 사용자 데이터를 처리함에 있어서 추천 항목에 대한 정확도를 유지하고 검색 시간을 단축하기 위해 새로운 형태의 유사 사용자 인덱스가 적용된 그래프 데이터 저장 시스템을 구현 하였다. 제안 시스템의 비교 성능 평가를 위해 관계형 데이터 베이스기반의 추천 엔진과 제안 시스템 기반의 추천 엔진을 각각 구현하고 추천 항목 구성 시간을 측정해 봄으로써 제안 시스템이 기존 관계형 데이터베이스보다 효과적으로 대규모 추천 엔진의 성능을 높일 수 있음을 보였다.

본 논문에서는 이전에 시도된 바 없던 대규모 추천 엔진을 위한 분산 그래프 데이터 저장 시스템을 제안 및 구현하고 추천 시스템의 성능을 높일 수 있음을 입증하였다는 점에서 연구에 의의를 찾을 구 있다. 그러나 제안 시스템에서 적용된 파티션 기법이 전체 시스템의 성능에 미치는 내용등과 관련한 실험이 이루어지지 않았다는 점과 기존 분산 그래프 데이터 저장 시스템들과의 적절한 비교 평가가 이루어지지 않았다는 점 등에서 본 연구의 한계를 찾을 수 있다. 따라서 이들 한계점을 극복하기 위한 연구를 본 논문의 향후 과제로 한다.

References

[1] D. S. Kim and Y. W. Chung, "Message delivery considering quality of service in delay tolrerant network", Journal of KIIT, Vol. 10, No. 11, pp. 121-127, Nov. 2012.

[3] G. Linden, B. Smith, and J. York, "Amazon.com recommendations: item-to-item collaborative filtering", Internet Computing, IEEE, Vol. 7, No. 1, pp. 76-80, Feb. 2003. https://doi.org/10.1109/MIC.2003.  1167344.

[4] Paul. C. Krause and Oleq Wasynczuk, "Electro mechanical Motion Devices", McGraw-Hill, pp. 23-45, May 1998.

[5] IRTF Delay Tolerant Networking research group, http://www.dtnorg.org. [accessed: Jan. 05, 2016]

저자소개

한글이름:

글자모양:돋움, 크기 :10, 장평:90, 자간:-6 단모양: 문단위:0, 문단아래:0, 여백왼쪽:0, 오른쪽여백:0

왼쪽정렬, 들여쓰기: 0

줄간격:150%, 왼쪽정렬

홍 길 동 (Gil-Dong Hong)

2xxx년 x월 : 한국대학교 전파공학과(공학사)

사진

2xxx년 x월 : 한국대학교 전파공학과(공학석사)

저자소개: 글자모양: 휴먼명조),

크기 :9, 장평:90, 자간:-6 단모양: 문단위:0, 문단아래:0, 여백왼쪽:0, 오른쪽여백:0 왼쪽정렬, 내어쓰기: 10 줄간격 :150%, 왼쪽정렬

2xxx년 x월 ~ 현재 : (주)에이비씨텔레콤 연구원

관심분야 : 전력분배/결합기, 초고주파 발진기, CDMA 단말기 Hardware

참고문헌: 글자모양 - 영문:Times New Roman, 크기 :10, 장평:90, 자간:-6

(저자, 저서명 문단모양- 줄간격 : 150%, 내어쓰기 : 15

References 형식 : 모두 영문표기

<저서>

저자명, “저서명”, 출판사, pp. 10-13, 월, 년도. DOI.

<저자명표기>

[1] W. Willinger, M. S. Taqqu, and A. Erramilli

<DOI 표기>

예 https://doi.org/10.1109/MIC.2003.1167344

(1) Journal Article

[1] D. W. Ryoo and C. S. Bae, "Design of The Wearable Gadgets for Life-Log Services based on UTC", IEEE Transactions on Consumer Electronics, Vol. 53, No. 4, pp. 1477-1482, Nov. 2007.

(2) Book

[1] H. K. Hartline, A. B. Smith, and F. Ratlliff, "Inhibitory interaction in the retina", In Handbook of Sensory Physiology, Springer-Verlag, pp. 381-390, 1972.

(3) Conference Proceedings

[1] Y. Yamamoto, S. Machida, and K. Igeta, "Micro-cavity semiconductors with enhanced spontaneous emission", Proc. 16th European Conf. on Opt. Commun., Amsterdam, The Netherlands, pp. 3-13, Sept. 1990.

(4) Patents

[1] C. E. Larsen, R. Trip, and C.R. Johnson, Methods for procedures related to the electrophysiology of the heart. U.S. Patent 5,529,067, June 25, 1995.

(5) Web URL

[1] INRIA Person Dataset: http://pascal.inrialpes.fr/data/human/. [accessed: Nov. 04, 2015]

* References 는 본문내에서 순서대로 나와야 합니다.

* References 는 8개이상(2개는 국제논문)

대규모 추천 엔진을 위한 새로운 분산 그래프 데이터 저장 시스템

편집용지(모양) : 사용자정의 폭L 190, 길이: 260 위:17.5, 아래 17.5 dhfmsWHr: 20, 왼쪽:20, 머리말:10, 꼬릿말 : 0

한글제목 : 글자모양 : 휴먼명조, 크기:17, 장평:90, 자간: -7 문단모양 : 문단위:10, 문단안래:10, 줄간격 : 130%

*

영문제목: 글자모양 : 견명조, 크기:15, 장평:90, 자간: -7

문단모양 : 문단위:10, 문단안래:10, 줄간격 : 130%

A New Distributed Graph Data Storage System for Large-Scale Recommender Engines

투고논문양식(저자정보없음)

*

지원기관표기

요  약

최근 들어 중요성이 강조되고 있는 온라인 추천 시스템들은 폭발적으로 증가하는 방대한 양의 웹 데이터를 처리하기 위한 보다 효과적인 데이터 저장 모델을 요구하고 있다. 그러나 추천 시스템에서 널리 사용되는 협업필터링(collaborative filtering)을 효과적으로 수행하면서 방대한 양의 데이터를 처리할 수 있는 데이터 저장 모델에 대한 연구는 아직 미미한 실정이다. 본 논문에서는 대규모 추천 시스템에서 요구되는 데이터 저장 모델을 위해 새로운 형태의 분산 그래프 데이터 저장 시스템을 제안한다. 제안하는 분산 그래프 데이터 저장 시스템은 대규모의 추천 엔진이 보다 빠르게 추천항목을 구성하기 위한 인덱스를 포함하고 있다.

요약본문: 7줄 이상 글자모양 - 휴먼명조, 크기 :9.2, 장평:90, 자간:-6 문단모양: 문단위:0, 문단아래:0, 여백왼쪽:10, 오른쪽여백:10 줄간격 : 150%

Abstract

영문요약문: 7줄~8줄이내 글자모양 - 영문:Times New Roman, 크기 :9.2, 장평:90, 자간:-6 단모양: 문단위:0, 문단아래:0, 여백왼쪽:10, 오른쪽여백:10

줄간격 : 150%

With the explosively increasing online data, recommender systems are more and more important. Therefore, increasing e-commerce data presents new challenges for storing and querying large amounts of data to online recommendation systems. However, there are few researches about processing a lot of online data in order to improve the performance of large-scale recommendation systems. This paper proposes a new graph data storage model for the large-scale recommendation system. In addition, the proposed graph data storage model includes new type of the index in order to rapidly compose recommendation lists. Also, we perform comparison experiments with existing data model. And we prove that our distributed graph data model has better performance with large-scale recommendation systems than other data models like the relational data model.

Keywords: 영문으로만 작성

약자를 제외하고는 모두 소문자로 작성하고, 개수는 반드시 4~6개로 작성

글자,문단: 영문요약과 동일

Keywords

distributed graph database, recommender systems, collaborative filtering, cloud computing

대규모 추천 엔진을 위한 새로운 분산 그래프 데이터 저장 시스템

Journal of KIIT. Vol. 23, No. 0, pp. 00-00, 00 00, 2025. pISSN 1598-8619, eISSN 2093-7571

*	□

Ⅰ. 서  론

서론부터 단을 2단으로 작업합니다.

각장제목: 글자모양: 휴먼고딕,

크기:11, 장평:90, 자간:-6 단모양:여백왼쪽:0, 오른쪽여백:0

문단위, 문단아래: 0

줄간격: 150%, 장제목 위아래 한줄위아래 한줄띄기

가운데정렬

웹의 눈부신 발전은 온라인 쇼핑과 같은 전자상거래나 영화와 음악과 같은 콘텐츠들의 소비들을 활성화 시키며 인간 생활을 더욱 풍요롭고 윤택하게 만들어 가고 있다. 그러나 폭발적인 온라인 데이터의 증가는 원하는 정보를 얻고자하는 사용자들과 이들 사용자를 대상으로 하는 사업자들에게 다양한 형태의 많은 불편함과 문제점들을 야기 시키고 있다. 예를 들어, 전자상거래 영역에서의 기업들은 사용자들이 온라인 쇼핑을 하면서 만들어내는 다양한 형태의 많은 히스토리 데이터를 마케팅 목적으로 처리하기 위한 어려움을 겪고 있다. 반대로, 사용자들은 정보의 홍수 속에서 자신이 찾고자하는 정보나 콘텐츠를 찾아내는데 불편함을 느끼고, 자신의 정보 욕구를 효과적으로 충족해내지 못하고 있다. 맞춤화나 개인화 서비스가 인터넷 쇼핑몰이나 웹 콘텐츠 서비스 제공자에게 있어 중요한 성공요인으로 여겨지면서 추천 시스템에 대한 필요성과 관심이 더욱 증대되었다[1][2]. 추천 시스템은 앞서 기술된 정보의 과부하(Information Overload)로 인해 야기되는 문제점들을 해결하고 개인화 서비스가 가능하게 한다는 장점을 가지고 있다. 일찍이 학계에서는 다양한 형태의 추천 알고리즘들이 연구되고 소개되었으며, 현재에도 활발히 진행되고 있다. 또한 Amazon, Netflix등 추천 시스템을 도입한 상거래 사이트들은 추천 시스템의 필요성과 중요성을 입증한 대표적인 성공 사례라 할 수 있다[3][4]. 대표적인 추천 기법인 협업 필터링(Collaborative Filtering: CF)은 보다 효과적으로 사용자의 선호도를 예측하여 추천 항목을 구성할 수 있는 것으로 알려져 있다 [5]. 그러므로 거의 대부분의 추천 시스템에서 협업 필터링 알고리즘을 사용하고 있을 뿐만 아니라, 추천 시스템의 성능을 높이려는 대부분의 연구들도 협업 필터링 기법을 확장한 형태로 새로운 추천 기법들을 제안하고 있다. 따라서 추천 시스템에서 협업 필터링은 매우 핵심적이며 중요한 요소라 할 수 있다.

그러나 추천시스템에서도 히스토리 데이터와 같은 저장하고 처리해야할 사용자 데이터가 증가함에 따라 성능이 저하되는 문제점에 직면하게 된다. 특히, 추천 시스템의 성능을 좌우하는 협업 필터링은 사용자간 유사도를 기반으로 추천 항목을 구성하는 특성을 가지고 있다. 결과적으로 추천 항목을 구성하기 위하여 유사도 계산을 해야 할 데이터가 증가 할수록 전체 추천 시스템의 성능이 떨어 질 수밖에 없는 것이다.

추천 시스템의 성능을 높이려는 대부분의 기존 연구들은 추천 항목에 대한 정확도를 높이려는 연구가 대부분이다[6]-[8]. 즉, 증가하는 데이터의 양을 고려하여 추천 시스템의 성능을 높이려는 연구는 아직 까지 미미한 실정이다. 따라서 본 논문에서는 대규모 추천 시스템의 추천 성능을 보다 효과적으로 높이기 위한 분산 그래프 데이터 모델을 제안한다. 우리는 기존의 관계형 데이터 모델 보다 그래프 데이터 모델이 대규모 추천 시스템에서 보다 효과적으로 적용 될 수 있음을 파악하고 대규모 추천 시스템에서 요구되는 데이터를 분산 환경의 그래프 데이터베이스에 저장한다. 또한 대량의 사용자 데이터를 처리함에 있어서 추천 항목에 대한 정확도를 유지하고 검색 시간을 단축하기 위해 새로운 형태의 인덱스 기법을 적용한다. 이를 위해 본 논문에서는 [9]에서 제안된 유사 사용자 색인을 분산 환경에 실제 적용하여 대규모 추천 엔진의 성능을 높일 수 있음을 보이고자 한다. 본 논문의 기여도를 나열하면 다음과 같다. 첫째, 증가하는 추천 시스템의 중요성과 필요성에 부응하여 현재까지 연구 사례가 없던 대규모 추천 엔진을 위한 데이터 저장시스템을 정의하고 구현하였다. 둘째, 실제 분산 환경에서의 성능 평가를 통해 추천 시스템의 성능이 개선되었음을 보였다.

바탕글 : 본문내용 - 글자모양:휴먼명조, 크기:10, 장평:90, 자간:-6 단모양: 문단위:0, 문단아래:0, 여백왼쪽:0, 오른쪽여백:0 들여쓰기:10 줄간격:150%

본 논문의 구성을 다음과 같다. 2장은 관련연구로 추천 시스템의 필요성과 중요성에 대하여 논하고 추천 시스템의 대표적 추천 기법인 협업 필터링에 대해 기술한다. 또한 최근의 NoSQL의 중요성이 커짐으로 인하여 그 관심이 증폭되고 있는 그래프데이터베이스를 소개하며, 분산 그래프데이터베이스의 최근 연구 동향을 살펴본다. 3장에서는  본 논문에서 제안하는 분산 그래프 데이터 저장 모델에 대해 자세하게 기술한다. 4장에서는 기존 데이터 저장 모델과 제안 저장 모델을 기반으로 작동하는 추천 시스템들을 클라우드 환경에서 구현하고 이를 기반으로 실시한 성능 평가에 대해 논한다. 마지막으로 5장에서는 결론에 대해 기술하고 본 연구가 갖는 한계점 및 향후 연구에 대하여 기술한다.

Ⅱ. 관련 연구

소제목: 2.1 등으로 표기  글자모양:중고딕, 크기 :11, 장평:90, 자간:-6 단모양: 문단위:0, 문단아래:0,

여백왼쪽:0, 오른쪽여백:0 왼쪽정렬,

들여쓰기:0 줄간격:150%

2.1 추천 엔진과 협업 필터링

구글이나 네이버등과 같은 사이트들의 일반적인 검색 엔진과 달리 추천 시스템은 개인 사용자의 성향이나 선호도 등을 고려하여 보다 개인화된 정보 서비스를 제공하는데 그 목적이 있다. 따라서 1990년대에 본격적으로 시작된 추천 시스템에 대한 연구들은 지금까지도 꾸준히 발전 해 오고 있으며, 그 중요성과 필요성이 계속적으로 증가함에 따라 앞으로도 더욱 발전할 것으로 예상된다. 추천 시스템을 위한 개인화 기법으로는 크게 규칙 기반 필터링(Rule-based Filtering), 학습 에이전트, 마지막으로 협업 필터링기법으로 정의 할 수 있다. 이 중 협업 필터링은 추천 시스템 분야에서 가장 성공적인 추천 기법으로 거의 모든 추천 시스템에 적용되고 있다. 협업 필터링의 핵심은 추천 대상이 되는 사용자와 유사한 다른 사용자들을 찾고, 이들 유사 사용자 집단에서 높이 평가된 아이템을 추천 하는 것이다.

기존의 많은 추천 시스템 관련 연구들은 주로 협업필터링 기법을 확장하여 선호도 예측의 정확도와 추천 능력을 향상시키기 위한 기법들을 제안하였다. 대표적으로 Saewar은 데이터의 희박성(Sparcity)으로 인한 추천 성능 저하를 해결하기 위한 추천 기법을 제안하였으며, Kim은 K-means 클러스터링 기법을 협업 필터링기법에 적용하여 추천 정확도를 높이 고자 했다[5]-[8]. 최근까지 진행되고 있는 추천 시스템 관련 연구들 역시 개인 사용자에게 보다 적합한 추천 서비스를 제공하기 위해 협업 필터링 기법을 확장한 다양한 형태의 추천 기법들을 제안하고 있다. 결론적으로, 추천 시스템의 성능을 높이려는 대부분의 기존 연구들은 추천 항목에 대한 정확도를 높이려는 연구가 대부분이다. 즉, 증가하는 데이터의 양을 고려하여 추천 시스템의 성능을 높이려는 연구는 아직 까지 미미한 실정이다.

2.2 NoSQL

소셜 네트워크 서비스 등의 등장으로 급속히 증가하는 비정형 데이터의 처리와 저장을 지원하는 데이터베이스들을 통칭하여 NoSQL(Not only SQL)라 부른다[10]-[12]. NoSQL은 테이블기반의 기존의 관계형 데이터가 아닌 다양한 형태의 데이터를 효율적으로 처리할 수 있는 구조와 유연성을 갖춘 분산 데이터베이스 관리 시스템이라 할 수 있다[11].  NoSQL은 데이터 저장 모델에 따라 컬럼 패밀리 스토리지, 문서 기반 스토리지, 키/밸류 기반 스토리지, 마지막으로 그래프 데이터베이스로 나뉜다. 컬럼 패밀리 스토리지 기반 NoSQL의 대표적인 사례인 빅테이블은 구글의 다양한 서비스에서 사용되고 있으며 대량의 데이터 저장과 처리에 용이하다고 알려져 있다[13]. 문서기반 NoSQL로는 SNS의 대표 성공 사례인 트위터에서 사용하고 있는 Mongo DB와 Couch DB등이 있다[15][16]. 키/밸류 기반 NoSQL에는 페이스북의 카산드라(Casandra)가 대표적인 사례이다. 그래프 기반 NoSQL은 앞서 나열한 NoSQL들과 달리 아직 까지 비즈니스 영역에서 활발하게 시장이 활성화되지 않고 있으며 적용 사례 또한 흔하지 않다. 그러나 최근 들어 그래프 데이터베이스는 소셜 네트워크 서비스나 추천 시스템등 데이터간 연관성이 중요하게 고려되는 영역에서 가장 적합한 저장 데이터 모델로 알려지면서 그래프데이터베이스와 관련된 연구들이 활발히 진행되고 있다. 대표적인 사례로 Neo Technology 사의 Neo4j가 손꼽힌다[18].

2.3 분산 그래프 데이터베이스

분산 컴퓨팅 분야는 지난 수년간 꾸준히 연구되어오고 있으며 분산 시스템의 성능을 높일 수 있는 많은 기법들이 제안되어왔다. 최근 [00]에서는 전체 시스템의 부하를 고루 분산하여 시스템의 신뢰성을 높이는 분산 기법이 제안되었다. 그러나 분산 그래프 데이터베이스의 경우 최근에 들어서야 활발히 연구되는 단계이므로 아직 까지 해결해야할 이슈들이 많다고 할 수 있다.

그래프 데이터베이스는 매우 다양한 영역의 데이터를 네트워크 구조를 갖는 그래프에 저장하고 이들 데이터에 대한 고수준의 접근성을 제공한다. 그래프 데이터베이스는 기본적으로 노드와 노드간 관계를 의미하는 에지, 그리고 노드에 저장된 데이터와 이들 데이터간 관계를 기술하는 속성으로 구성된다. 또한 다양한 탐색 알고리즘 적용을 통해 그래프 상에서의 질의를 처리하게 된다.

그래프 데이터베이스는 기존 NoSQL과 뚜렷히 구별되는 특성들을 지닌 것으로 알려져 있다. 특히, 그래프 데이터베이스는 다른 NoSQL들과 달리 데이터 규모나 가용성보다 데이터 간 연관성이나, 데이터 간 관계 분석 등에 사용 목적이 있다고 할 수 있다. 실제로 그래프 데이터베이스는 생물정보학, 추천 엔진, 그리고 소셜 네트워크나 클라우드 분석등 데이터 간 관계를 데이터 자체보다 중요하게 여기는 분야에서 사용된다. 그러나 시스템의 가용성과 데이터 규모 등을 고려하지 않는 기존의 그래프 데이터베이스는 방대한 양의 웹 데이터를 처리하기에 많은 한계점을 지니고 있다.

또한 그래프 데이터베이스 상에서의 검색은 질의어에 부합하는 속성을 갖는 노드나 노드간 특정 관계를 찾아내는 것을 목적으로 한다. 검색의 효과적인 수행을 위해서 다양한 형태의 인덱스 기법들을 그래프 데이터베이스에 적용할 수 있다. 그러나 일반적으로 사용되는 기존 인덱스 기법들과 달리 데이터 자체를 나타내는 노드 정보뿐만 아니라 데이터간 관계를 의미하는 에지 정보 또한 고려하여 색인을 수행하여야 한다. 그래프 데이터베이스 기반의 검색과 색인 기법들은 비교적 생물정보학 분야에서 활발히 진행되어왔다. 그러나 SNS나 전자 상거래 등에서 발생하는 웹 데이터를 저장하고 처리하는데 이들 기법들을 적용하기에는 적합하지 않다. 그러므로 웹에서 발생하는 비정형 데이터를 처리하고 저장하는 그래프 데이터베이스에 적합한 검색 기법과 색인 기법에 대한 연구가 필요한 실정이다.

최근 들어 그래프 데이터베이스에 대한 관심이 증폭되면서 관련 연구도 활발히 진행되고 있다. 이들 대부분은 앞서 기술한 문제점을 해결하기 위한 분산 기반의 그래프 데이터베이스에 관한 연구들이다. 대표적으로 Li-Young은 대규모 소셜 컴퓨팅을 위한 분산 그래프 데이터 저장 시스템을 제안하였다. 그의 연구에서는 Front end, Middleware, 그리고 Backend Store의 3개 층으로 구성된 분산 시스템을 구현하고 소셜 컴퓨팅에서 널리 사용되는 페이지랭크 등의 알고리즘들을 적용해 봄으로써 분산 그래프 데이터 저장 시스템이 시스템의 성능을 높일 수 있음을 보였다. 상용화된 대표적인 분산 그래프 데이터베이스로는 마이크로소프트사의 Trinity를 꼽을 수 있으며 오픈 소스 프로젝트로는 Titan등이 있다. 이밖에도 클라우드 환경에서 대규모 데이터를 효과적으로 처리하기 위한 연구들도 있다. 그러나 이들 상용 SW나 관련 연구 대부분은 계속적으로 증가하는 대량의 그래프 데이터를 저장하는데 주로 초점을 두고 있다. 따라서 그래프에 속한 데이터간 연관성 분석과 같은 대규모 시스템의 성능을 높이기 위한 컴퓨팅 기법에 대한 연구 사례는 아직 까지 미미하다.

Ⅲ. 대규모 추천 엔진을 위한 분산 그래프 데이터 저장 시스템

기존의 많은 추천 시스템들의 추천 기법들은 관계형 데이터베이스에 저장된 데이터들을 토대로 작동되었다. 그러나 테이블 간 조인 연산을 요구하는 관계형 데이터베이스는 추천 시스템의 성능 저하를 야기 한다고 알려졌다[12]. 또한 방대한 양의 웹 데이터를 토대로 하는 추천 기법이 효과적으로 적용되기 위한 분산 그래프 데이터 저장 모델의 필요성이 증대되고 있지만 이와 관련된 연구는 아직 알려진 바가 없다. 따라서 본 논문에서는 그래프 데이터베이스 기반의 대규모 추천 엔진을 위한 분산 그래프 데이터 저장 시스템을 제안한다.

본 연구에서는 관련연구에서 소개된 Li-Young의 [00]에서 제안한 3개 층의 분산 저장구조를 확장하여 추천 시스템에 적합한 새로운 분산 저장 구조를 정의 한다.

.

그림 1. 대용량 추천 시스템을 위한 분산 그래프 데이터 저장 시스템 구조

Fig. 1. The architecture of distributed graph data storage system for large-scale recommender systems

그림과 표 안 영문표기만 가능합니다.

그림 1은 본 논문에서 제안하는 대규모 추천 엔진을 위한 분산 그래프 데이터 저장 모델 기반 시스템의 전체구조를 나타낸다. 전체 구조는 크게 세 개의 단계인 Front end, Middleware, 그리고 Backend Store로 구성된다. 먼저, Front end 단계는 사용자와의 인터페이스를 구현하는 단계로, name server와 유사 사용자 노드에 대한 색인인 유사 사용자 인덱스로 구성된다. name server는 사용자로부터 노드 아이디(Node Identification)를 키워드로 하는 질의어를 전달받아 해당 질의어에 부합하는 노드들의 저장 위치를 similar user index로부터 가져온다. 유사 사용자 인덱스는 본 연구의 토대라 할 수 있는 [9]에서 제안된 색인기법으로 그래프 데이터베이스 기반의 추천 시스템의 성능을 보다 효과적으로 개선할 수 있음을 보였다.

그림 2는 [9]에서 제안된 유사 사용자 인덱스의 구조를 보인다. 유사 사용자 인덱스는 B-트리를 기반으로 구현되었으며 말단에는 각 특정 사용자 노드와 유사한 사용자 노드들의 노드 위치 정보가 저장 되어 있다. 협업 필터링 기법은 특정 사용자와 비슷한 성향을 가진 유사 사용자들을 기반으로 추천 목록을 구성한다. 전체 그래프에서 유사 사용자 노드들을 찾아 이를 따로 인덱스에 포함하기 위해 [9]에서는 협업 필터링 알고리즘을 분석하여 유사 사용자로 추출될 확률적 요소들을 정의하고 이를 기반으로 유사 사용자 노드들을 인덱스로 미리 구성하였다.

그림캡션: 글자모양:중고딕, 크기 :9, 장평:90, 자간:-6 단모양: 문단위:0, 문단아래:0, 여백왼쪽:0, 오른쪽여백:0 왼쪽정렬, 들여쓰기 : 0 줄간격 :130%, 가운데정렬

그림, 표, 식과 글사이는 한줄을 띄웁니다.

그림 2. 유사 사용자 색인

Fig. 2. Similar user index

표 1. 실험 데이터 세트

Table 1. Experimental data sets

Data type Number of data	User	Movie content	Evaluation points
2,000	1,500	500	54,032
4,000	3,000	1,000	84,000
6,000	4,000	2,000	354,003
8,000	5,000	3,000	754,004
9,940	6,040	3,900	1,000,209

표캡션: 글자모양:중고딕, 크기 :9, 장평:90, 자간:-6 단모양: 문단위:0, 문단아래:0, 여백왼쪽:0, 오른쪽여백:0

왼쪽정렬, 들여쓰기 : 0

줄간격 :130%, 왼쪽정렬

표 1은 5개의 실험 데이터 세트를 보인다. 평가 점수는 사용자 A가 영화 콘텐츠 B에 대해 직접 부여한 평가 점수로 그래프 데이터베이스에서는 사용자 노드와 콘텐츠 노드의 관계를 구성하는 에지의 속성 값으로 나타낼 수 있다.

4.3 성능 평가

제안한 분산 그래프 데이터 저장 시스템의 성능 평가를 위해서 본 연구에서는 관계형 데이터베이스 기반의 추천 엔진과 제안 저장 시스템 기반의 추천 엔진을 구현하고 이들 각각의 추천 알고리즘의 수행 시간을 측정한다.

제안 기법과 RDB 기반의 추천 엔진의 성능은 매우 뚜렷한 차이를 보인다. 특히, 데이터의 크기가 커져감에 따라 RDB 기반의 추천 엔진 경우, 추천 항목 구성 시간도 비례하여 증가하는 반면, 제안 시스템 기반의 추천 엔진은 데이터 크기의 상관없이 비교적 일정한 추천 항목 구성 시간이 걸리는 것을 보였다.

식은 왼으로 정렬 식번호는 오른으로 정렬.

[eqn: hat{f} (x,y)`=`median` _{(s,t)` IN Sxy} ` LEFT { g`(s,t) RIGHT }]           (1)

Ⅴ. 결론 및 향후 과제

폭발적인 온라인 데이터의 증가는 원하는 정보를 얻고자하는 사용자들과 이들 사용자를 대상으로 하는 사업자들에게 다양한 형태의 많은 불편함과 문제점들을 야기했다. 이러한 문제점들을 해소하기 위한 목적으로 등장한 다양한 형태의 추천 시스템들 역시 히스토리 데이터와 같은 저장하고 처리해야할 사용자 데이터가 증가함에 따라 성능이 저하되는 문제점에 직면하게 되었다.

본 논문에서는 대규모 추천 시스템의 추천 성능을 보다 효과적으로 높이기 위한 새로운 분산 그래프 데이터 모델을 제안하였다. 이를 위해 대량의 사용자 데이터를 처리함에 있어서 추천 항목에 대한 정확도를 유지하고 검색 시간을 단축하기 위해 새로운 형태의 유사 사용자 인덱스가 적용된 그래프 데이터 저장 시스템을 구현 하였다. 제안 시스템의 비교 성능 평가를 위해 관계형 데이터 베이스기반의 추천 엔진과 제안 시스템 기반의 추천 엔진을 각각 구현하고 추천 항목 구성 시간을 측정해 봄으로써 제안 시스템이 기존 관계형 데이터베이스보다 효과적으로 대규모 추천 엔진의 성능을 높일 수 있음을 보였다.

본 논문에서는 이전에 시도된 바 없던 대규모 추천 엔진을 위한 분산 그래프 데이터 저장 시스템을 제안 및 구현하고 추천 시스템의 성능을 높일 수 있음을 입증하였다는 점에서 연구에 의의를 찾을 구 있다. 그러나 제안 시스템에서 적용된 파티션 기법이 전체 시스템의 성능에 미치는 내용등과 관련한 실험이 이루어지지 않았다는 점과 기존 분산 그래프 데이터 저장 시스템들과의 적절한 비교 평가가 이루어지지 않았다는 점 등에서 본 연구의 한계를 찾을 수 있다. 따라서 이들 한계점을 극복하기 위한 연구를 본 논문의 향후 과제로 한다.

References

[1] D. S. Kim and Y. W. Chung, "Message delivery considering quality of service in delay tolrerant network", Journal of KIIT, Vol. 10, No. 11, pp. 121-127, Nov. 2012.

[3] G. Linden, B. Smith, and J. York, "Amazon.com recommendations: item-to-item collaborative filtering", Internet Computing, IEEE, Vol. 7, No. 1, pp. 76-80, Feb. 2003. https://doi.org/10.1109/MIC.2003.  1167344.

[4] Paul. C. Krause and Oleq Wasynczuk, "Electro mechanical Motion Devices", McGraw-Hill, pp. 23-45, May 1998.

[5] IRTF Delay Tolerant Networking research group, http://www.dtnorg.org. [acessed: Jan. 05, 2016]

저자소개

참고문헌: 글자모양 - 영문:Times New Roman, 크기 :10, 장평:90, 자간:-6

(저자, 저서명 문단모양- 줄간격 : 150%, 내어쓰기 : 15

References 형식 : 모두 영문표기

<저서>

저자명, “저서명”, 출판사, pp. 10-13, 월, 년도. DOI.

<저자명표기>

[1] W. Willinger, M. S. Taqqu, and A. Erramilli

<DOI 표기>

예 https://doi.org/10.1109/MIC.2003.1167344

(1) Journal Article

[1] D. W. Ryoo and C. S. Bae, "Design of The Wearable Gadgets for Life-Log Services based on UTC", IEEE Transactions on Consumer Electronics, Vol. 53, No. 4, pp. 1477-1482, Nov. 2007.

(2) Book

[1] H. K. Hartline, A. B. Smith, and F. Ratlliff, "Inhibitory interaction in the retina", In Handbook of Sensory Physiology, Springer-Verlag, pp. 381-390, 1972.

(3) Conference Proceedings

[1] Y. Yamamoto, S. Machida, and K. Igeta, "Micro-cavity semiconductors with enhanced spontaneous emission", Proc. 16th European Conf. on Opt. Commun., Amsterdam, The Netherlands, pp. 3-13, Sept. 1990.

(4) Patents

[1] C. E. Larsen, R. Trip, and C.R. Johnson, Methods for procedures related to the electrophysiology of the heart. U.S. Patent 5,529,067, June 25, 1995.

(5) Web URL

[1] INRIA Person Dataset: http://pascal.inrialpes.fr/data/human/. [accessed: Nov. 04, 2015]

* References 는 본문내에서 순서대로 나와야 합니다.

* References 는 8개이상(2개는 국제논문)

Representation of On-Board Pattern at Every Move in Go Games

영문제목: 글자모양 : 견명조, 크기:15, 장평:90, 자간: -7

문단모양 : 문단위:10, 문단안래:10, 줄간격 : 130%

영문저자명: 글자모양 : 휴먼명조, 크기:10, 장평:90,

자간: 5 문단모양 : 문단위:10, 문단안래:10, 줄간격 : 130%

저자가 3명 이상일 경우 마지막저자는 , and로 표기

투고논문양식(저자정보없음)

*

*

연구지원문구: 글자모양 : 휴먼명조, 크기:9.2, 장평:90, 자간: 5 문단모양 : 문단위, 문단안래:0, 줄간격 : 130%

Abstract

Here, we define the pattern on a go-board which has a tengen-pattern and tengen centered 9 square-patterns using the (area, level, offset) coordinate system. In addition to designing a data structure for go-game display that efficiently manages the liberties of connected moves for the purpose of modifying board pattern after taking out moves, we implement a game-browsing program which identifies group of connected moves to be taken out and then adjusts pattern value for taken out moves to board pattern immediately at each addition of a move to the go board. We discuss necessary conditions for the application of board pattern to pattern database. We show data for the connected moves and taken moves obtained by running above program for 300 games by pro-players.

영문요약문: 7줄~8줄이내 글자모양 - 영문:Times New Roman, 크기 :9.2, 장평:90, 자간:-6 단모양: 문단위:0, 문단아래:0, 여백왼쪽:10, 오른쪽여백:10

줄간격 : 150%

요  약

요약본문: 7줄~8줄이내 글자모양 - 휴먼명조, 크기 :9.2, 장평:90, 자간:-6 문단모양: 문단위:0, 문단아래:0, 여백왼쪽:10, 오른쪽여백:10 줄간격 : 150%

바둑판 위의 패턴을 (영역, 레벨, 거리) 좌표계를 사용하여, 천원과 천원을 중심으로 하는 9개의 사각형패턴으로 정의하였다. 사석제거 후의 패턴 수정을 위해 반상의 연결된 돌들의 공배를 효율적으로 관리하는 기보표시 자료구조를 설계하여, 기존의 게임기록파일로부터 반상패턴을 생성 시, 착수 시점별로 제거되어야 하는 연결된 돌들의 군을 알아내어, 반상패턴의 제거된 돌들에 대한 패턴 값을 바로 조정하는 기보표시프로그램을 구현한다. 착수시점별 반상패턴의 응용을 위한 필요조건에 대해 다룬다. 위 프로그램을 사용하여 프로 선수가 둔 300국의 바둑게임에서 연결된 돌 및 사석제거에 관한 조사 결과를 보인다.

Keywords: 영문으로만 작성

약자를 제외하고는 모두 소문자로 작성하고, 개수는 반드시 4~6개로 작성

글자,문단: 영문요약과 동일

Keywords

adaptive neural network control, robot System, GFN, actuator failure, uncertainty

Representation of On-Board Pattern at Every Move in G

Journal of KIIT. Vol. 23, No. 0, pp. 00-00, 00 00, 2025. pISSN 1598-8619, eISSN 2093-7571

편집용지(모양): 사용자정의 폭L 190, 길이: 260 위:17.5, 아래 17.5 dhfmsWHr: 20, 왼쪽:20, 머리말:10, 꼬릿말 : 0

*	□

각주(저자소속): 글자모양: 휴먼명조, 크기:8.2,

장평:100, 자간:-8, 줄간격:125%

Ⅰ. Introduction

바탕글 : 본문내용 - 글자모양:휴먼명조, 크기:10, 장평:90, 자간:-6 단모양: 문단위:0, 문단아래:0, 여백왼쪽:0, 오른쪽여백:0 들여쓰기:10 줄간격:150%

각장제목: 글자모양: 휴먼고딕,

크기:11, 장평:90, 자간:-6 단모양:여백왼쪽:0, 오른쪽여백:0

문단위, 문단아래: 0

줄간격: 150%, 장제목 위아래 한줄위아래 한줄띄기

가운데정렬

Detecting human has attracted a lot of research interests in recent years, due to the drive from many emerging applications, such as perceptual interfaces, ubiquitous computing, and smart video surveillance [1]-[3]. Different applications are concerned with different image resolutions of the subjects, thus requiring different techniques. For example, in perceptual interfaces, the motions of the human body parts need to be determined for action recognition; thus this application require fairly high resolution for

analyzing the articulated motion of the body parts. In contrast, in many video surveillance applications, such as robot vision for inspection since the human typically is associated with small region and low resolutions, the human needs to be treated as a non-rigid entity for detection, while detailed motion of the body parts is no longer the major focus here. This paper addresses effective feature selection in the detection problem. In computer vision field, human detection is considered as a difficult problem, due to the variation of human appearances in image. The complexity of the problem is added with the cluttered and dynamic background. In this paper we consider human detection by placing this problem as a classification problem, solving with a discriminative approach through the supervised learning. Being in this manner, the human detection requires two components: a set of features and a discriminative learning method. It is important to have features that can robustly represent the appearance of object in interest i.e. human, while optimally separates human from others e.g. windows, chairs etc. To classify these features, we also need a strong discriminative learning algorithm, which offers proper generalization and bring a desirable separation line between object and non-object. As shown in[4], Histogram of Oriented Gradient (HOG) has been successfully trains the Support Vector Machines (SVM) to detect human in images with an acceptable performances. This success, in one aspect, might be considered as the fruits of the success of the feature to model the observed object as an instance of a specific class. Given a discriminative set of features, SVM will give a good generalization and consequently provides a well classifier. However, finding a representative feature to cover every variation of pose and appearance of human in image is considered to difficult. It is also interesting to use redundant features for human detection problem, and employs AdaBoost algorithm to learn important features, while avoiding the rest to be considered in the model[5]. The HOG, as shown in[6], one of the recent robust features set for human detection problem (one can refer to Region Covariance[5] as an alternative) that encodes the object’'s shape by using gradient structure, and then captures the object spatial information by grid quantization and local normalization. This procedure lets HOG committed the illumination invariance as its property. Regarding to the two main components of human detection in supervised learning approach, the remainders of this paper are mainly discussed about two issues. The first one is the evaluation of several variant of Histogram of Oriented Gradient[4], so called HOG-family, as a robust features set for discriminating human from other objects. This includes the non-overlapped, dense [4], spatial pyramidal[6] and our new proposed HOG feature: multi-scale image pyramid HOG. The systematic comparison within HOG-family along various combinations with SVM shall provide experimental validation of the most discriminative feature within HOG-family. The second issue is the discussion about speeding-up the performance of SVM evaluation, trained by the HOG-family, by firstly reducing the features dimension through Principal Component Analysis (PCA). This reduction is expected to affect the speed of testing phase of SVM, while preserving the classification quality.

This paper is organized as follows. In Section 2, we describe the HOG-family as features, along with SVM as the classifier. The incorporation of PCA for feature dimension reduction with SVM is presented afterwards. The data sets and the performance measure are outlined in Section 3, with comparison and analysis as closing notes. Finally, conclusion and outline for future research direction is drawn in Section 4.

서론부터 단을 2단으로 작업합니다.

Ⅱ. Features and the classifier

In this section we briefly introduce the HOG as our discriminative feature for dealing with the human detection problem. Afterwards, we discuss the basic concept of SVM and how PCA are incorporated into SVM for feature dimensional reductions. The SVM under PCA transformation is proven to be invariant, by then it is safe to improve SVM evaluation along PCA.

소제목: 2.1 등으로 표기  글자모양:중고딕, 크기 :11, 장평:90, 자간:-6 단모양: 문단위:0, 문단아래:0,

여백왼쪽:0, 오른쪽여백:0 왼쪽정렬,

들여쓰기:0 줄간격:150%

2.1 HOG Family

The utilization of orientation histogram as shape encoding descriptors has been used in[8] for hand gesture recognition. Later it was developed into robust local feature descriptors known as SIFT[9]. In SIFT, the features are computed at a sparse set of scale-invariant key points, rotated to align their dominant orientations and used individually. The HOG as proposed by[4][10], are computed in dense grids at a single scale without dominant orientation alignment. The grid position of the block implicitly encodes spatial position relative to the detection window in the final feature vector. In addition to dense HOG [4], the experiment is also performed to evaluate non- overlapped HOG as the basic HOG variant,

The HOG-family features are shown in Fig. 1 and briefly described as follows:

1. Non-overlapped. This is the simplest HOG representation. Histogram of each cell is normalized with the block norm.

2. Overlapped (dense). This is similar to the implementation in [4], and it uses the overlapped blocks as the basic descriptor.

3. Spatial pyramid. The pyramid of HOG is built by using different cells of each pyramid level and then the concatenated histogram is composed of feature data in each level.

4. Multi-scale. The image pyramid levels are created from the image and the histogram is calculated at each level. By then, the feature vector is built by the concatenation of histogram from different levels. In this implementation, we combine two different level of image pyramid to build the HOG feature.

그림, 표, 식과 글사이는 한줄을 띄웁니다.

그림캡션: 글자모양:중고딕, 크기 :9, 장평:90, 자간:-6 단모양: 문단위:0, 문단아래:0, 여백왼쪽:0, 오른쪽여백:0 왼쪽정렬, 들여쓰기 : 0

줄간격 :130%, 가운데정렬

Fig. 1. HOG-Fmaily features for human detection

2.1.1 Building HOG from image

Let I denote an image of width [eqn: m] and [eqn: I(x,y)] represent the pixel intensity in corresponding position [eqn: (x,y)], then the HOG descriptor can be computed by the following steps:

1. Perform image enhancement through gamma correction.

2. From image [eqn: I], we compute image gradient in horizontal and vertical directions by one dimensional entered mask[eqn: LEFT [ -1`0`1 RIGHT ] ^{T}]. By then, we have following formulations for image gradient in each point:

식은 왼으로 정렬 식번호는 오른으로 정렬.

[eqn: g _{x} (x,y)=I(x+1,y)-I(x-1,y)# # g _{y} (x,y)=I(x+1,y)-I(x-1,y)]            (1)

where [eqn: g _{x} (x,y)] and [eqn: g _{y} (x,y)] denote the  horizontal and vertical components of the image gradient respectively.

3. The magnitude [eqn: m(x,y)] and the orientation [eqn: theta (x,y)] of image data from its gradient can be calculated as follows:

[eqn: m(x,y)= sqrt {g _{x} (x,y) ^{2} +g _{x} (x,y) ^{2}}# # theta (x,y)=tan ^{-1} (g _{x} (x,y)/g _{x} (x,y))]           (2)

The orientation [eqn: theta (x,y)] has values in [eqn: LEFT [ 0,2 pi RIGHT ]]range.

4. We dvide the image into [eqn: S _{w} XS _{h}] non-overlapping cells. For each cells, we quantize the orientation [eqn: theta (x,y)] for all pixels into [eqn: s _{`b}] orientation bins weighted by its magnitude [eqn: m(x,y)].

5. The feature is  normaalized by the sum of blocks. In all HOG variant, we use a magnitude of a block of [eqn: 2 TIMES 2] cells to normalize each of cells. By blocks normalization we capture the information in the surroundings cells also included. We divide the image into [eqn: S _{w}]-by-[eqn: S _{h}] non-overlapping cells. For each cells, we quantize the orientation [eqn: theta (x,y)] for all pixels into [eqn: s _{`b}] orientation bins weighted by its magnitude [eqn: m(x,y)].

6. The histogram from each cell is formed into one feature vector depends on the configuration required for each HOG variant as shown in Fig. 1.

The output of this procedure per each image is 1-by-N feature contains normalized both image magnitude and orientation, which is considerably robust, compact and illumination invariant[4][10].

3.3 Experimental results

We only use one run phase of training without re-training by augmenting images from false positives obtained with initial training set as used in[8]. The test phase is performed on normalized positives images. Although this might seems restrictive, we may rely on an assumption that given the generalization of the SVM and proper choice of training data sets, if a feature perform well in this data sets then it will perform comparably well in the multi-scale detection schema as used in practice[4][8]. The evaluation will be performed under some fixed HOG parameters. For our data set (detection of 48x48 upper body), each cells size is 12x12 pixels, blocks is defined by 2x2 cells with stride is 12 pixels in both direction (for dense type). We use 249 positives and 953 negatives images for training. The testing data sets contain 100 positives and 7332 negatives. To evaluate performances of PCA-SVM we use two projection sizes: one-third and one-sixth of original feature size. This is shown in Table 1. The SVM training and test are performed using svmlight with default parameters and RBF as the kernel.

표캡션: 글자모양:중고딕, 크기 :9, 장평:90, 자간:-6 단모양: 문단위:0, 문단아래:0, 여백왼쪽:0, 오른쪽여백:0

왼쪽정렬, 들여쓰기 : 0

줄간격 :130%, 왼쪽정렬

Table 1. Full and PCA projected size of the feature sets

HOG-type	Full size	1/3	1/6
Non-overlap	144	48	24
Dense	324	108	54
Spatial pyramid	189	63	31
Multi-scale	288	96	48

The performances of HOG-family in PR curves can be seen in Fig. 3. For full size feature, at 0.8 precision, multiscale-HOG which we propose has better recall compared to other HOG variant including dense-HOG from[4][8]. We also can see that PCA reduces performance significantly in 1/6 feature size and for 1/3 feature size, dense-HOG and multi-scale- HOG have comparable performance compared to full feature size. To make this clear, Fig. 4 shows the comparison of full feature size and 1/3 PCA projected feature for dense HOG and multi-scale HOG. To show the advantage of PCA-SVM the processing time to extract feature and the runtime of the test phase for test data set are shown in Table 2. We only consider dense and multiscale since the performance.

References

[1] D. S. Kim and Y. W. Chung, "Message delivery considering quality of service in delay tolrerant network", Journal of KIIT, Vol. 10, No. 11, pp. 121-127, Nov. 2012.

[3] G. Linden, B. Smith, and J. York, "Amazon.com recommendations: item-to-item collaborative filtering", Internet Computing, IEEE, Vol. 7, No. 1, pp. 76-80, Feb. 2003. https://doi.org/10.1109/MIC.2003. 1167344.

참고문헌: 글자모양 - 영문:Times New Roman, 크기 :10, 장평:90, 자간:-6

(저자, 저서명 문단모양- 줄간격 : 150%, 내어쓰기 : 15

References 형식 : 모두 영문표기

<저서>

저자명, “저서명”, 출판사, pp. 10-13, 월, 년도. DOI.

<저자명표기>

[1] W. Willinger, M. S. Taqqu, and A. Erramilli

<DOI 표기>

예 https://doi.org/10.1109/MIC.2003.1167344

(1) Journal Article

[1] D. W. Ryoo and C. S. Bae, "Design of The Wearable Gadgets for Life-Log Services based on UTC", IEEE Transactions on Consumer Electronics, Vol. 53, No. 4, pp. 1477-1482, Nov. 2007.

(2) Book

[1] H. K. Hartline, A. B. Smith, and F. Ratlliff, "Inhibitory interaction in the retina", In Handbook of Sensory Physiology, Springer-Verlag, pp. 381-390, 1972.

(3) Conference Proceedings

[1] Y. Yamamoto, S. Machida, and K. Igeta, "Micro-cavity semiconductors with enhanced spontaneous emission", Proc. 16th European Conf. on Opt. Commun., Amsterdam, The Netherlands, pp. 3-13, Sept. 1990.

(4) Patents

[1] C. E. Larsen, R. Trip, and C.R. Johnson, Methods for procedures related to the electrophysiology of the heart. U.S. Patent 5,529,067, June 25, 1995.

(5) Web URL

[1] INRIA Person Dataset: http://pascal.inrialpes.fr/data/human/. [accessed: Nov. 04, 2015]

* References 는 본문내에서 순서대로 나와야 합니다.

* References 는 8개이상(2개는 국제논문)

[4] Paul. C. Krause and Oleq Wasynczuk, "Electro mechanical Motion Devices", McGraw-Hill, pp. 23-45, May 1998.

[5] IRTF Delay Tolerant Networking research group, http://www.dtnorg.org. [accessed: Jan. 05, 2016]

Authors