Statistics_Machine

Advisor(s): Dr. Bruce Weide, Dr. Paolo Bucci
Participants: Ratnamala Bearavolu, Susan Hohenberger
Start Date: Winter Quarter 1999
Project Status: Active

Index:

Abstract
Calendar
Project Development
Findings and Contributions
Return to Europa

Abstract:

The Statistics_Machine component was designed to handle the computation of maximum, minimum, mean, median, and standard deviation on an arbitrary number of reals. A practical application would be to handle the CIS221, CIS222, CIS321 online evaluation form data. The goal was to create a clean and user friendly interface with an elegant design supporting it.

Calendar:

• Tuesday Feb 16, 1999: Presentation on overall project abstract and algorithms A, B, C
• Tuesday Feb 23, 1999: Open brainstorm in group meeting on a piece-wise algorithm for median computation in linear time
• Thursday March 4, 1999: Algorithm D added as best of batch algorithms
• Friday May 14, 1999: Findings presetented at the Ohio State University Undergraduate Research Forum
• Friday Oct 1, 1999: "Intelligent" blend of real-time and batch median algorithms discussed in Europa meeting

Project Development:

The project development state is active. We succeeded in developing and anaylzing an algorithm that produced the median in near real-time when new data additions were added to a statistics machine that was being continually queried for the median. However, this algorithm involved too much overhead to compete with the best of the batch algorithms on a single run.

Therefore, our future work is to combine the real-time and batch median algorithms into an "intelligent" median component. Using a small amount of overhead, this "intelligent" algorithm can switch between the real-time and batch algorithms to produce the median for the user with the fastest method based on how the user is using the statistics machine.

Findings and Contributions:

Statistic_Machine Operations

Insert (consumes Real x), Clear (), Size (), Maximum (), Minimum (), Mean (), Median (), Standard_Deviation ()


Representation

|Queue_of_Reals (buffer) | Real (max) | Real (min) | Real (sum) | Real (sum of squares) | Real (median) | Boolean (median_is_calculated)|


Algorithms

A: Merge Sort and Find Method

Median is computed at time of Median() call by merge sorting data and selecting middle element. Order nlogn.

B: Median of Medians Method

Median is computed at time of Median() call by selecting the median of medians as a partition and separating data. Order n.

C: Twin Binary Tree Method (Later called: near "real-time" algorithm)

Median is computed at each Insert() call by storing the items in twin binary search trees. Order nlogn (logn at each Insert()).

D: Computation Using Random Partitions Method (Later called: "best of batch" algorithm)

Median is computed at time of Median() call by generating a random partition and solving for kth in n problem. Order n-squared (averages much better).

1999 Ohio State University Undergraduate Research Forum Results

After anaylsis involving randomly generated data sets of variable sizes, we discovered ...

• Algorithm D out-performed* all other algorithms on a single median query of the statistics machine.
• Algorithm C returned the median faster by several hours on data sets that exceeded 3,000 items.

Algorithm C was implemented using a special object-oriented approached referred to as "recasting" the algorithm as an object. Unlike Algorithms A, B, and D, this recasted algorithm was completely designed by the authors of this research. The primary need to do this was because all other median algorithms described in text books were for batch applications (single runs). However, these algorithms produce horrible results if the user wishes to insert data, ask for the median, insert more data ask for the median again, and so on. This is the central reason that most real-time applications use a mean approximation in place of the median.

However, there are cases, such as noise reduction in electrical engineering, that could be enhanced by using the median instead of a mean approximation if an efficient median algorithm were known to exist. Our research developed such an algorithm. But we discovered the downfall of this algorithm to be that although it could produce the median in constant time after one new data insertion (thereby performing superbly in a real-time environment), it performed terribly on a batch run of the data.

Our conclusions at the research forum indicated that "recasting" algorithms as objects can open up the possibilities of algorithm development in many areas just as it made it possible to create algorithm C in the median arena. Specifically for median compuation, we reported that repeatedly queried real-time applications for median could be realized with algorithm C, but that for batch algorithms it was more efficient to stick with D, the best of the batch algorithms.

The above ends our findings at the OSU Research Forum. However, over the summer Ratna and I asked ourselves "What if you could have the best of both worlds? What if you could have one algorithm that performed well in both batch and real-time applications?" Therefore, our future work is to combine the real-time and batch median algorithms into an "intelligent" median component. Using a small amount of overhead, we propose that this "intelligent" algorithm can switch between the real-time and batch algorithms producing the median with the fastest possible method based on how the user is using the statistics machine. This exciting question not only fuels further algorithm study, but also explores the fundamentals of object-oriented programming and introduces concepts of artifical intelligence.

  Return to Europa

Last modified: Sat Dec 4 19:26:00 EST 1999