공간 키워드 유사도 기반의 부분적 집단 공간 키워드 질의처리 기법
A Partial Collective Spatial Keyword Query Processing based on Spatial Textual Similarity
- 주제(키워드) 질의 처리 , 공간 데이터베이스 , 공간 키워드 질의 , query processing , spatial databases , spatial keyword query
- 발행기관 서강대학교 일반대학원
- 지도교수 박석
- 발행년도 2021
- 학위수여년월 2021. 2
- 학위명 석사
- 학과 및 전공 일반대학원 컴퓨터공학과
- UCI I804:11029-000000065808
- 본문언어 한국어
- 저작권 서강대학교 논문은 저작권보호를 받습니다.
초록/요약
모바일 기기의 보급으로 위치 데이터에 기반한 사용자 서비스가 등장하기 시작했다. 또한 머신 러닝이 등장하며 사용자의 취향이나 선호도를 세밀하게 분석할 수 있는 환경이 구성되었다. 기존 위치 공간 질의는 모든 조건을 엄격하게 만족하는 POI만 반환하기 때문에 이러한 환경에서 사용자 선호도 기반 서비스를 개발하기 위해서 조건을 완화하여 질의를 유연하게 처리하는 방법이 필요하다. 기존 집단적 공간 키워드 질의(Collective Spatial Keyword Query)는 질의 위치와 가까우면서 제시된 키워드 집합을 모두 포함하는 POI들을 반환한다. 하지만 고정된 수의 질의 키워드를 고려하므로 사용자의 부분 키워드 집합에 대한 선호도를 충분히 반영할 수 없다. 따라서 POI 마다 선호도에 맞는 키워드를 유동적으로 선택하는 방법이 필요하다. 본 연구에서는 키워드의 선호도를 고려하여 POI 집합을 찾는 새로운 질의인 부분적 집단 공간 키워드 질의(Partial Collective Spatial Keyword Query)를 제안한다. 부분적 집단 공간 키워드 질의는 조합 최적화 문제이므로 POI의 수가 늘어남에 따라 수행 시간이 급격하게 증가한다. 따라서 이러한 문제를 해결하기 위해 전체적인 탐색 공간을 줄이는 키워드 기반 탐색 기법을 제안한다. 또한 키워드의 부분집합을 계산하는 시간을 줄이기 위해 선형 탐색에 기반한 단말노드 가지치기 기법과 근사 알고리즘에 의한 임계값을 설정하고, 하나의 후보 집합이 가질 수 있는 하한값을 계산하여 임계값에 기반한 가지치기 기법들을 제안한다.
more초록/요약
With the spread of mobile devices, user services based on location data have begun to emerge. In addition, machine learning has emerged and an environment has been constructed to allow detailed analysis of users' tastes or preferences. Existing collective spatial keyword queries return Points of Interest(POI), which are close to the query location and contain all of the presented set of keywords. However, considering a fixed number of query keywords, it is not possible to fully consider the user's preference for a subset of keyword sets. Therefore, there is a need for a flexible selection of keywords that fit the preference for each POI. In this thesis, we propose a Partial Collective Spatial Keyword Query, a novel query to find a POI set considering the preference of each keyword. Since Partial Collective Spatial Keyword Query is a combinatorial optimization problem, the performance time increases rapidly as the number of POIs increases. Therefore, to address these problems, we propose a keyword-based search technique that reduces the overall search space. Furthermore, to reduce the time to compute a subset of keywords, we propose threshold-based pruning techniques based on linear navigation and threshold-based pruning techniques by establishing thresholds by approximation algorithms, and computing the lower bounds that a single candidate set can have.
more