We use cookies to improve your experience with our site.

Indexed in:

SCIE, EI, Scopus, INSPEC, DBLP, CSCD, etc.

Submission System
(Author / Reviewer / Editor)
Hai-Long Liu, Qun Chen, Zhan-Huai Li. Optimization Techniques for RFID Complex Event Processing[J]. Journal of Computer Science and Technology, 2009, 24(4): 723-733.
Citation: Hai-Long Liu, Qun Chen, Zhan-Huai Li. Optimization Techniques for RFID Complex Event Processing[J]. Journal of Computer Science and Technology, 2009, 24(4): 723-733.

Optimization Techniques for RFID Complex Event Processing

Funds: This work is supported by the National Natural Science Foundation of China under Grant No. 60720106001.
More Information
  • Author Bio:

    Hai-Long Liu is currently a postgraduate student at School ofComputer, Northwestern Polytechnical University, Xi'an, China.He is a student member of China Computer Federation. His currentresearch interest is data management technologies.

    Qun Chen is currently a professor at School of Computer,Northwestern Polytechnical University, Xi'an, China. He is amember of China Computer Federation. He receivedhis Ph.D. degree in computer science from National University ofSingapore in 2003. Between 2004 and 2006, he was a researchassociate in Hong Kong University of Science and Technology. Hisresearch interests include RFID data management, XML databasetechnologies and Web service technologies. He has published dozensof research papers in top ranked database conferences and journals.He is also a technology consultant to many mainland and HKcompanies.

    Zhan-Huai Li is a professor at School of Computer,Northwestern Polytechnical University, Xi'an, China. He is vicedean of the school and vice chairman of Database Technical Committee,China Computer Federation. He is a senior member of ChinaComputer Federation. He received his Master's and Ph.D. degrees fromNorthwestern Polytechnical University in 1987 and 1996 respectively.His current research interests include RFID data management andmultimedia real-time database.

  • Received Date: July 17, 2008
  • Revised Date: April 20, 2009
  • Published Date: July 04, 2009
  • One research crucial to wider adoption of Radio Frequency Identification (RFID) technology is how to efficiently transform sequences of RFID readings into meaningful business events. Contrary to traditional events, RFID readings are usually of high volume and velocity, and have the attributes representing their reading objects, occurrence times and spots. Based on these characteristics and the Non-deterministic Finite Automata (NFA) implementation framework, this paper studies the performance issues of RFID complex event processing and proposes corresponding optimization techniques. Our techniques include: (1) taking advantage of negation events or exclusiveness between events to prune intermediate results, thus reduces memory consumption; (2) with different selectivities of complex events, purposefully reordering the join operations between events to improve overall efficiency, achieve higher stream throughput; (3) utilizing the slot-based or B+-tree-based approach to optimizing the processing performance with the time window constraint. We present the analytical results of these techniques and validate their effectiveness through experiments.
  • [1]
    Doerr K H, Gates W R, Mutty J E. A hybrid approach to the evaluation of RFID/MEMS technology applied to ordinance inventory. International Journal of Production Economics, 2006, 103(2): 726-741.
    [2]
    Lee Y M, Cheng F, Leung Y T. Exploring the impact of RFID on supply chain dynamics. In Proc. the 2004 Winter Simulation Conference (WSC 2004), Washington DC, USA, December 5-8, 2004, pp.1145-1152.
    [3]
    Delen D, Hardgrave B C, Sharda R. RFID for better supplychain management through enhanced information visibility. White Paper, Information Technology Research Institute, University of Arkansas, 2007, http://itri.uark.edu.
    [4]
    Hakim H, Renouf R, Enderle J. Passive RFID asset monitoring system in hospital environments. In Proc. the 32nd Annual Northeast Bioengineering Conference, Easton, PA, USA, April 1-2, 2006, pp.217-218.
    [5]
    Shariq R, Jeffery S R, Krishnamurthy S et al. Events on the edge. In Proc. Int. Conf. Management of Data (SIGMOD 2005), Baltimore, Maryland, USA, June 13-16, 2005, pp.885- 887.
    [6]
    Zhang X L, King B. An anti-counterfeiting RFID privacy protection protocol. Journal of Computer Science and Technology, May 2007, 22(3): 627-644.
    [7]
    Li Z K, Gadn R, Prabhu B S. Applications of RFID technology and smart parts in manufacturing. In Proc. ASME 2004 Design Engineering Technical Conferences and Computers and Information in Engineering Conference (DETC'04), Salt Lake City, Utah, USA, September 28-October 2, 2004, pp.DETC2004-57662.
    [8]
    Mark Palmer. Seven principles of effective RFID data management. 2004, http://www.progress.com/realtime/docs/articles/7principles rfid mgmnt.pdf.
    [9]
    Carey D, Cetintemel U, Cherniack M et al. Monitoring streams | A new class of data management applications. In Proc. the 28th Int. Conf. Very Large Data Bases (VLDB 2002), Hong Kong, China, August 20-23, 2002, pp.215-226.
    [10]
    Jianjun C, Dewitt D J, Feng T et al. NiagaraCQ: A scalable continuous query system for Internet databases. In Proc. Int. Conf. Management of Data (SIGMOD 2000), Dallas, Texas, USA, May 16-18, 2000, pp.379-390.
    [11]
    Chandrasekaran S, Cooper O, Deshpande A et al. TelegraphCQ: Continuous dataflow processing for an uncertain world. In Proc. the First Biennial Conference on Innovative Data Systems Research (CIDR 2003), Asilomar, CA, USA, January 5-8, 2003, pp.269-280.
    [12]
    Chakravarthy S, Krishnaprasad V, Anwar E, Kim S. Composite events for active databases: Semantics, contexts and detection. In Proc. the 20th Int. Conf. Very Large Data Bases (VLDB'94), Santiago de Chile, Chile, September 12- 15, 1994, pp.606-617.
    [13]
    Gatsiu S, Dittrich K R. Events in an active object-oriented database system. In Proc. the 1st International Workshop on Rules in Database Systems (RIDS), Edinburgh, Scotland, August 30-September 1, 1993, pp.23-39.
    [14]
    Gehani N H, Jagadish H V, Shemueli O. Composite event specification in active databases: Model and implementation. In Proc. the 18th Int. Conf. Very Large Databases (VLDB'92), Vancouver, Canada, August 23-27, 1992, pp.327- 338.
    [15]
    Meo R, Psaila G, Ceri S. Composite events in chimera. In Proc. the 5th Int. Conf. Extending Database Technology (EDBT'96), Avignon, France, March 25-29, 1996, pp.56-76.
    [16]
    Eugene W, Yanlei D, Shariq R. High-performance complex event processing over streams. In Proc. the International Conference on Management of Data (SIGMOD 2006), Chicago, Illinois, USA, June 27-29, 2006, pp.407-418.
    [17]
    Zimmer D, Unland R. On the semantics of complex events in active database management systems. In Proc. the 15th International Conference on Data Engineering (ICDE 1999), Sydney, Australia, March 23-26, 1999, pp.392-399.
    [18]
    Hinze A. Efficientfiltering of composite events. In Proc. the 20th British National Database Conference (ICDE 1999), BNCOD 20 Coventry, UK, July 15-17, 2003, pp.207-225.
    [19]
    Gruber R, Krishnamurthy B, Panagos E. CORBA notification service: Design challenges and scalable solutions. In Proc. the 17th International Conference on Data Engineering (ICDE , Heidelberg, Germany, April 2-6, 2001, pp.13-20.
    [20]
    Franklin M J, Jeffery S R, Krishnamurthy S et al. Design considerations for high fan-in systems: The HiFi approach. In Proc. the 2nd Biennial Conf. Innovative Data Systems Research (CIDR 2005), Asilomar, CA, USA, Jan. 4-7, 2005, pp.290-304.
    [21]
    Fusheng W, Peiya L. Temporal management of RFID data. In Proc. the 31st Int. Conf. Very Large Data Bases (VLDB 2005), Trondheim, Norway, Aug. 30-Sept. 2, 2005, pp.1128- 1139.
    [22]
    Fusheng W, Shaorong L, Peiya L et al. Bridging physical and virtual worlds: Complex event processing for RFID data streams. In Proc. the 10th Int. Conf. Extending Database Technology (EDBT 2006), Munich, Germany, Mar. 26-31, 2006, pp.588-607.
    [23]
    Gonzalez H, Han J W, Li X L, Klabjan D. Warehousing and analyzing massive RFID data sets. In Proc. the 22nd International Conference on Data Engineering (ICDE 2006), Atlanta, GA, USA, April 3-8, 2006, pp.83-92.
    [24]
    Gonzalez H, Han J W, Li X L. FlowCube: Constructing RFID flowcubes for multi-dimensional analysis of commodity flows. In Proc. the 32nd Int. Conf. Very Large Data Bases (VLDB 2006), Seoul, Korea, September 12-15, 2006, pp.834-845.
    [25]
    Chandrasekaran S, Cooper O, Deshpande A et al. TelegraphCQ: Continuous dataflow processing. In Proc. the Int. Conf. Management of Data (SIGMOD 2003), San Diego, California, USA, June 9-12, 2003, p.668.
    [26]
    Seshadri P, Livny M, Ramakrishan R. The design and implementation of a sequence database system. In Proc. the 22nd Int. Conf. Very Large Data Bases (VLDB'96), Mumbai (Bombay), India, September 3-6, 1996, pp.99-110.
    [27]
    Sadri R, Zaniolo C, Zarkesh A et al. Expressing and optimizing sequence queries in database systems. ACM Transactions on Database Systems (TODS), 2004, 29(2): 282-318.
    [28]
    Aguilera M K, Strom R E, Sturman D C et al. Matching events in a content-based subscription system. In Proc. the 18th Annual ACM Symp. Principles of Distributed Computing (PODC'99), Atlanta, Georgia, USA, May 3-6, 1999, pp.53-61.
    [29]
    Fabret F, Jacobsen H A, Llirbat F et al. Filtering algorithms and implementation for very fast publish/subscribe. In Proc. the Int. Conf. Management of Data (SIGMOD 2001), Santa Barbara, California, USA, May 21-24, 2001, pp.115-126.
    [30]
    Demers A, Gehrke J, Hong M et al. Towards expressive publish/subscribe systems. In Proc. the 10th International Conference on Extending Database Technology (EDBT 2006), Munich, Germany, March 26-31, 2006, pp.627-644.
    [31]
    Mert A, Cetintemel U, Nesime T. Plan-based complex event detection across distributed sources. In Proc. the 34th Int. Conf. Very Large Data Bases (VLDB 2008), Auckland, New Zealand, August 24-30, 2008, pp.66-77.
  • Related Articles

    [1]Wooseok Ryu, Bonghee Hong, Joonho Kwon, Ge Yu. A Reprocessing Model for Complete Execution of RFID Access Operations on Tag Memory[J]. Journal of Computer Science and Technology, 2012, 27(1): 213-224. DOI: 10.1007/s11390-012-1218-z
    [2]Da Teng, Shou-Bao Yang, Wei-Qing He, Yun Hu. QoS-TEOS: QoS Guaranteed Throughput-Effciency Optimal Distributed Scheduling in WiMAX Mesh Networks[J]. Journal of Computer Science and Technology, 2010, 25(5): 970-981. DOI: 10.1007/s11390-010-1077-4
    [3]Santi Marti nez, Magda Valls, Concepcio Roig, Josep M. Miret, Francesc Gine. A Secure Elliptic Curve-Based RFID Protocol[J]. Journal of Computer Science and Technology, 2009, 24(2): 309-318.
    [4]Gu Ning, Lin Zongkai, Guo Yuchai. On Model, Memory Management and Interface in EDBMS/3[J]. Journal of Computer Science and Technology, 1998, 13(4): 337-347.
    [5]Hu Weiwu, Shi Weisong, Tang Zhimin. A Framework of Memory Consistency Models[J]. Journal of Computer Science and Technology, 1998, 13(2): 110-124.
    [6]Zhou Jianqiang, Xie Li, Dai Fei, Sun Zhongxiu. Adaptive Memory Coherence Algorithms in DSVM[J]. Journal of Computer Science and Technology, 1994, 9(4): 365-372.
    [7]Jin Guohua, Chen Fujie. On the Problem of Optimizing Parallel Programs for Complex Memory Hierarchies[J]. Journal of Computer Science and Technology, 1994, 9(1): 1-26.
    [8]Shen Meiming, Tian Xinmin, Wang Dingxing, Zheng Weimin, Wen Dongchan. Optimized Parallel Execution of Declarative Programs on Distributed Memory Multiprocessors[J]. Journal of Computer Science and Technology, 1993, 8(3): 43-52.
    [9]Jin Guohua, Chen Fujie. Optimizing FORTRAN Programs for Hierarchical Memory Parallel Processing Systems[J]. Journal of Computer Science and Technology, 1993, 8(3): 19-30.
    [10]S. T. Chanson, L. Liang, A. Kumar. Throughput Models of CSMA Network with Stations Uniformly Distributed along the Bus[J]. Journal of Computer Science and Technology, 1987, 2(4): 243-264.

Catalog

    Article views (30) PDF downloads (2348) Cited by()
    Related

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return