검색 상세

칼럼 지향 데이터베이스 시스템을 위한 대용량 공간-키워드 데이터 질의 처리 기법

Very Large Spatial-keyword Data Query Processing Methods for Column-oriented Database

  • 발행기관 서강대학교 일반대학원
  • 지도교수 정성원
  • 발행년도 2020
  • 학위수여년월 2020. 2
  • 학위명 박사
  • 학과 및 전공 일반대학원 컴퓨터공학과
  • UCI I804:11029-000000064974
  • 본문언어 한국어
  • 저작권 서강대학교 논문은 저작권보호를 받습니다.

초록/요약

데이터 수집기술의 발달과 함께 지리 공간 데이터베이스 시스템은 데이터의 대용량화와 속성(attribute)의 다양화라는 새로운 문제에 직면하였다. 기존에 사용되던 관계형 데이터베이스 기반의 공간 데이터 처리 시스템들은 이와 같은 대용량 공간 데이터를 저장하고 검색하는 방법을 제공하지 않고 있기 때문에 다수의 연구자들은 새로운 전용 시스템을 개발하거나, 분산 파일 시스템을 수정하여 이 문제를 해결하고자 노력하고 있다. NoSQL DBMS는 복합적인 속성을 갖는 대용량 공간 데이터를 다루기 위한 대한 효과적인 대안이 될 수 있다. 특히 HBase와 Cassandra로 대표되는 칼럼 지향(Column-oriented) DBMS들은 분산 파일 시스템위에서 잘 작동할 수 있도록 설계되었으며, 상대적으로 자유로운 스키마를 가지고 있기 때문에 이처럼 복합적인 속성을 갖는 대용량 지리 공간 데이터를 효과적으로 다루기 위한 기반 시스템으로 활용하기에 적합한 구조를 가지고 있다. 그런데 이와 같은 시스템들은 테이블의 행키(rowkey)에 대한 1차원적인 인덱스만을 제공하기 때문에 다차원 공간 데이터를 효과적으로 저장하고 검색하기 위해서는 데이터의 공간적 속성에 대한 보조 인덱스와 이를 활용한 질의 처리 알고리즘이 필수적으로 개발되어야 한다. 본 연구에서는 칼럼 지향 DBMS에서 대용량 지리 공간 데이터에 대한 공간 및 공간-키워드 질의를 효과적으로 처리하는 기법을 개발한다. 목표를 달성하기 위한 방법으로 본 연구에서는 먼저 칼럼 지향 DBMS에 저장된 다차원 공간 데이터에 대한 인덱싱 기법과 이를 활용한 공간 질의 처리 알고리즘을 개발한다. 개발하는 기법의 주된 아이디어는 공간 데이터에 대한 보조 인덱스를 테이블 형태로 저장하고 상대적으로 크기가 작은 인덱스 테이블에 대한 선행 검색을 통해 질의 처리 시 발생하는 긍정 오류를 감소시키는 것이다. 본 연구에서 제안하는 보조 인덱스는 계층적인 구조를 가지며 이 인덱스를 활용한 질의 처리 알고리즘은 빠른 시간 내에 공간 질의를 처리할 수 있다. 다음으로 본 연구에서는 앞선 연구 성과를 다양한 속성 값과 함께 저장되는 공간 데이터에 대해 확장하는 연구를 진행한다. 공간 데이터는 수치적 속성이나 범주 속성을 함께 가질 수 있으며, 최근에는 특히 비정형적 속성을 갖는 텍스트 데이터와 함께 발생하는 경우가 많다. 이와 같은 데이터에 대한 질의는 공간 키워드 질의(spatial-keyword query)로 분류되며, 객체간의 공간적 인접성 뿐 아니라 텍스트적 연관성을 함께 질의조건으로 갖는다. 본 연구에서는 칼럼 지향 DBMS에서 공간 키워드 질의를 효과적으로 처리하기 위한 방법으로 데이터를 위치-키워드 쌍으로 이루어진 키워드 세그먼트로 분할하고 동일한 키워드를 갖는 세그먼트들에 대한 부분 공간 인덱스를 생성한다. 주어진 공간 키워드 질의는 각각의 키워드 세그먼트에 대한 질의로 분할되어 처리되며 각 부분 공간 인덱스의 탐색 결과를 병합하는 방법을 통해 공간 키워드 질의를 처리한다. 본 연구에서 개발하는 기법은 표준 공간 키워드 질의를 효과적으로 처리할 뿐 아니라 속성 값에 대한 불리언 표현식(Boolean expression)을 질의 조건으로 포함하는 공간 키워드 질의 또한 효과적으로 처리할 수 있다. 마지막으로 본 연구에서는 공간-텍스트 데이터에 대한 새로운 질의 조건을 갖는 새로운 타입의 공간 키워드 질의들을 개발하고, 개발된 질의를 효과적으로 처리하기 위한 알고리즘을 제시한다. 표준 공간 키워드 질의로 분류되는 질의들의 검색 조건은 기존의 공간 질의와 문서 검색 질의의 질의 조건을 단순 결합한 형태를 가지고 있다. 그러나 최근 공간-텍스트 데이터의 양이 급증함에 따라 고유한 검색조건을 갖는 질의에 대한 수요가 증가하고 있다. 본 연구에서 개발한 질의는 기존의 공간 키워드 질의조건인 공간적 인접성 및 텍스트적 연관성 뿐 아니라, 객체의 주변 환경에 대한 조건을 검사하여 객체를 필터링한다. 또한 개발된 질의는 서로 다른 도메인에 속하는 객체들과의 관계를 검색 조건으로 가질 수 있기 때문에, 본 연구에서는 이를 효과적으로 처리할 수 있는 부분 인덱스간의 협업 알고리즘을 개발한다. 개발된 알고리즘은 키워드, 혹은 도메인별로 빌드된 여러 개의 공간 인덱스를 동시에 탐색하며 탐색 과정에서 각 부분 질의 조건에 부합하지 않는 인덱스 노드들을 빠른 시점에 제거할 수 있다.

more

초록/요약

With the rapid development of data acquisition techniques, geospatial DBMS are faced to problem of system scalability and diversity of data attributes. Since existing RDBMS-based spatial data processing systems do not provide a efficient method for storing and retrieving such large and diverse spatial data, many researchers have tried to solve this problem by developing a dedicated system or extending distributed file system. NoSQL DBMS can be an effective alternative for handling the large and diverse spatial data. In particular, column-oridented DBMSs not only provide a user-friendly table view, but it also provide a relatively free schema and work well on distributed file systems. The problem is that the system only provides one-dimensional index for retrieve key-value segments in their file system. Therefore, a secondary indexing techniques and query processing algorithms should be developed to handle multi-dimensional spatial data on those systems. In this paper, we develop methods to efficiently process spatial and spatial-keyword queries for large and diverse geospatial data on column-oriented DBMS. First of all, we develop a spatial index and query processing techniques for spatial data in HBase. The main idea of our method is that the secondary index for spatial attributes are built in the form of table, and searches for the index tables are preceded the spatial query processing to reduce false positives on it. The proposed indexes have a hierarchical structure and query processing algorithms based on this index can process spatial queries in a short time. Next, we extend our spatial query processing method to handle the spatial data which have various kinds of attributes. Spatial data can have both numerical and categorical attributes, and it often has unstructured textual attributes. The query for such data is called the spatial-keyword query, and it has not only query conditions for spatial proximity but also textual relationships for query keywords. In this study, we divide an spatial-keywords data into location-keyword pairs, and construct spatial indexes for the segments having the same keyword. The given spatial keyword query is also divided into queries for each location-keyword segment and processed. The final query result is obtained by merging the local results of each index in subspace. The technique developed in this study can not only efficiently process standard spatial-keyword queries, but also process well spatial keyword queries including Boolean expressions for attribute values ​​as query conditions. Finally, we develop a novel type of spatial keyword queries with new query conditions for spatial-keyword data, and present an algorithm to efficiently process the developed queries. The search conditions of the queries classified as standard spatial keyword queries have a simple combination of the query conditions of the existing spatial query and the document search query. However, as the amount of spatial-keyword data has recently increased, the demand for the novel type of query having a unique search condition has increased. The query developed in this study filters the object by examining the environmental conditions of the object as well as the spatial adjacency and textual relevance, which are the existing spatial keyword query conditions. In addition, since the developed query can have relations with objects belonging to different keyword domains as search conditions, we develops a collaborative algorithm between partial indexes that can handle this types of queries effectively. The proposed algorithms simultaneously searches for multiple indexes constructed for each domain of keywords and can avoid unnecessary search for objects that cannot meet each partial query condition.

more