具時間權重之串流資料的結合運算機制

Join Mechanism for Streaming Time-weighted Data

陳秀秀(Hsiu-Hsiu Chen)

指導教授 ： 陳世穎

國立臺中科技大學/資訊學群/資訊科技與應用研究所/碩士(2009年)

https://doi.org/10.6826/NUTC.2009.00051

摘要

近年來，由於資訊應用服務的多樣化，產生許多串流資料應用的需求，例如
網路流量控制與電話通信等串流資料的應用。這些應用中，使用者可以使用串流
資料管理系統（data stream management system，DSMS）來進行串流資料的查詢運
算。在這些系統上，每一筆串流資料的重要性都視為相同，並未考慮資料可能依
時間改變而有不同的重要性。另一方面，結合運算(join operations)是資料庫系統重
要的查詢技術；但是，由於串流資料不同於傳統的靜態資料，所以傳統的結合運
算技術無法直接應用在串流資料上。本研究將探討串流資料系統中，在考慮具時
間權重的資料（亦即資料可能依時間改變而有不同的重要性）的情況下，如何完
成串流資料的結合運算。本研究設計一串流資料處理模型，使用滑動視窗機制並
加入資料之時間權重值，以設計結合運算演算法。此一演算法利用結合雜湊機制
(hash join)進行結合運算，並利用資料之時間權重產生符合條件的結合運算結果。
我們亦開發實驗平台設計串流資料實驗，觀察模擬實驗之結果。實驗結果顯示，
本研究之結合運算機制在串流資料的筆數越多時，在所需之執行時間相近的情況
下，較傳統未考慮資料之時間權重的演算法，可提供使用者更多的結合運算結果。

關鍵字

串流資料 ； 結合運算 ； 滑動視窗 ； 時間權重資料

並列摘要

There are increasing demands for streaming data applications nowadays. In these
applications, streaming data comes into systems continuously at high speed. Streaming
data has properties that the traditional database management systems cannot support.
For example, data items arrive continuously and independently, the number of data
items is large and cannot be predicted, and approximate query results are permitted. As
a result, new mechanisms, especially the join mechanism, must take these special needs
into account to process streaming data efficiently for better system performance. This
paper proposes a join mechanism on stream data that takes into account the data
importance of individual time. In this study, a time-weighted streaming data model by
using the sliding window technique is presented. Also, the hash-join technique is
adopted to accelerate the join performance. Experimental results show that our proposed
method can generate more join results with almost the same time cost with another
proposed method.

並列關鍵字

streaming data ； join operation ； sliding window ； time-weighted data

參考文獻

pp.120-139.

Nishizawa , Justin Rosenstein , Jennifer Widom, 2003, “STREAM: the stanford

[3] R. Avnur and J. Hellerstein, 2000, “Continuously adaptive query processing,”

[5] B. Babcock, M. Datar, and R. Motwani, 2004, “Load shedding for aggregation

[6] Shivnath Babu and Jennifer Widom, 2001, “Continuous queries over data