臺灣博碩士論文加值系統

具規模的無線射頻識別系統在後端的資料處理常常需要高效的資料庫系統，本研究即源於這些對有效率的主記憶體資料庫索引結構的強烈需求。本研究提出了一個以簽章為基礎的網格索引結構來獲取有效率的資料搜尋及儲存能力。基於已知的應用程式知識，我們也提出了有效率的方法來辨識出重覆的插入資料和執行批次刪除，範圍搜尋等動作。這些方法都已實作在開放原始碼的主記憶體資料庫- H2，且使用真實的無線射頻識別系統工作數據來測試。

A large-scaled RFID application often needs a highly efficient database system in data processing. This research is motivated by the strong demand of an efficient index structure design for main-memory database systems of RFID applications. In this paper, a signature-based grid index structure is proposed for efficient data queries and storage. An efficient methodology is proposed to locate duplicates and to execute batch deletions and range queries based on application domain knowhow. The capability of the design is implemented in an open source main-memory database system H2 and evaluated by realistic workloads of RFID applications.

Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . v
Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
List of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
List of Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
Chapter 1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . 4
Chapter 2 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.1 System Architecture . . . . . . . . . . . . . . . . . . . . . . . . 7
2.2 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
Chapter 3 The Signature-based Grid Index . . . . . . . . . . . . . . 11
3.1 The Grid-Index Structure . . . . . . . . . . . . . . . . . . . . . 11
3.2 Signature-based Operations . . . . . . . . . . . . . . . . . . . 13
3.3 Java-Related Object Management . . . . . . . . . . . . . . . . 19
Chapter 4 Performance Evaluation . . . . . . . . . . . . . . . . . . . 22
4.1 Experimental Setup . . . . . . . . . . . . . . . . . . . . . . . . 22
4.2 Performance and Overhead Evaluation . . . . . . . . . . . . 24
Chapter 5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . 29
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

[1] K. Finkenzeller, RFID Handbook: Fundamentals and Applications in Contactless
Smart Cards and Identification. New York, NY, USA: JohnWiley
& Sons, Inc., 2003.
[2] S. E. Sarma, S. A. Weis, and D. W. Engels, “RFID Systems and Security
and Privacy Implications,” inWorkshop on Cryptographic Hardware
and Embedded Systems, vol. 2523 of Lecture Notes in Computer Science,
pp. 454–470, 2002.
[3] L. Satpathy and A. P.Mathew, “Rfid assistance system for faster book
search in public libraries,” in CHI ’06: CHI ’06 extended abstracts on
Human factors in computing systems, (New York, NY, USA), pp. 1289–
1294, ACM, 2006.
[4] K.M. Zuberi and K. G. Shin, “An efficient semaphore implementation
scheme for small-memory embedded systems,” in RTAS ’97: Proceedings
of the 3rd IEEE Real-Time Technology and Applications Symposium
(RTAS ’97), (Washington, DC, USA), p. 25, IEEE Computer Society,
1997.
[5] K. M. Zuberi and K. G. Shin, “Emeralds: A small-memory real-time
microkernel,” IEEE Trans. Softw. Eng., vol. 27, no. 10, pp. 909–928,
2001.
[6] G. B. I. Creus and P. Niska, “System-level power management for
mobile devices,” in CIT ’07: Proceedings of the 7th IEEE International
Conference on Computer and Information Technology, (Washington, DC,
USA), pp. 799–804, IEEE Computer Society, 2007.
[7] D. Rakhmatov and S. Vrudhula, “Energy management for batterypowered
embedded systems,” Trans. on Embedded Computing Sys.,
vol. 2, no. 3, pp. 277–324, 2003.
[8] 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
REFERENCES 31
Pacific design automation, (New York, NY, USA), pp. 145–150, ACM,
2005.
[9] N. Aaraj, S. Ravi, A. Raghunathan, and N. K. Jha, “Hybrid architectures
for efficient and secure face authentication in embedded systems,”
IEEE Trans. Very Large Scale Integr. Syst., vol. 15, no. 3, pp. 296–
308, 2007.
[10] 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, (New York, NY,
USA), pp. 753–760, ACM, 2004. Moderator-Srivaths Ravi.
[11] H. Garcia-Molina and K. Salem, “Main memory database systems:
An overview,” IEEE Trans. on Knowl. and Data Eng., vol. 4, no. 6,
pp. 509–516, 1992.
[12] “H2 database.” http://www.h2database.com/.
[13] “Hsql database.” http://hsqldb.org/.
[14] K.-R. Choi and K.-C. Kim, “T*-tree: a main memory database index
structure for real time applications,” in RTCSA ’96: Proceedings of the
Third International Workshop on Real-Time Computing Systems Application
(RTCSA ’96), (Washington, DC, USA), p. 81, IEEE Computer Society,
1996.
[15] T. J. Lehman, Design and performance evaluation of a main memory relational
database system (t tree). PhD thesis, 1986.
[16] T. J. Lehman and M. J. Carey, “A study of index structures for main
memory database management systems,” in VLDB, pp. 294–303,
1986.
[17] H. Lu, Y. Y. Ng, and Z. Tian, “T-tree or b-tree: Main memory database
index structure revisited,” in Australasian Database Conference, pp. 65–
73, 2000.
[18] T. A. Mueck and M. L. Polaschek, Index Data Structures in Object-
Oriented Databases. Norwell,MA, USA: Kluwer Academic Publishers,
1997.
[19] Y. Chen and Y. Chen, “Signature file hierarchies and signature graphs:
a new index method for object-oriented databases,” in SAC ’04: Proceedings
of the 2004 ACM symposium on Applied computing, (New York,
NY, USA), pp. 724–728, ACM, 2004.
REFERENCES 32
[20] W. Lee and D. Lee, “Signature file methods for indexing objectoriented
database systems,” in Proceedings of the 2nd International
Computer Science Conference, 1992.
[21] I. E. Shanthi, Y. Izaaz, and R. Nadarajan, “On the sd-tree construction
for optimal signature operations,” in Compute ’08: Proceedings of the
1st Bangalore annual Compute conference, (New York, NY, USA), pp. 1–
8, ACM, 2008.
[22] U. Deppisch, “S-tree: a dynamic balanced signature index for office
retrieval,” in SIGIR ’86: Proceedings of the 9th annual international ACM
SIGIR conference on Research and development in information retrieval,
(New York, NY, USA), pp. 77–87, ACM, 1986.
[23] E. Tousidou, P. Bozanis, and Y. Manolopoulos, “Signature-based
structures for objects with set-valued attributes,” Inf. Syst., vol. 27,
no. 2, pp. 93–121, 2002.
[24] E. Tousidou, A.Nanopoulos, and Y.Manolopoulos, “Improvedmethods
for signature-tree construction,” Comput. J., vol. 43, no. 4, pp. 300–
313, 2000.
[25] D. Dervos, Y. Manolopoulos, and P. Linardis, “Comparison of signature
filemodels with superimposed coding,” Inf. Process. Lett., vol. 65,
no. 2, pp. 101–106, 1998.
[26] C. Faloutsos, “Access methods for text,” ACM Comput. Surv., vol. 17,
no. 1, pp. 49–74, 1985.
[27] C. Faloutsos, “Signature files,” pp. 44–65, 1992.
[28] H. Lieberman and C. Hewitt, “A real-time garbage collector based on
the lifetimes of objects,” Commun. ACM, vol. 26, no. 6, pp. 419–429,
1983.
[29] C.-T. Lo, M. Chang, O. Frieder, and D. Grossman, “The object behavior
of java object-oriented database management systems,” pp. 247–
252, April 2002.
[30] “Jvmti.” http://java.sun.com/javase/6/docs/technotes/guides/jvmti/.