基於資料關係之區間查詢演算法｜國立臺灣科技大學博碩士論文系統

簡易檢索 / 詳目顯示

回結果列表

研究生：	陳明瑜 Ming-Yu Chen
論文名稱：	基於資料關係之區間查詢演算法 A Data-Relation Based Interval Query Algorithm for Dynamic System
指導教授：	邱舉明 Ge-Ming Chiu
口試委員:	吳秀陽 Shiow-Yang Wu 鄧惟中 Wei-Chung Teng 金台齡 Tai-Lin Chin
學位類別：	碩士 Master
系所名稱：	電資學院 - 資訊工程系 Department of Computer Science and Information Engineering
論文出版年：	2015
畢業學年度：	103
語文別：	中文
論文頁數：	43
中文關鍵詞：	區間查詢、重疊查詢、區間索引
外文關鍵詞：	Interval Query, Overlap Query, Interval Index.
相關次數：	點閱：172 下載：2
分享至:	分享至facebook 分享至twitter

查詢本校圖書館目錄查詢臺灣博碩士論文知識加值系統勘誤回報

上一筆

近年來，隨著網路通訊的發展，使得人們可以隨時隨地獲得新資訊，而人們獲得
新資訊的同時，也會不斷產生新資料，因此資料的有效管理成為現今重要的議題之
一。
在本篇論文中，我們主要是探討如何在動態的環境下，針對區間資料做區間查詢。
區間資料應用廣泛，但現有的區間查詢方式無法兼具查詢效能與動態新增，因此我們
提出了新的方法，其方法為一個基於資料關係所建立的結構，並且利用資料關係提出
了有效率的區間查詢演算法和新增資料演算法。
論文最後，我們實現了我們所提出的方法，並與現有的方法去做效能評估，整體
而言我們的方法都能夠兼具快速查詢與動態新增。

In recent years, the development of Internet has provided humans to acquire
information more easily, and they produce a large amount of data simultaneously.
Thus, effective management of data has become an important issue.
In this paper, we focus on supporting interval queries for interval data. However,
existing methods used to query interval data, to the best of our knowledge, fail to combine
two important features of high query efficiency and dynamic insertion.
Therefore, we propose a method based on the relation of interval data and an
algorithm used to efficiently query between intervals and insert instance.
For the rest of this paper, several existing methods are implemented to compare with
ours, and the experimental results show that our proposed method can provide a more
efficient combination of querying and inserting instances.

摘要
................................................................................................................  I
Abstract  ..........................................................................................................  II
誌謝  ..............................................................................................................  III
目錄  ..............................................................................................................  IV
圖目錄  ..........................................................................................................  VI
表目錄  ........................................................................................................  VIII
第一章  緒論  .................................................................................................  1
1.1  研究背景  ...................................................................................................  1
1.2  區間資料  ...................................................................................................  1
1.3  區間查詢  ...................................................................................................  3
1.4  論文目標  ...................................................................................................  5
1.5  論文架構  ...................................................................................................  5
第二章  相關研究  ..........................................................................................  7
2.1  Endpoints Index  .........................................................................................  7
2.1.1  資料結構  .......................................................................................  7
2.1.2  查詢流程  .......................................................................................  9
2.2  線段樹  .......................................................................................................  9
2.2.1  資料結構  .......................................................................................  9
2.2.2  查詢流程  .....................................................................................  11
2.3  單點查詢  .................................................................................................  12
2.3.1  資料結構  .....................................................................................  12
2.3.2  查詢流程  .....................................................................................  13
V
第三章  基於區間關係查詢演算法  ............................................................  15
3.1  問題描述與定義  .....................................................................................  15
3.2  區間資料關係分析  .................................................................................  16
3.2.1  基本關係  .....................................................................................  16
3.2.2  第一類區間  .................................................................................  18
3.2.3  第二類區間  .................................................................................  18
3.2.4  新區間  .........................................................................................  23
3.3  儲存架構  .................................................................................................  24
3.3.1  Endpoints List  ..............................................................................  24
3.2.5  Data Relation List  ........................................................................  26
3.4  DRBIQ 流程  ............................................................................................  28
3.5  DRBInsert 流程  .......................................................................................  33
第四章  實驗結果  ........................................................................................  35
4.1  實驗設定  .................................................................................................  35
4.2  Interval Query  ..........................................................................................  36
4.2.1  不同資料筆數  .............................................................................  36
4.2.2  不同資料大小  .............................................................................  37
4.2.3  不同查詢範圍  .............................................................................  38
4.3  Data Insertion  ..........................................................................................  40
第五章  結論與未來研究方向  ....................................................................  41
重要參考文獻  ..............................................................................................  42

                                

[1] T. Guo, T. G. Papaioannou, and K. Aberer, "Model-view sensor data management in
the cloud," in Big Data, 2013 IEEE International Conference on, 2013, pp. 282-290.
[2] K.-L. Wu, S.-K. Chen, and P. S. Yu, "Interval query indexing for efficient stream
processing," in Proceedings of the thirteenth ACM international conference on
Information and knowledge management, 2004, pp. 88-97.
[3] E. N. Hanson and T. Johnson, "Selection predicate indexing for active databases
using interval skip lists," Information Systems, vol. 21, pp. 269-298, 1996.
[4] C.-H. Ang and K.-P. Tan, "The interval B-tree," Information Processing Letters, vol.
53, pp. 85-89, 1995.
[5] C. P. Kolovson and M. Stonebraker, Segment indexes: Dynamic indexing techniques
for multi-dimensional interval data vol. 20: ACM, 1991.
[6] J. M. Schmidt, "Interval stabbing problems in small integer ranges," in Algorithms
and Computation, ed: Springer, 2009, pp. 163-172.
[7] R. Elmasri, G. T. Wuu, and Y.-J. Kim, "The time index: An access structure for
temporal data," in Proceedings of the 16th International Conference on Very Large
Data Bases, 1990, pp. 1-12.
[8] A. Kumar, V. J. Tsotras, and C. Faloutsos, "Designing access methods for bitemporal
databases," Knowledge and Data Engineering, IEEE Transactions on, vol. 10, pp.
1-20, 1998.
[9] M. K. Aguilera, W. Golab, and M. A. Shah, "A practical scalable distributed b -tree,"
Proceedings of the VLDB Endowment, vol. 1, pp. 598-609, 2008.
[10] A. V. Alekseyenko and C. J. Lee, "Nested Containment List (NCList): a new algorithm
for accelerating interval query of genome alignment and interval databases,"
Bioinformatics, vol. 23, pp. 1386-1393, 2007.
[11] R. M. Layer, K. Skadron, G. Robins, I. M. Hall, and A. R. Quinlan, "Binary Interval
Search: a scalable algorithm for counting interval intersections," Bioinformatics,
vol. 29, pp. 1-7, 2013.
[12] F. Chang, J. Dean, S. Ghemawat, W. C. Hsieh, D. A. Wallach, M. Burrows, et al.,
"Bigtable: A distributed storage system for structured data," ACM Transactions on
Computer Systems (TOCS), vol. 26, p. 4, 2008.
[13] G. DeCandia, D. Hastorun, M. Jampani, G. Kakulapati, A. Lakshman, A. Pilchin, et al.,
"Dynamo: amazon's highly available key-value store," in ACM SIGOPS Operating
Systems Review, 2007, pp. 205-220.
[14] A. Lakshman and P. Malik, "Cassandra: a decentralized structured storage system,"
ACM SIGOPS Operating Systems Review, vol. 44, pp. 35-40, 2010.
43
[15] Apache HBase. Available: http://hbase.apache.org/
[16] G. Sfakianakis, I. Patlakas, N. Ntarmos, and P. Triantafillou, "Interval indexing and
querying on key-value cloud stores," in Data Engineering (ICDE), 2013 IEEE 29th
International Conference on, 2013, pp. 805-816.
[17] S. Wu, D. Jiang, B. C. Ooi, and K.-L. Wu, "Efficient B-tree based indexing for cloud
data processing," Proceedings of the VLDB Endowment, vol. 3, pp. 1207-1218,
2010.

簡易檢索 / 詳目顯示

相關論文