디지털 라이브러리[ 검색결과 ]
사용자와 이동 객체의 움직임을 동시에 고려한 예측 질의처리 기법
http://doi.org/10.5626/JOK.2018.45.12.1302
최근 GPS가 탑재되어 있는 스마트폰이나 태블릿 PC 등 모바일 기기의 사용이 증가함에 따라, 다양한 센서로부터 얻은 대량의 데이터를 분석하는 것이 가능해졌다. 이에 따라 다양한 위치기반 서비스들을 효과적으로 제공하기 위해 공간 질의를 효율적으로 처리하는 기법에 대한 연구가 이루어지고 있다. 본 논문에서는 기존 예측 공간 질의처리 연구들에서 사용자의 이동을 고려하지 않아 원하는 질의 결과를 반환하지 못하는 한계점을 극복하기 위한 방법을 제시한다. 구체적으로, 도로 교통망 환경에서 사용자의 이동시간과 대기시간을 고려했을 때 도달 가능성이 높은 최적의 K개의 이동 객체를 반환하는 예측 질의를 효율적으로 처리하기 위한 알고리즘을 제안하며, 이 과정에서 사용자와 이동 객체의 움직임을 동시에 고려하여 이동 범위를 단계적으로 확장함으로써 불필요한 계산을 줄이는 기법을 적용한다. 또한 적절한 인덱스구조를 사용함으로써 정점과 이동 객체의 수가 많은 환경에서도 효율적으로 처리할 수 있도록 하였다. 마지막으로, 도로 교통망 환경에서의 실험을 통해 효율성 측면에서 유의미한 결과를 보였다.
연속 Top-k 질의 모니터링을 위한 효율적인 알고리즘
본 논문에서는 기존 공간 속성만을 고려하는 그리드 기반의 색인 기법을 변형하여 보다 빠른 연산을 수행하는 상위-k 질의 기법을 제안한다. 제안하는 기법은 이동 객체의 공간 속성 뿐만 아니라 비공간 속성을 활용하여 사용자가 선호하는 정보를 효과적으로 검색할 수 있는 메인메모리 기반 그리드 색인 구조인 Bit-Vector Grid Index(BVGI)를 구축한다. 그리드의 각 셀은 이동객체의 비공간 속성 값을 비트 벡터로 부호화하여 이동 객체가 어떤 셀에 포함되어 있는지 빠르게 판단할 수 있고, 각 셀에 존재하는 이동객체의 비트 벡터만을 비교하여 불필요한 연산을 줄일 수 있다. 성능 평가를 통해 제안하는 BVGI 기법이 기존의 질의 처리 기법보다 메모리 사용량과 CPU-time 측면에서 우수함을 보였다.
