應用曲線擬合建立資料串流之摘要結構

Applying Curve Fitting Techniques to Construct the Synopsis of Data Streams

彭義凱(Yi-Kai Peng)

指導教授 ： 鍾葉青

國立清華大學/電機資訊學院/資訊系統與應用研究所/碩士(2006年)

https://doi.org/10.6843/NTHU.2006.00094

摘要

資料串流是一連串即時、連續且有序的資料物件，是目前廣泛採用於處理大量動態資料的資料格式。資料內容不斷變動以及儲存資料所需空間無限是資料串流的兩大特性，同時也是處理資料串流時必須克服的議題。對於資料變動，近似解是一個已被廣泛運用的方案，使用於提供與實際值有一定程度符合的解答；在儲存空間上，數個不同的資料結構已被提出，用於儲存資料串流的部份資訊以取代儲存所有資料。建立資料串流摘要的目的在於儲存資料串流的部份資訊並利用特定演算法處理使用者的要求，提供近似解。在本論文中，資料串流中的物件被視為平面座標系中的一點，其目的在於利用曲線擬合技巧以一多項式作為資料串流的概述，並以微積分計算技巧提供近似解。經實驗可證明此演算法可將資料串流中Ｎ個物件以O(logN)空間儲存，且近似解能達到95%的準確度。

關鍵字

資料串流 ； 曲線擬合 ； Synopsis

並列摘要

A data stream is a real-time, continuous, and ordered sequence of data items. It is a widely used data format to deal with large amount of dynamic data. Dynamic content and unbounded storage requirement are the two main characteristics of data streams. We need to deal with these two issues while processing data streams. For the dynamic content issue, the approximate answering is a widely used approach to process queries on data streams. For the unbounded storage size issue, some data structures have been proposed to summarize the data streams and keep the storage space required small. Synopsis is a data structure that summarizes the data streams. By using some algorithms, users can get approximate answers of data streams from the summarized information stored in synopsis. In this thesis, we use the curve fitting technique to construct the synopsis of data streams in the form of a curve that expressed by a polynomial function. The algorithms for constructing the synopsis data structure and querying the data stream are also proposed. We prove that the storage space required by the proposed method is O(logN). From the experimental results, we observe that our approach can achieve 95% accuracy on data contents for the queries.

並列關鍵字

Data Stream ； Curve Fitting ； Synopsis

參考文獻

[1] S. Acharya, P. B. Gibbons, V. Poosala, and S. Ramaswamy, "Join synopses for approximate query answering," ACM SIGMOD Record, vol. 28, pp. 275-286, 1999.

[3] B. Babcock, S. Babu, M. Datar, R. Motwani, and J. Widom, "Models and issues in data stream systems," Proceedings of the twenty-first ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, pp. 1-16, 2002.

[5] S. Babu and J. Widom, "Continuous queries over data streams," ACM SIGMOD Record, vol. 30, pp. 109-120, 2001.

[7] J. E. Dennis and R. B. Schnabel, Numerical methods for unconstrained optimization and nonlinear equations: Prentice-Hall Englewood Cliffs, NJ, 1983.

[11] P. Flajolet and G. N. Martin, "Probabilistic counting algorithms for data base applications," Journal of Computer and System Sciences, vol. 31, pp. 182-209, 1985.