大型感測網路資料庫之資料壓縮與查詢

Data Compression and Query for Large Scale Sensor Network Database

郭哲瑋(Che-Wei Kuo)

指導教授 ： 施吉昇

國立臺灣大學/電機資訊學院/資訊工程學研究所/碩士(2010年)

https://doi.org/10.6342/NTU.2010.01689

摘要

摘要
多維度時間資料表格是感測網路應用中常見的儲存格式。隨著時間的
推移，資料表格將變得非常龐大而無法管理。為了減少儲存空間，並
達到即時查詢，如何權衡資料壓縮率以及即時查詢效能是一項具挑戰
性的議題。在這篇論文中，我們特別針對大型感測網路資料庫，提出
一個高儲存效率的框架，並且不犧牲查詢效能。資料壓縮採用幾種包
括字典壓縮和熵編碼等壓縮技術。同時，對壓縮後資料能直接進行查
詢而不需解壓縮的動作，以提升查詢效能。實驗針對幾種不同感測網
路應用，包括數位型電表、加洲索諾馬縣紅杉林、以及氣象觀測等資
料庫系統來評估資料壓縮率和查詢效能。實驗結果顯示，資料壓縮後
大小在原始大小 31％ 以內，且編碼效率達 75％ 以上。同時，在
查詢時增加的開銷在 8％ 以內，整體來看，查詢效能甚至優於未壓
縮資料表格。

關鍵字 - 資料壓縮, 感測網路, 感測網路應用

關鍵字

資料壓縮 ； 感測網路 ； 感測網路應用

並列摘要

Multi-dimensional temporal data set is the common format in sensor network applications to store sampled temporal data. As time goes on, the size of the core tables in the data set may increase to enormous size and the tables become not manageable. In order to reduce storage space and allow online query, how to trade off data compression effectiveness for on-line query performance is a challenge issue. In this paper, we are concerned with an effective framework for temporal data set that does not scarify online query performance and is specifically designed for very large sensor network database. The sampled data are compressed using several candidate approaches including dictionary-base compress and entropy coding. In the mean time,on-line queries are conducted without decompressing the compressed data set so as to enhance the query performance. Experiments are conducted on a digital power meter, Sonoma redwood, and Sensor KDD databases to evaluate the proposed methodologies in terms of data compression ratio and data query speed. The results show that the compression ratio are at most 31% and the coding efficiency achieves over 75%. In the mean time, the increased overhead for online query is limited up to 8% and overall query performance is even better than the uncompressed data.

Keywords - Data compression, sensor network, sensor network applications.

並列關鍵字

Data compression ； sensor network ； sensor network applications

參考文獻

[2] K. ROMER and E. Z. FRIEDEMANN MATTERN, “The Design Space of Wireless

Sensor Networks,” vol. 11, pp. 54–61, December 2004.

[3] C.-Y. CHONG and S. P. KUMAR, “Sensor Networks: Evolution, Opportunities,

wiki/Demographics of Chicago. Last accessed at April 2010.

[8] “Postgresql.” http://www.postgresql.org/.