블록체인을 위한 공간-키워드 데이터 인덱싱을 위한 HQ-skLSM 트리
Spatial Keyword Search Query Processing Method for Blockchain-based Geospatial Point Data Using HQ-skLSM tree
- 주제어 (키워드) 블록체인 , 공간 키워드 데이터 , 쿼리 , blockchain , spaital keyword data , query
- 발행기관 서강대학교 일반대학원
- 지도교수 정성원
- 발행년도 2025
- 학위수여년월 2025. 2
- 학위명 석사
- 학과 및 전공 일반대학원 인공지능학과협동과정
- 실제 URI http://www.dcollection.net/handler/sogang/000000079665
- UCI I804:11029-000000079665
- 본문언어 한국어
- 저작권 서강대학교 논문은 저작권 보호를 받습니다.
초록 (요약문)
블록체인은 위변조 방지 특성 덕분에 다양한 분야에서 널리 채택되었다. 그러나 블록체인 환경에서 공간-키워드 점 데이터를 효율적으로 인덱싱하기 위한 기법은 여전 히 연구가 부족한 실정이다. 이전 연구에서는 블록체인에서 대량의 공간 점 데이터를 효율적으로 인덱싱하면서 쿼리 처리 시 Disk I/O를 최소화하는 구조로 Hierarchical Quadrant spatial LSM 트리(HQ-sLSM 트리)를 제안하였다. 하지만 이 방법은 지리적 정보만지원하여텍스트데이터를처리하는데한계가있다.본논문에서는본질적으로 쓰기 작업이 집중되는 블록체인에서 대규모 공간-키워드 점 데이터를 효율적으로 인덱 싱할 수 있도록 설계된 Hierarchical Quadrant spatial-keyword LSM 트리(HQ-skLSM 트리)를 제안한다. 데이터의 공간 정보와 텍스트 정보를 분리하여 인덱싱하고, 텍스트 필터를도입하여공간필터와결합함으로써쿼리처리시 Disk I/O를감소시킨다.실험 결과, HQ-skLSM 트리는 데이터 삽입 성능에서 우수할 뿐만 아니라, boolean range, boolean kNN, top-k 쿼리 처리에서도 기존 방법보다 뛰어난 성능을 보인다.
more초록 (요약문)
Blockchain technology has seen widespread adoption across various fields due to tamper-proof characteristics. However, efficient indexing techniques for spatial-keyword point data in blockchain environments remain underexplored. Previous research introduced the hierarchical quadrant spatial LSM tree (i.e., HQ-sLSM tree) as an effective structure for indexing large volumes of spatial point data in blockchain while minimizing disk I/O during query processing. This approach is limited in handling text data, as it only supports geographic information. In this paper, we propose the hierarchical quadrant spatial-keyword LSM tree (i.e., HQ-skLSM tree), designed to efficiently index large-scale spatial keyword point data in blockchain, which is inherently write-intensive. By separating keywords and frequencies, we introduce text filters that, when combined with spatial filters, result in reduced disk I/O during query processing. Experimental results show that the HQ-skLSM tree not only achieves superior performance in data insertion but also outperforms existing methods in boolean range, boolean kNN, and top-k query processing.
more목차
1. 서 론 1
2. 관련 연구 4
3. spatial-keyword 데이터 인덱싱을 위한 HQ-skLSM 트리 7
3.1 HQ-skLSM 트리 구조 7
3.2 HQ-skLSM 트리의 컴포넌트 테이블 11
3.3 Dictionary 14
3.4 Posting List 15
3.5 공간 필터와 텍스트 필터 16
3.6 HQ-skLSM 트리의 데이터 삽입 방법 17
4. HQ-skLSM 트리 기반의 질의 처리 20
4.1 Boolean range 질의 처리 20
4.2 Boolean kNN 질의 처리 25
4.3 Top-k 질의 처리 30
4.3.1 get_rank_score function 31
4.3.2 get_range function 33
4.3.3 A top-k query algorithm for HQ-skLSM tree 35
5. 실험 및 성능 평가 40
5.1 실험데이터 40
5.2 spatial-keyword 데이터 삽입 성능 비교 41
5.2.1 VARYING MDL 42
5.2.2 VARYING THRESHOLD 43
5.3 Boolean range 질의 성능 비교 44
5.4 Boolean kNN 질의 성능 비교 46
5.5 Top-k 질의 성능 비교 48
6. 결 론 50
참고문헌 51
