센서 네트워크에서 스트림 데이터 질의의 효율적인 처리를 위한 다중 질의 색인 기법

국문 초록 (Abstract)

센서 네트워크는 스스로 감지하고 계산하고 무선으로 서로 통신할 수 있는 기능을 갖춘 센서들로 이루어진 네트워크이다. 센서 네트워크의 특정들로는 네트워크가 자체적으로 관리가 되어야 한다는 것과 배터리 전원이여서 전력의 효율성을 크게 고려해야 한다는 것이 있다. 센서 네트워크에서 생성되는 많은 양의 연속적인 데이터에 대하여 여러 개의 질의들을 동시에 처리해야 하는 경우에 전력의 효율성을 극대화시켜야 한다. 본 연구에서는 센서 네트워크에서 감시 목적의 미리 정의된 다중 질의들에 대해 색인을 두어 다중 질의 처리 성능을 높이고 메모리와 전력을 효율적으로 사용할 수 있는 기법을 제안한다. 공간 색인 기법 중에서 이진 탐색트리에 기반한 데이터 구조로서 각 레벨별로 차원이 반복되어 각 차원을 분할시키는 k-d 트리와, 공간을 계층적 구조로 자르며 겹침 관계를 줄인 R-트리의 변형인 R+-트리를 기반으로 하여 이들의 응용 및 융합을 통해 다중 질의를 색인하는 새로운 트리인 SMILE 트리를 제안한다. 질의들에 대한 SMILE 트리를 구성하여 센서 네트워크에서 생성되는 스트림 데이터에 대하여 관련된 질의를 탐색하도록 하면 질의를 순차 탐색하는 것과 비교하여 경우에 따라서는 평균 탐색시간을 약 50% 정도로 줄일 수 있다.

다국어 초록 (Multilingual Abstract)

A sensor network consists of a network of sensors that can perform computation and also communicate with each other through wireless communication. Some important characteristics of sensor networks are that the network should be self administered and the power efficiency should be greatly considered due to the fact that it uses battery power. In sensor networks, when large amounts of various stream data is produced and multiple queries need to be processed simultaneously, the power efficiency should be maximized. This work proposes a technique to create an index on multiple monitoring queries so that the multi-query processing performance could be increased and the memory and power could be efficiently used. The proposed SMILE tree modifies and combines the ideas of spatial indexing techniques such as k-d trees and R+-trees. The k-d tree can divide the dimensions at each level, while the R+-tree improves the R-tree by dividing the space into a hierarchical manner and reduces the overlapping areas. By applying the SMILE tree on multiple queries and using it on stream data in sensor networks, the response time for finding an indexed query takes in some cases 50% of the time taken for a Linear search to find the query.

목차 (Table of Contents)

• 요약
• ABSTRACT
• 1. 서론
• 2. 관련 연구
• 3. 센서 네트워크에서의 스트림 데이터 처리를 위한 다중 질의 색인 기법
• 4. 구현 및 성능 평가
• 4. 결론 및 향후 연구
• 참고문헌

참고문헌 (Reference)

• 1 S. R. Madden, "TinyDB : An Acquisitional Query Processing System for Sensor Networks" 30 (30): 122-173, 2005
• 2 "TinyDB"
• 3 T. Sellis, "The R+-Tree : A Dynamic Index for Multi-Dimensional Objects" 507-518, 1987
• 4 C. Bohm, "Searching in High-Dimensional Spaces-Index Structures for Improving the Performance of Multimedia Databases" 33 (33): 323-373, 2001
• 5 "STREAM project"
• 6 A. Guttman, "R-Trees-A Dynamic Index Structure for Spatial Searching" 47-57, 1984
• 7 K. Wu, "Query indexing with containment-encoded intervals for efficient stream processing" 9 (9): 62-90, 2006
• 8 J. Gehrke, "Query Processing in Sensor Networks" IEEE ComSoc 2004
• 9 J. L. Bentley, "Multidimensional binary search trees used for associative searching" 18 (18): 509-517, 1975
• 10 B. Bobcock, "Models and Issues in Data Stream Systems" 1-16, 2002