Journal of Korea Spatial Information System Society (한국공간정보시스템학회 논문지)

Korea Spatial Information System Society (대한공간정보학회)
권호 표지

Mining Frequent Trajectory Patterns in RFID Data Streams

RFID 데이터 스트림에서 이동궤적 패턴의 탐사

  • 서성보 (청주대학교 정보통신연구센터 학술연구) ;
  • 이용미 (충북대학교 전자계산학과) ;
  • 이준욱 (한국전자통신연구원) ;
  • 남광우 (군산대학교 컴퓨터정보공학과) ;
  • 류근호 (충북대학교 전기전자컴퓨터공학부) ;
  • 박진수 (청주대학교 정보통신공학부)
  • Published : 2009.03.31
Download PDF
⟨ Previous Next ⟩

Abstract

This paper proposes an on-line mining algorithm of moving trajectory patterns in RFID data streams considering changing characteristics over time and constraints of single-pass data scan. Since RFID, sensor, and mobile network technology have been rapidly developed, many researchers have been recently focused on the study of real-time data gathering from real-world and mining the useful patterns from them. Previous researches for sequential patterns or moving trajectory patterns based on stream data have an extremely time-consum ing problem because of multi-pass database scan and tree traversal, and they also did not consider the time-changing characteristics of stream data. The proposed method preserves the sequential strength of 2-lengths frequent patterns in binary relationship table using the time-evolving graph to exactly reflect changes of RFID data stream from time to time. In addition, in order to solve the problem of the repetitive data scans, the proposed algorithm infers candidate k-lengths moving trajectory patterns beforehand at a time point t, and then extracts the patterns after screening the candidate patterns by only one-pass at a time point t+1. Through the experiment, the proposed method shows the superior performance in respect of time and space complexity than the Apriori-like method according as the reduction ratio of candidate sets is about 7 percent.

이 논문은 RFID 데이터 스트림의 변화 특성을 고려하면서 단일 패스로 이동궤적 패턴을 실시간 추출하는 새로운 기법을 제안한다. RFID, 센서와 무선 네트워크 기술의 발달로 인해 현실 세계에서 실시간으로 데이터를 수집하고 유용한 패턴을 탐사하는 연구에 많은 관심이 집중되고 있다. 스트림 데이터에서 순차 패턴 또는 이동궤적 패턴을 탐사하는 기존의 연구 기법들은 반복적으로 데이터베이스 또는 트리를 탐색하는 고비용 문제점과 시간의 변화에 따르는 동적 특성을 실시간으로 패턴에 반영하지 못하는 단점이 있다. 제안하는 기법은 시간에 따라 RFID 데이터 스트림의 변화를 정확히 반영하기 위해 시간진화 그래프를 이용하여 이진 시간관계 테이블에 빈발한 2-길이 항목간 정보를 유지한다. 또한 다중 패스의 문제점을 해결하기 위해 t 시점에 이진 시간관계 테이블을 이용하여 k-길이의 후보 이동궤적 패턴을 추론하고, t+1 시점에서 후보 패턴을 검증하는 과정을 통해 k-길이 이동궤적 패턴을 단일 패스로 추출한다. 실험결과 제안하는 기법은 기존의 Apriori-계열 기법들과 비교하여 약 7% 정도 후보 패턴의 비율이 적게 생성되어 시간 및 공간 복잡도 측면에서 우수한 성능을 보였다.

Keywords

References

  1. Gonzalez, H., Han, J. and Li, X., ‘‘FlowCube: Constructing RFID FlowCubes for Multi-Dimensional Analysis of Commodity Flows,” In Proc. of 32th Int. Conf. on Very Large Database, pp. 834-845, 2006.
  2. Gonzalez, H., Han, J., Li, X. and Klabjan, D., ‘‘Warehousing and Analyzing Massive RFID Data Sets,” In Proc. of 22nd Int. Conf. on Data Engineering, pp. 83-93, 2006.
  3. Han, J., Cheng, H., Xin, D. and Yan, X., ‘‘Frequent pattern mining: current status and future directions,” Journal of Data Mining and Knowledge Discovery, Vol. 14, No.1, pp. 55-86, 2007.
  4. Zhao, Q. and Bhowmick, S. S., ‘‘Sequential Pattern Mining: A Survey,” Technical Report Center for Advanced Information Systems, School of Computer Engineering, Nanyang Technological University, Singapore, 2003.
  5. Agrawal, R. and Srikant, R., ‘‘Fast algorithms for mining association rules ,” In Proc. of 20th Int. Conf. on Very Large Database, pp. 487-499, 1994.
  6. Giannella, C., Han, J., Pei J., Yan, X. and Yu, P. S., ‘‘Mining Frequent Patterns in Data Streams at Multiple Time Granularities,” In H. Kargupta, A. Joshi, K. Sivakumar, and Y. Yesha (eds.), Next Generation Data Mining, Chapter 3, P. 191-212, AAAI/MIT, 2003.
  7. Jin, R. and Agrawal, G., ‘‘Frequent Pattern Mining in Data Streams,” In Charu C. Aggrawal (eds), Chapter 4, p. 61-84, Springer Science and Business Media, LLC., 2007.
  8. Manku, G. S. and Motwani, R., ‘‘Approximate Frequency Counts Over Data Streams,” In Proc. of 28th Int. Conf. on Very Large Database, pp. 346-357, 2002.
  9. Teng, W. G., Chen, M. G., and Yu, P. S., ‘‘A Regression-Based Temporal Pattern Mining Scheme for Data Streams,” In Proc. of 29th Int. Conf. on Very Large Database, pp. 93-104, 2003.
  10. Han, J., Pei, J., Yin, Y. and Mao, R., “Mining Frequent Patterns without Candidate Generation: A Frequent-Pattern Tree Approach,” Data Mining and Knowledge Discovery, Vol. 8, No. 1, pp. 53-87, 2004. https://doi.org/10.1023/B:DAMI.0000005258.31418.83
  11. Yunhao, L., Lei, C., Pei, J., Chen, Q. and Zhao, Y., “Mining Frequent Trajectory Patterns for Activity Monitoring Using Radio Frequency Tag Arrays,” In Proc. of 5th IEEE Int. Conf. on Pervasive Computing and Communications, 2007.
  12. Gabor Melli, Data Generator, http://www. datasetgenerator.com/
  13. 김철연, 임종화, T. Ng Raymond, 심규석, “정량 정보를 포함한 순차 패턴 마이닝 알고리즘,” 한국정보과학회 논문지 D-데이터베이스, Vol. 33, No. 5, pp 453-462, 2006.
  14. 김의찬, 김계현, 이철용, 박은지, “비트 클러스터링을 이용한 빈발 패턴 탐사의 성능 개선 방안,” 한국공간정보시스템학회 논문지 Vol.9, No.1, pp.105-115, 2007.
  15. 유기현, 남광우, “공간 데이터스트림을 위한 조인 전략 및 비용 모델,” 한국공간정보시스템학회 논문지, Vol.10, No.4, pp.59-66, 2008.
  16. 김동현, 이기형, 홍봉희, 반재훈, “RFID 태그 객체의 위치 추적을 위한 색인 구조의 설계 및 구현,” 한국공간정보시스템학회 논문지, Vol.7, No.2, pp.67-79, 2005.