臺灣博碩士論文加值系統

在具有規模的無線射頻辨識系統應用中，往往需要一個能夠提供後端資料庫高效能的數據處理，並且使用有效率的索引結構。本篇論文提出了一個索引結構，為多維度雜湊函數索引（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.

Contents
摘要 i
ABSTRACT ii
Chapter 1. Introduction 1
1.1 Introduction 1
1.2 System Architecture and Motivation 3
1.3 Thesis Organization 5
Chapter 2. Related Work 6
2.1 Previous remarks 6
2.2 Linked List 6
2.3 AVL-Tree structure 7
2.4 T-Tree structure 8
2.5 Grid Index structure 9
Chapter 3. The Multi-Dimensional Hash Index structure 13
3.1. The MH-Index Structure 13
3.2. The MH-Index Operations 16
Chapter 4. Performance evaluation 24
4.1. Experimental setup 24
4.2. Performance result 26
Conclusion 30
References 31

[1]Y. Chen and Y. Chen. “Signature file hierarchies and signature graphs: a new index method for object-oriented databases,” In Proceedings of the 2004 ACM symposium on Applied computing, SAC ’04, pages 724–728, New York, NY,USA, 2004. ACM.

[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.

[3]Hsql Database. http://hsqldb.org/.

[4]U. Deppisch. “S-tree: a dynamic balanced signature index for office retrieval.” In Proceedings of the 9th annual international ACM SIGIR conference on Research and development in information retrieval, SIGIR ’86, pages 77–87, New York, NY, USA, 1986. ACM.

[5]H2DB. http://www.h2database.com/.

[6]T. J. Lehman and M. J. Carey. “A study of index structures for main memory database management systems.” In Proceedings of the 12th International Conference on Very Large Data Bases, VLDB ’86, pages 294–303, San Francisco, CA, USA, 1986. Morgan Kaufmann Publishers Inc.

[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.

[9]I. E. Shanthi, Y. Izaaz, and R. Nadarajan. “On the sd-tree construction for optimal signature operations.” In Proceedings of the 1st Bangalore Annual Compute Confer- ence, COMPUTE ’08, pages 14:1–14:8, New York, NY, USA, 2008. ACM.

[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.

[12]E. Tousidou, A. Nanopoulos, and Y. Manolopoulos. “Improved methods for signature-tree construction.” Comput. J., 43(4):300–313, December 2000.

[13]X. Zhang, L. Cheng, and Q. Zhu. “Improvement of filtering algorithm for rfid middleware using kdb-tree query index.” JSW, 6(12):2521–2527, 2011.

[14]Jvm ti. http://java.sun.com/javase/6/docs/technotes/guides/jvmti/.

[15]H. Garcia-Molina and K. Salem. “Main memory database systems: An overview.” IEEE Trans. on Knowl. and Data Eng., 4(6):509–516, 1992.

[16]K. M. Zuberi and K. G. Shin. “Emeralds: A small-memory real-time microkernel.” IEEE Trans. Softw. Eng., 27(10):909–928, 2001.

[17]D. Dervos, Y. Manolopoulos, and P. Linardis. “Comparison of signature file models with superimposed coding.” Inf. Process. Lett., 65(2):101–106, 1998.

[18]K. Finkenzeller. “RFID Handbook: Fundamentals and Applications in Contactless Smart Cards and Identification.” John Wiley &; Sons, Inc., New York, NY, USA, 2003.

[19]P. Kocher, R. Lee, G. McGraw, and A. Raghunathan. “Security as a new dimension in embedded system design.” In DAC ’04: Proceedings of the 41st annual conference on Design automation, pages 753–760, New York, NY, USA, 2004. ACM. Moderator-Srivaths Ravi.

[20]K. Kwon, Y. Yi, D. Kim, and S. Ha. Embedded software generation from system level specification for multi-tasking embedded systems. In ASP-DAC ’05: Proceedings of the 2005 conference on Asia South Pacific design automation, pages 145–150, New York, NY, USA, 2005. ACM.

[21]W. Lee and D. Lee. “Signature file methods for indexing object-oriented database systems.” In Proceedings of the 2nd International Computer Science Conference, 1992.

[22]C.-T. Lo, M. Chang, O. Frieder, and D. Grossman. “The object behavior of java object-oriented database management systems.” pages 247–252, April 2002.