이 장에서는 제안 모델의 이해를 돕기 위해 본 논문의 모델과 비슷한 관련 연구에 대하여 설명한다. 또한, 기존 연구와 본 연구와의 차이점을 설명한다.

본 논문에서는 구글의 위도와 경도에 기반을 둔 2차원 ID인 S2의 셀 레벨 16을 사용하였고, 이때 한 셀이 커버하는 범위는 약 150m×150m 정도이다. Wu 외 5인[7]의 방안은 로우 키(row key)에 날짜와 시간 구글 S2의 셀 레벨 12를 사용하여 공간을 표현하였다. 구글 S2 셀이란 공간 인덱싱 모델 중 하나로 지구 전체를 그리드 형태로 커버하는 모델이다. 이 모델은 1~30레벨로 나누어져 있고, 레벨의 숫자가 높을수록 커버하는 범위가 좁아 섬세하게 공간을 표현할 수 있다. 하지만 너무 작은 셀을 사용하면 질의 응답 속도 지연과 메모리 과부하 현상을 초래할 수 있다.

각 셀은 64비트의 고유한 셀 아이디를 갖는다. [7]의 연구에서 사용된 셀 레벨 12는 한 셀이 커버하는 범위가 약 2km×2km로 세밀한 측정이 불가하다는 단점이 있다. Fox 외 3인[8]의 방안은 공간은 GeoHash[9]를 사용하여 인덱싱하고 시간과 함께 인덱스 키에 넣었다. GeoHash는 문자가 길어질수록 세밀한 공간을 커버할 수 있으며, 1~9문자 중 [8]은 150m×150m를 커버하는 7문자를 사용하였다. UQE-Index[10]는 B+-tree와 R-tree를 결합한 하이브리드 인덱싱 방안이다. 3D R-tree[11]는 3D-tree 기반의 인덱스 방안이다. KD-tree[12]는 k개의 차원을 가진 이진 트리이다. 각 노드에 위도, 경도, 시간을 넣어서 트리 구조를 생성하였다. 셀 레벨 16으로는 트리가 생성되지 않아 셀 레벨 15로 공간을 표현하였다.

그러나 위 연구들은 IoT 데이터 검색에 특화된 인덱스 모델이고 본 논문의 제안방안은 사용자 질의처리에 관한 대용량 데이터를 신속하게 분석하는 연구로 비교하기에 적합하지 않다. 비슷한 연구인 [5]의 제안방안을 다음 2.2절에서 설명한다.

이번 절에서는 제안방안에서 다룰 모델의 기존방안과 문제점에 대하여 설명한다.

이 연구는 [5]의 방안으로 2.1절의 관련 연구와 달리 분석에 관한 연구로 특정 시경계, 특정 도로, 도시 전체의 시경계, 도시 전체의 도로, 사용자 지정(원, 사각형, 다각형, 선) 등 다양한 지역과 사용자가 원하는 날짜를 웹을 통해 입력받아 분석 결과를 사용자에게 시각적으로 제공한다. 그림 1은 [5]의 방안으로 위에서 기술한 다양한 질의들을 하나의 인덱스로 제공하는 통합 인덱스 모델의 구성도이다. 검색엔진은 수집 서버와 인덱스 서버로 나뉘는데, 수집 서버는 실제 IoT 센서로부터 실시간으로 수집되는 IoT 데이터와 시경계, 도로 좌표 등의 공공 데이터가 몽고디비(MongoDB)에 저장된다. 저장된 모든 3차원 IoT 데이터는 날짜, 시간, 위도, 경도 등의 값을 가지며 상기 값들이 완전하지 않으면 제거된다. 위도, 경도, 시간 축으로 되어있는 이 3차원 공간에 IoT 데이터가 존재하게 되는데 사용자가 웹을 통해 날짜와 지역을 선택하여 질의하면 3차원 공간으로 인덱싱되어있는 데이터베이스에서 빠르게 검색 후 결과를 웹을 통해 시각화한다. 특히 이 인덱스는 5자리의 8진수를 이용하여 2000년~2063년까지 64년분의 데이터를 표현할 수 있으며, 매일 생성되는 데이터를 추가로 쌓을 수 있다.

인덱스 서버는 (1) 수집 서버로부터 주기적으로 새로 추가된 인스턴스 데이터를 가져와서, (2) 불완전한 데이터 제거 및 수집된 데이터의 시간차가 1시간 미만일 경우 같은 트레젝토리(trajectory)로 취급하는 트레젝토리 생성 등의 데이터 정제 작업을 수행한 후, (3) 인덱스 처리를 위해 3차원 시공간 모델에 맵핑하여 해당 IoT 데이터가 저장되는 셀 아이디를 식별한다. (3)의 과정을 전처리 과정이라고 칭한다. (4) 전처리 과정에서 나온 결과들을 바탕으로 셀 아이디의 리스트로 구성된 통합 인덱스 모델을 구축한다. 이렇게 구축된 인덱스 서버에 사용자는 웹을 통하여 지역과 날짜를 질의한다. 이후 셀을 탐지하고 집계, 요약하여 S2 셀을 이용하여 그림 2와 같이 사용자에게 시각적으로 결과를 제공한다.

Fig. 2. 
Visualization results based on user queries

그림 2는 미세먼지 농도의 각 분석 결과이고, 각 질의는 q1은 특정 시경계 즉, 동을 검색한 결과이고, q2는 특정 도로, q3는 히트맵 검색, q4는 전체 시경계 검색, q5는 전체 도로 검색, q6는 전체 히트맵 검색, q7~q10은 사용자가 마우스로 원, 사각형, 다각형, 선 모양으로 드래그하여 선택한 지역의 검색 시각화 결과이다. 색 구분은 0~30은 좋음으로 파란색, 31~80은 보통으로 녹색, 81~150은 나쁨으로 노란색, 151 이상은 매우 나쁨으로 빨간색으로 표현하였다.

표 1은 각 질의 종류별 응답시간이다. 질의하는 지역 즉, 질의하는 공간의 크기에 따라 질의시간에 차이가 있어 각 응답시간은 무작위로 10번의 질의를 통해 얻은 응답시간 평균이다. 대부분 질의 응답시간은 약 1초 내외지만, 시에서 일부분이 아닌 시 전체를 검색하는 q4~q6는 응답시간이 많이 지연되기 때문에 q4~q6를 개선한다.

그림 3은 q4~q6의 과정 중 기존방안의 질의처리 프로세스이다. 그림은 현재 도로명으로 되어있지만, 도로명뿐만 아니라 시경계 검색도 같은 순서를 갖는다. 가장 먼저 웹을 통해 검색하고 싶은 날짜와 전체 또는 부분검색 할 범위를 웹에 입력한다. 과정 (1)은 사용자가 질의한 날짜와 시간에 해당하는 데이터를 데이터베이스에서 불러와 OCT ID 별 S2 ID가 저장되어있는 S_Table을 생성한다. 과정 (2)는 사용자가 질의한 지역에 대해 데이터베이스에서 행정구역별 S2 ID가 저장되어있는 R_Table을 생성한다. 과정 (3)에서는 과정 (1)과 (2)의 결과물을 조인을 사용하여 행정구역명과 OCT ID를 키와 값 쌍으로 생성한다. 과정 (4)는 OCT ID를 이용하여 도로명별 미세먼지의 평균 농도를 집계한다. 이러한 과정 중 과정 (3)과 (4)가 전체 질의 프로세싱 중 약 94%를 차지하는데, 이는 n개의 행을 가진 테이블과 m개의 행을 가진 테이블을 비교하는 과정에서 조인을 사용하기 때문에 테이블의 크기가 커지면 응답시간이 지수적으로 증가하는 문제가 있다. 본 논문에서는 이를 해결하기 위해 해시 함수와 블로킹을 사용하여 선형적인 시간복잡도를 갖는 개선 알고리즘을 제안한다.

Fig. 3. 
Query processor in [5]

이번 절에서는 2.2절의 기존방안에서 지연되는 그림 2의 q4~q6의 질의처리 속도를 개선하는 알고리즘을 제안한다. 기존방안의 q4~q6의 검색 기간을 24시간에서 8개월로 늘렸을 때의 결과는 표 2와 같다.

q4는 질의의 기간을 하루 기준으로 측정했던 것보다 8개월로 기간을 확장해 측정한 결과 응답시간이 약 250%, q5는 약 3,630%, q6는 약 4,850% 증가한 것을 확인할 수 있었다.

그림 4는 해시 함수와 블로킹을 사용한 제안방안의 흐름도이다. R_Table은 행정구역별 S2 ID가 저장되어있는 행정구역 정보 테이블, S_Table은 OCT ID 별 S2 ID가 저장되어있는 인덱스 테이블이다. 먼저 R_Table의 경우 해시 함수에 입력값으로 S2 ID와 행정구역명을 넣으면 출력값은 S2 ID를 키로, 행정구역명과 테이블 명을 값으로 가지는 키, 값 형태의 쌍을 출력한다. 마찬가지로 S_Table의 경우 OCT ID와 S2 ID를 입력값으로 넣으면 S2 ID를 키로 OCT ID와 테이블 명을 값으로 만들어주는 키, 값 형태의 쌍을 출력한다. 통과한 결과를 이용하여 같은 S2 ID 쌍을 그룹화 해주는 블로킹 과정을 거치게 되고 블록별 테이블 명을 확인하여 다를 경우 임시테이블의 한 행에 저장한다. 마지막으로 이렇게 생성된 임시테이블과 인스턴스 테이블을 조인을 통하여 행정구역별 미세먼지 농도의 평균을 집계하게 되는데, 이러한 과정을 거치면 표 3과 같은 결과가 출력된다.

Fig. 4. 
Proposed query processor using the key-value-based hash function and the blocking method

행정구역별 IoT 데이터(미세먼지 농도)의 평균 집계결과인 표 3을 가지고 지도에 시각화 후 그 결과를 웹에 전송하여 사용자는 웹을 통하여 시각화된 결과를 확인할 수 있다. 그로 인해 사용자는 직관적으로 자신이 질의했던 IoT 데이터 결과를 확인할 수 있다.

이 절에서는 기존 연구와 제안방안의 알고리즘과 시간복잡도를 비교한다. 먼저 기존 연구의 질의처리에 대한 알고리즘은 Algorithm 1과 같다.

Line 1은 시경계 명을 키로 S2 ID를 값으로 갖는 키와 값 쌍이고, Line 2는 각 시경계의 OCT ID를 저장하는 키와 값 쌍이다. Line 3은 그림 3의 함수 1의 반환 값이다. Line 1~6은 그림 3의 1번 과정이다. Line 7~11은 각 시경계 명별 OCT ID를 저장하는 그림 3의 3번 과정이다. 따라서 시간복잡도는 Line 4의 n개 행과 Line 5의 m개 행을 조인 연산을 사용하여 비교하기 때문에 O(n) × O(m)과 같다. 시간복잡도가 O(n) × O(m)이기 때문에 n또는 m이 증가하면 응답 속도도 지수적으로 증가한다.

다음 Algorithm 2는 해시와 블로킹 기법을 사용한 제안방안의 질의처리 알고리즘이다.

Line 1은 R_Table과 S_Table을 불러오는 과정, Line 2는 키와 값을 구분하는 과정이다. Line 3은 키와 값에 필요하지 않은 문자를 정규표현식을 사용하여 제거하고, Line 4는 한 열로 되어있는 OCT ID를 분리하는 부분이다. 따라서 시간복잡도는 아래 식과 같다. 아래 식 (1)의 n과 m은 각각 S_Table과 R_Table의 행 개수를 의미하고, k는 블로킹 된 블록의 값 개수이다. 그래서 (2)와 같이 비교하는 개수는 k2, 비교 횟수는 k2가 되기 때문에 (3)과 같이 전개할 수 있다. m과 n의 관계는 m과 k는 n에 비해 비교적 수가 적기 때문에 상수처럼 취급할 수 있다.

이처럼 제안방안의 시간복잡도는 O(n)에 수렴하는 선형적인 시간복잡도를 가지는 것을 확인할 수 있다.

실험에 사용한 데이터는 택시 34대가 2011년 1월 1일부터 2018년 8월 29일까지 대구광역시를 이동하며 수집한 IoT 데이터를 사용하였다. 각 택시의 센서는 시간, 경도, 위도, 초미세먼지, 미세먼지, 온도 등 15개의 칼럼을 1초마다 생성된 데이터를 수집하였다. 본 논문에서는 시간, 위도, 경도, 센서 아이디, 미세먼지, 초미세먼지 칼럼을 사용하였고, 인덱싱 기간은 2018년 1월 1일부터 2018년 8월 29일까지인 데이터를 사용하였다. 도로 데이터는 국가공간정보포털에서 행정안전부의 도로 구간 데이터 사이트에서 제공하는 shape 파일 형식의 도로 구간 데이터 세트를 사용하였다. 하지만 제공된 데이터 세트는 국내 좌표계로 이루어져 있어 위경도 좌표계로 변환하는 작업을 거쳤다. 시경계 데이터의 경우 통계청에서 제공하는 대한민국 행정구역 읍면동 데이터를 다운로드 받았다. 이는 전국에 있는 모든 도시의 시경계(시, 구, 동)에 대한 공간 정보를 위도와 경도로 표시한 데이터이다.

표 4는 제안방안을 구현하고 실험한 컴퓨터의 하드웨어 사양과 사용된 운영체제에 대한 실험환경이다.

본 논문의 실험은 Python 3.6.5를 사용하여 입력받은 사용자 질의에 해당하는 지역의 IoT 데이터를 분석하여 그 결과를 시각화하였고, MySQL 5.7을 이용하여 해시 함수와 블로킹 과정을 구현하였다.

다음은 구현하면서 사용한 라이브러리들의 버전이다. Folium 0.10.1[13]은 오픈스트리트 맵(OpenStreetMap)을 사용하는 라이브러리로, 분석 결과를 지도위에 색을 통하여 구분하여 시각화할 때 사용하였다. Shapely 1.7.0[14]은 기하학적 도형을 사용자가 마우스를 드래그하여 그릴 수 있는 라이브러리로, 지도위에 선, 원, 사각형, 다각형 등 사용자가 원하는 도형을 생성해 원하는 지역을 선택할 수 있도록 하였다. s2sphere 0.2.5[15]는 구글 S2 셀을 사용하기 위한 라이브러리이다.

실험은 24시간, 1주일, 1개월, 8개월의 결과를 비교하였다. 실험 결과는 24시간, 1주일, 1개월의 경우 10개의 질의를 무작위로 질의해 얻은 최솟값, 최댓값, 평균, 표준편차이다.

표 5는 주요함수들의 8개월 단위 질의의 응답시간을 비교실험 한 결과이다. q4는 시경계 전체, q5는 전체 도로 검색, q6은 전체 히트맵 검색을 하는 질의이다.

함수 (A)는 그림 3의 1번 과정으로 데이터베이스에서 OCT ID를 사용하여 질의한 날짜와 시간에 해당하는 데이터를 적재하는 함수, 함수 (B)는 그림 3의 3번 과정으로 행정구역별 OCT ID를 생성하는 과정, 함수 (C)는 그림 3의 4번 과정으로 인스턴스 테이블에서 행정구역별 평균을 집계하는 함수이다.

제안방안에서는 SQL 문을 사용하여 일괄적으로 처리하기 때문에 함수 (A)와 (B) 과정이 통합되었다. [5]의 방안 중 (B) 함수는 조인 연산을 사용하여 행정구역별 OCT ID의 키와 값의 쌍을 만들어 데이터의 크기가 증가함에 따라 시간복잡도가 지수적으로 증가한다. 하지만 제안방안의 경우 해시 함수와 블로킹 기법을 이용하여 선형적인 시간복잡도를 갖기 때문에 시간이 단축되는 효과가 있다. q4~q6 중 q4와 q5의 같은 전체 검색임에도 시간이 차이가 나는 이유는 동의 개수가 187개로 4,007개인 도로의 개수보다 적기 때문이다.

표 6은 기존방안인 [5]의 방안과 제안방안을 비교 실험한 결과이다.

질의별 10개의 질의를 무작위로 질의하여 얻은 최소값(min), 최대값(max), 평균(avg), 표준편차(σ)이다. 8개월은 전체 데이터를 검색하는 것이므로 10번 질의를 하면 같은 지역의 같은 기간을 동일하게 10번 질의하는 것이기 때문에 여러 번 질의할 필요가 없었다. 모든 질의 응답시간은 소수점 3번째 자리에서 반올림하였다. q4는 대구광역시의 동 전체를 검색하는 질의이다. 1일 기준 평균이 [5]의 방안 보다 약 39% 시간이 단축되었다. 표준편차 또한 [5]의 방안보다 변화폭이 작아 사용자에게 안정적으로 결과를 제공해줄 수 있다. 기간을 1주로 확장할 경우 [5]의 방안은 1일 기준보다 약 151% 시간이 증가했지만 본 논문의 제안방안은 약 4% 증가하였다. 응답시간 또한 [5]의 방안보다 약 74% 시간이 단축되었는데 [5]의 방안은 데이터가 증가함에 따라 시간복잡도가 지수적으로 증가하여 반면 본 논문의 제안방안은 선형적인 시간복잡도를 갖기 때문이다.

q5는 대구광역시의 도로 전체를 검색하는 질의이다. 1일 기준 평균이 [5]의 방안보다 약 51% 단축되었다. q4보다 더 큰 폭으로 시간이 감소하였는데, 이는 동의 개수보다 도로의 개수가 많아 도로 검색의 경우가 데이터의 크기가 크기 때문이다. 그리고 [5]의 방안의 경우 1일 기준에서 1주로 기간을 확장할 경우 [5]의 방안은 1일 기준보다 약 348% 증가했지만 본 논문의 제안방안은 약 169% 증가하였다.

q6는 대구광역시의 도로 전체의 히트맵을 생성하는 질의이다. 도로를 기준으로 집계하기 때문에 응답시간은 q5와 유사하다.

비교실험 결과 제안방안이 기존방안인 [5]의 방안보다 더 빠른 응답 속도를 보였다. 응답시간의 평균을 기준으로 전체 약 66%, 1일 단위는 약 47%, 1주일 단위는 약 71%, 1개월 단위는 약 86%, 8개월 위는 약 60% 향상되었다. 이는 데이터의 크기가 증가함에 따라 시간복잡도가 지수적으로 증가하는 기존방안에 비해 선형적인 시간복잡도를 갖는 제안방안이 더 우수하다는 것을 증명한다.