Mining in a mobile environment

ABSTRACT

Distributed PRocessing in Mobile Environments (DPRiME) is a framework for processing large data sets across an ad-hoc network. Developed to address the shortcomings of Google's MapReduce outside of a fully-connected network, DPRiME separates nodes on the network into a master and workers; the master distributes sections of the data to available one-hop workers to process in parallel. Upon returning results to its master, a worker is assigned an unfinished task. Five data mining classifiers were implemented to process the data: decision trees, k-means, k-nearest neighbor, Naïve Bayes, and artificial neural networks. Ensembles were used so the classification tasks could be performed in parallel. This framework is well-suited for many tasks because it handles communications, node movement, node failure, packet loss, data partitioning, and result collection automatically. Therefore, DPRiME allows users with little knowledge of networking or distributed systems to harness the processing power of an entire network of single- and multi-hop nodes.

REFERENCES

• 1: C. Pettey, "Gartner Says Worldwide Smartphone Sales Grew 29 Percent in First Quarter of 2008," Gartner, 6 June 2008, 30 July 2008 <http://www.gartner.com/it/page.jsp?id=688116>.
• 2: B. Thuraisingham, L. Khan, C. Clifton, J. Maurer, and M. Ceruti, "Dependable Real-Time Data Mining," Proceedings of the Eighth IEEE International Symposium on Object-Oriented Real-Time Distributed Computing (2005).
• 3: J. Dean and S. Ghemawat, "MapReduce: Simplified Data Processing on Large CLusters," Sixth Symposium on Operating System Design and Implementation (2004), 15 July 2008 <http://labs.google.com/papers/mapreduce.html>.
• 4: T. M. Mitchell, Machine Learning, Ed. E. M. Munson, Singapore: The McGraw-Hill Companies, Inc., 1997.
• 5: I. H. Witten and E. Frank, Data Mining: Practical Machine Learning Tools and Techniques, 2nd ed. San Francisco: Morgan Kaufmann, 2005.
• 6: K. W. Bowyer, L. O. Hall, T. Moore, and N. Chawla, "A Parallel Decision Tree Builder for Mining Very Large Visualization Data Sets," IEEE International Conference on Systems, Man, and Cybernetics 3 (2000): 1888--893.
• 7: R. Agrawal and J. C. Shafer, "Parallel Mining of Association Rules." Ieee Trans. On Knowledge And Data Engineering 8 (1996): 962--69.
• 8: G. J. Narlikar, "A Parallel, Multithreaded Decision Tree Builder," (1998).
• 9: T. G. Dietterich, "Ensemble Methods in Machine Learning." Lecture Notes in Computer Science (2000).
• 10: C. Chu, S. K. Kim, Y. Lin, Y. Yu, G. Bradski, A. Y. Ng, and K. Oluktun, "Map-Reduce for Machine Learning on Multicore."

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Data mining

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
      H.3.4 Systems and Software
          Subjects: Performance evaluation (efficiency and effectiveness); Distributed systems

  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.2 Design Methodology
          Subjects: Classifier design and evaluation

General Terms:
Algorithms, Design, Management, Performance

Keywords:
MapReduce, ad-hoc network, classifier, data mining, ensemble