블록체인 기반의 지리 공간 포인트 데이터 인덱싱을 위한 공간 LSM 트리
Spatial LSM Tree for Indexing Blockchain-based Geospatial Point Data
- 주제어 (키워드) 공간 LSM 트리 , 블록체인 , 공간 데이터 , LSM 트리 , 컴포넌트 테이블 , 공간 필터
- 발행기관 서강대학교 일반대학원
- 지도교수 정성원
- 발행년도 2022
- 학위수여년월 2022. 8
- 학위명 석사
- 학과 및 전공 일반대학원 컴퓨터공학과
- 실제 URI http://www.dcollection.net/handler/sogang/000000067023
- UCI I804:11029-000000067023
- 본문언어 한국어
- 저작권 서강대학교 논문은 저작권 보호를 받습니다.
초록
블록체인 기술은 IOT, 헬스케어 등 다양한 분야에서 높은 활용도로 주목받으며, 분산 데이터베이스에 대한 대안으로도 활용되고 있다. 블록체인에 대한 높은 활용성에도 불구하고, 블록체인 기반의 지리 공간 데이터를 효율적으로 인덱싱하는 기법은 지금까지 많은 연구가 진행되지 않았다. 이에 본 논문에서는 블록체인의 쓰기-집중적인(write-intensive) 특성을 반영하여 지리 공간 포인트 데이터의 블록을 블록체인에 삽입 시 I/O 비용을 감소시키는 공간 LSM 트리 인덱싱 기법을 제안한다. 제안 기법은 실시간으로 대량의 업데이트가 발생하는 블록체인 상에서 지리 공간 데이터를 Geohash를 통해 선형화하고, 데이터간의 공간적 인접성을 고려하여 데이터 삽입 및 질의 처리 시 I/O 비용을 최소화한다. 또한, 지리 공간 포인트 데이터 범위 질의 및 kNN 질의 처리 시 공간 LSM 트리에 대한 불필요한 탐색을 줄이기 위한 공간 필터를 제안한다.
more초록
Blockchain technology is attracting attention for its high usability in various fields such as IOT and healthcare, and it being used as an alternative to distributed databases. Despite their high usability for blockchain, the techniques for efficiently indexing blockchain-based geospatial data have not been studied much until now. Therefore, in this paper, we propose a Spatial LSM tree indexing method that reduces the I/O cost when a block of geospatial point data is inserted into a blockchain by reflecting the write-intensive features of the blockchain. The proposed method linearizes geospatial data through Geohash on the blockchain where a large scale of real time updates occur. It also minimizes the I/O cost when range query and inserting data into the blockchain by taking the spatial proximity of the point data into account. It also proposes a spatial filter to reduce unnecessary traversal of spatial LSM tree for processing geospatial point data range queries and kNN queries.
more