MINING IN A MOBILE ENVIRONMENT, [S. T. McRoskey]{.underline}, [J. H.
Notwell]{.underline}, N. V. Chawla\*, C. Poellabauer\*, University of
Notre Dame, Department of Computer Science and Engineering, Notre Dame,
IN 46556, cpoellab@cse.nd.edu

Wireless ad-hoc networks are increasingly being investigated for a
variety of mobile computing applications, including sensor networks,
mobile ad-hoc networks (MANETs), wireless mesh networks, robust
communication among first responders, and social networking tools. In
another area of computer science there is an increasing desire to
perform real-time data mining. Currently, data mining largely takes
place long after the data have been collected; performing these tasks in
real-time requires using the limited resources available in the
environments where data are collected. Processing large amounts of data
on mobile and sensing devices is taxing on their processors, memory, and
batteries. Therefore, the challenge is to (a) build a framework that
robustly supports the efficient distribution of knowledge extraction
tasks and (b) study and re-design data mining techniques to match the
constraints and requirements of resource-constrained wireless
environments.

The proposed solution, called Distributed PRocessing in Mobile
Environments (DPRiME), represents an abstract framework and associated
implementation for processing large data sets in a distributed wireless
environment. DPRiME is based on Google's MapReduce, which is a solution
to process vast amounts of data on many commodity machines. A strict
implementation of MapReduce in a mobile environment is not possible
because it relies on a fully-connected network and shared storage space,
i.e., features not found in wireless networks. Therefore, DPRiME
specifically focuses on the challenges of knowledge extraction in mobile
environments, including unreliable wireless communications, node
mobility, node failure, packet loss, data partitioning, and automatic
result collection.

A distributed knowledge extraction task is initiated when a user inputs
a data set, a processing function, and any required processing
parameters on a device, which becomes the master device. The master then
pings its one-hop neighbors and waits for their responses. Available
worker devices respond and the master partitions the data with respect
to the number of workers, i.e., a task is then sent to each worker. A
worker may decide to also ping its one-hop neighbors and delegate some
of the processing task to its neighbors, thereby serving as their
master. When a worker has completed its task (or collected all results
from its workers), the results are sent back to the master. Like
MapReduce, DPRiME incorporates a back-up functionality, i.e., each
master maintains a list of tasks, through which it continually loops and
assigns any unfinished tasks to idle workers until all tasks are
completed.

Communication between devices is implemented using UDP, with several
acknowledgement and retransmission features added to the framework on
top of UDP. These features are essential to ensure robust communication
in dynamic environments, without the overheads and connection-oriented
communication imposed by TCP. In addition, to address the high cost of
worker's losing contact with their master, Dynamic Source Routing (DSR)
is used as a simple means for workers to find a route back to their
master.

Five data mining classifiers were implemented across this framework:
decision trees, k-means, k-nearest neighbor, naive Bayes, and artificial
neural networks. Ensembles were selected to perform the classifications
in parallel for their ability to generate highly accurate classification
results. Ensembles operate by splitting the data into many pieces and
training a classifier on each piece. Each classifier is then used to
classify test examples, with their majority vote used to determine the
final classification.

Our preliminary results indicate DPRiME is highly effective for
processing data-intensive tasks. Their classification performance was
evaluated in three different scenarios: one master; one master and two
one-hop workers; and one master, two one-hop workers, and four two-hop
workers. Unsurprisingly, k-nearest neighbor took the longest and
exhibited the greatest improvement when distributed across this
framework. This is because, unlike the other classifiers, no model was
created for classification. K-means, which took the least amount of
time, performed worse when distributed across our framework because the
additional communication costs outweighed the benefits of using multiple
devices to process a task. Thus, DPRiME performs best for data intensive
tasks, where communication overheads are only a small fraction of total
time, allowing users with little knowledge of networking or distributed
systems to harness the processing power of an entire network of single-
and multi-hop nodes.

This work was supported by National Science Foundation Grant
CNS-0754933.