Open Access Open Access  Restricted Access Subscription or Fee Access

Finding Frequently Occurring Paths of Flying Objects Using FP-Tree Approach

Arthur A. Shaw, N.P. Gopalan

Abstract


During the last two decades frequent pattern mining has been an emerging and active field in data mining research. In this work the process of applying algorithms to extract specific patterns from data sets from a particular domain plays a significant role. Ear-lier methods to mine frequently occurring paths of objects in spatial–temporal databases adopt complex algorithms and require many data-base scans. In this paper a modified frequent pattern tree (FP_tree) algorithm is used to find the frequently occurring paths of flying objects by two phase process. Initially, the flying object paths data-base (2D) is scanned to generate the condensed smaller data structure called FP_tree so as to compress the data and make traversal fast. Finally, the database is scanned using a partition based divide and conquer method to decompose the mining task into a set of smaller tasks for FP_tree based mining frequent paths of flying objects. The proposed algorithm outperforms the mining frequent trajectory pat-terns in spatial–temporal databases approach in terms of number of scans and candidate set generation. This may be applied to interesting game domains and find the frequently occurring paths of a ball shot by a player in some games which follows a trajectory path.

Keywords


Data Mining, FP_tree, Frequent Pattern, Frequent Trajectory Pattern and Trajectory Data Mining.

Full Text:

PDF

References


Arthur .A. Shaw (2010) Finding Frequently Occurring Paths of Flying Objects by FP-Tree Approach. In Proceedings of the Int’l Conference on Information and Communication Technology - ICICT 2010.

H. Cao, N. Mamoulis, D.W. Cheung, (2007). Discovery of periodic patterns in spatiotemporal sequence, IEEE Transactions on Knowledge and Data Engineering 19 (4) (2007) 453–467.

Anthony J.T. Lee , Yi-An Chen, Weng-Chong Ip (2009). Mining fre-quent trajectory patterns in spatial–temporal databases. In the journal of Information Sciences 179 (2009) 2218–2231.

Hans-Peter Kriegel, Karsten M.Borgwardt, Peer Kröger, Alexey Pryak-hin, Matthias Schubert, Arthur Zimek, (2007). Future trends in data min-ing. In the Springer Journal Data Mining and Knowledge Discovery, Volume 15, Number 1 / August, 2007, 23 March 2007.

Fayyad U, Piatetsky-Shapiro G, Smyth P (1996). Knowledge discovery and data mining: Towards a unifying framework. In: Proceedings of the 2nd ACM international conference on knowledge discovery and data mining (KDD), Portland, OR, pp 82–88.

Han, J. and M. Kember, 2001. Data Mining: Concepts and Techniques. Morgan Kauffmann Publishers.

Agrawal R, Imielinski T, Swami A (1993) Mining association rules between sets of items in large databases. In: Proceedings of the 1993ACM-SIGMOD International conference on management of data (SIGMOD’93), Washington, DC, pp 207–216.

J. Han, J. Pei, B. Mortazavi-Asl, Q. Chen, U. Dayal, M.C. Hsu, Mining frequent patterns without candidate generation, in: Proceedings of the ACM SIGMOD Int’l Conf. on Management of Data, 2000, pp. 1–12.

Agarwal R, Aggarwal CC, Prasad VVV (2001) A tree projection algo-rithm for generation of frequent itemsets. J Parallel Distributed Compu-ting 61: 350–371.

Pei J, Han J, Lakshmanan LVS (2001) Mining frequent itemsets with convertible constraints. In: Proceeding of the 2001 Int’l Conf. on data engineering (ICDE’01), Heidelberg, Germany, pp 433–332.

Liu J, Pan Y, Wang K, Han J (2002) Mining frequent item sets by op-portunistic projection. In: Proceeding of the 2002 ACM SIGKDD inter-national conference on knowledge discovery in databases (KDD’02), Edmonton, Canada, pp 239–248.

Liu G, Lu H, Lou W, Yu JX (2003) on computing, storing and querying frequent patterns. In: Proceeding of the 2003 ACM SIGKDD interna-tional conference on knowledge discovery and data mining (KDD’03), Washington, DC, pp 607–612.

Grahne G, Zhu J (2003) efficiently using prefix-trees in mining frequent itemsets. In: Proceeding of the ICDM’03 Int’ll workshop on frequent itemset mining implementations (FIMI’03), Melbourne, FL, pp 123–132.

United States Patent Application Publication – Baseball Practice Sys-tems, Pub. No.: US2009/0163301 A1, Inventors: John Flading, Marietta, GA (US) and Larry Duan Cripe, Seattle, WA (US).

United States Patent Application Publication – Trajectory Detection and Feedback System for Tennis, Pub. No.: US2008/0200287 A1, Inventors: Marty, Alan W. (Menlo Park, CA, US) and Edwards, Thomas A. (Menlo Park, CA, US).

Han, J., Pei, J., Yin, Y. & Runying Mao, (2004). Mining Frequent Pat-terns without Candidate Generation: A Frequent Pattern Tree Approach. In the Data Mining and Knowledge Discovery, 8, 53-87, 2004.

Agrawal R, Srikant R (1995) Mining sequential patterns. In: Proceedings of the 1995 Int’l conference on data engineering (ICDE’95), Taipei, Taiwan, pp 3–14.


Refbacks

  • There are currently no refbacks.


Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.