In RFID/USN (Radio Frequency IDentification/Ubiquitous Sensor Network) environments, a large amount of data is generated. Since data generated in these environments has different characteristics from data generated in traditional environments, we cannot apply traditional database technologies. We propose techniques to manage such data effectively and efficiently. We first discuss data management techniques in RFID environments and then discuss those in USN environments.
Since data generated in RFID environments has noisy and duplicate data, various filtering techniques are needed. Especially, it is important to eliminate duplicate data since RFID data has many duplicates. However, it is difficult to eliminate duplicate RFID data in one pass with the limited memory since a large amount of RFID data is generated simultaneously in a streaming fashion. Therefore, we propose one pass approximate methods (Time Bloom Filters and Time Interval Bloom Filters) based on Bloom Filters using a small amount of memory.
The RFID data collected from many RFID readers will be used for various analyses in the central server. It is important to analyze the object transition in many RFID applications. In this dissertation, focusing on supply chain management, we propose an efficient storage scheme and query processing for large RFID data sets in order to analyze the object transition efficiently. We first define query templates to analyze the object transition. We then propose an effective path encoding scheme to encode the flow information for products. To retrieve the time information for products efficiently, we utilize a numbering scheme used in the XML area.
The generated data in USN environments is ordered data and its volume is huge. Therefore, we need to reduce the ordered data effectively. For effective data reduction, we consider compression schemes with data reordering. We first investigate general principles to improve the compression ratio for ordered data by reordering of data. Then, based on the principles, we reconsider two compression schemes, run-length encoding (lossless compression) and bucketing scheme (lossy compression) as bases for showing the impact of data reordering in compression schemes. Also, we propose various optimization techniques related to data reordering in the compression schemes.
In USN environments, aggregate queries are one of the most important queries. Especially, group-by aggregate queries can be used in various USN applications such as tracking, monitoring, and event detection. In this dissertation, we propose a framework, called the G-Framework, to effectively process continuous group-by aggregate queries in the case that sensors are grouped by the geographical location. In the G-Framework, we can perform energy efficient data aggregate processing and dissemination using two-dimensional Haar wavelets. Also, to process continuous group-by aggregate queries with a HAVING clause, we divide data collection into two phases.
RFID/USN 환경에서는 많은 양의 데이터가 발생한다. 이러한 환경에서 발생하는 데이터는 기존의 환경에서 발생하는 데이터와 다른 특징을 지니므로, 기존의 데이터베이스 기술을 적용할 수 없다. 본 학위 논문에서는 그러한 데이터를 효과적이고 효율적으로 관리할 수 있는 기술들을 제안한다. 먼저, RFID 환경에서의 데이터 관리 기술을 논의하고, 다음으로 USN 환경에서의 데이터 관리 기술을 논의한다.
RFID 환경에서 발생하는 데이터는 노이지 데이터(Noisy Data)와 중복 데이터(Duplicate Data)를 포함하기 때문에, 다양한 필터링 기술들을 필요로 한다. 특별히, RFID 데이터는 중복 데이터를 많이 포함하기 때문에 중복 데이터를 제거하는 것이 중요하다. 그러나, 많은 양의 RFID 데이터는 동시에 스트림 형태로 발생하기 때문에, 제한된 메모리를 가지고 원 패스(One Pass)로 중복 데이터를 제거하는 것은 어렵다. 그럼으로써, 작은 메모리를 사용하여 블룸 필터(Bloom Filter)에 기반한 원 패스 근사 방법을 제안한다.
많은 RFID 리더로부터 모아진 RFID 데이터는 중앙 서버에서 다양한 분석을 위해 사용될 것이다. 다양한 RFID 애플리케이션(Application)에서 객체(Object)의 이동을 분석하는 것은 중요하다. 본 학위 논문에서는, 공급망 관리(Supply Chain Management)에 중점을 두면서, 객체 이동을 효율적으로 분석하기 위하여 대용량 RFID 데이터를 위한 효율적인 저장 스킴 및 질의 처리 방법을 제안한다. 먼저, 객체 이동을 분석하기 위한 질의 템플릿을 정의하고, 이동 정보를 인코딩 하기 위한 효과적인 패스 인코딩 스킴(Path Encoding Scheme)을 제안한다. 객체에 대한 시간 정보를 효율적으로 검색하기 위해 XML 분야에서 사용된 넘버링 스킴(Numbering Scheme)을 활용한다.
USN 환경에서 발생된 데이터는 순서가 있는 데이터(Ordered Data)이고, 데이터 볼륨은 매우 크다. 그러므로, 순서가 있는 데이터를 효과적으로 줄일 필요가 있다. 효과적인 데이터 축소를 위해, 본 학위 논문에서는 압축 방법을 데이터 재정렬 기술과 함께 고려해 본다. 먼저, 데이터 재정렬을 통해 압축률을 높일 수 있는 일반적인 원칙들을 규명한다. 그런 다음에, 압축 방법에서의 데이터 재정렬 효과를 알아 보기 위한 기초로써, 앞의 일반적인 원칙에 기반하여 런 길이 인코딩(Run-length Encoding)과 버케팅 스킴(Bucketing Scheme)을 재고려한다. 또한, 압축 방법에서 데이터 재정렬과 관련된 다양한 최적화 기술들을 제안한다.
USN 환경에서, 집계 질의는 가장 중요한 질의 중의 하나이다. 특별히, 그룹에 의한 집계 질의(Group-by Aggregate Query)는 트래킹, 모니터링, 이벤트 탐지 등의 다양한 USN 애플리케이션에서 사용될 수 있다. 본 학위 논문에서는 센서가 지리적인 위치로 그룹되어 있는 경우, 그룹에 의한 연속 집계 질의를 효과적으로 처리할 수 있는 G-Framework를 제안한다. G-Framework에서는 이차원 Haar 웨이블렛(Haar Wavelet)을 사용해서 에너지에 효율적인 데이터 집계 처리 및 분배를 수행할 수 있다. 또한, HAVING절을 가진 그룹에 의한 연속 집계 질의를 처리하기 위해 데이터 수집을 두 단계로 나눈다.
