主記憶體資料庫上之多維度索引結構設計

A Multi-Dimension Hash Index Design for Main-Memory RFID Database Applications

葉勝翔(Sheng-Shang Ye)

指導教授 ： 盧永豐

共同指導教授 ： 黃慧鳳

國立臺中科技大學/資訊與流通學院/資訊工程系碩士班/碩士(2012年)

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

摘要

在具有規模的無線射頻辨識系統應用中，往往需要一個能夠提供後端資料庫高效能的數據處理，並且使用有效率的索引結構。本篇論文提出了一個索引結構，為多維度雜湊函數索引（MH-Index），它能夠滿足RFID資料庫所需要的請求，其主要的想法是提供RFID應用在主記憶體資料庫上執行資料處理時能得到很好的效率。多維度雜湊索引的架構是以資料庫的欄位屬性為基礎，從資料庫取得的欄位屬性儲存到多維的空間上，並且利用雜湊函數將要檢索的項與用來檢索的索引關聯起來，生成一種便於搜索的資料結構，並且透過我們所設計的索引來支援查詢，以大幅改善資料庫查詢及應用程式的效能。在實驗結果上，我們提出的多維度雜湊索引明顯的優於其他在資料庫上所提供地的索引結構。

關鍵字

索引結構 ； 雜湊函數 ； 主記憶體資料庫 ； 無線射頻辨識技術

並列摘要

A large-scale RFID application often requires an efficient index structure design for database to provide a highly efficient data processing. This paper presents a new indexing scheme, called Multi-dimension Hash index (MH-index), that satisfies all the requirements of a good RFID database applications. The main idea is to provide RFID applications extremely high efficiency in data manipulations over main-memory databases. A MH-Index is constructed based on multi-dimensional attributes that are the keys of one relation. The capability of the design is implemented in an open source main-memory database system H2 and evaluated by realistic workloads of RFID applications. Comparing to other indexes, the experimental results show that the proposed index design outperforms others in execution time.

並列關鍵字

Index structure ； hash ； main-memory database ； RFID

參考文獻

[2] K. R. Choi and K. C. Kim. “T*-tree: a main memory database index structure for real time applications.” In Proceedings of the Third International Workshop on Real-Time Computing Systems Application, RTCSA ’96, pages 81, Washington, DC, USA, 1996. IEEE Computer Society.

[7] T. J. Lehman. “Design and performance evaluation of a main memory relational database system (t tree).” PhD thesis, 1986. AAI8621915.

[8] H. Lu, Y. Y. Ng, and Z. Tian. “T-tree or b-tree: Main memory database index structure revisited.” In Proceedings of the Australasian Database Conference, ADC’00, pages 65–, Washington, DC, USA, 2000. IEEE Computer Society.

[10] P. L. Suei, Y. F. Lu, R. J. Liao, and S. W. Lo. “A signature-based grid index design for main-memory rfid database applications.” J. Syst. Softw., 85(5):1205–1212, May 2012.

[11] E. Tousidou, P. Bozanis, and Y. Manolopoulos. “Signature-based structures for objects with set-valued attributes.” Inf. Syst., 27(2):93–121, April 2002.