Darwin meets Polynomial:
Evolutionary Techniques Applied to
Hashing
Daniar
Hussain
Steven Malliaris
Presentation
This page is a brief presentation to our project. It
is the HTML version of the PowerPoint Presentation that we gave in
Washington, D.C. during the Siemens Westinghouse Competition.
GECCO-2000
I just returned from the GECCO-2000
(Genetic and Evolutionary Computation COnference) held in Las Vegas, Nevada.
It was a great trip, and though I am not yet officially old enough to
"gamble," I did drop a nickel into a random slot machine just
for the heck of it, and won 5 cents! While I was still ahead of the game,
I decided to quit :-).
Steven Malliaris and I did a poster presentation of our research in hashing.
Overall our presentation went very well, and everyone was very impressed with
our idea. I am also happy to say that I am finally an officially published
author :-) -- we had one page in the proceedings. Here is the reference:
Hussain, Daniar and Malliaris, Steven. "Evolutionary techniques
applied to hashing: An efficient data retrieval method." GECCO-2000
Proceedings, Morgan-Kaufman Publishing, pg. 760.
Papers
Abstract (PDF
Format, PS Format) published in the
Proceedings of the Genetic and Evolutionary Computation Conference 2000
held in Las Vegas, Nevada on July 8-12, 2000.
Technical Mathematical
Paper
Paper Reporting Results
& Major Conclusions (less technical
version)
Evolution in Action (some recent work into the
dynamics of our algorithm):
Distribution of
Polynomials: (0.25 density, 0.5
density, 0.75 density)
An Introduction to Genetic Algorithms
by Eric Krevice Prebys, MIT Undergraduate Mathematics Journal
Press Coverage
Click to see Johnstown-area newspaper article about us!
Siemens-Westinghouse Science and Technology Competition
Our work was presented at Carnegie Mellon
University on October 31, 1999 at the regional competition of
the Siemens-Foundation sponsored competition. This project
won the Regional Winner status and will compete in the
National Competition in Washington, DC on December 4, 1999.
Stay tuned for results from that competition!
The results are in! On December
4-6, 1999 our project competed in the national
Siemens-Westinghouse Science and Technology Competition held
in the Capital Hilton in Washington, D.C. and won top place
in the team competition! We were both astonished to say the
least on how far our little idea had taken us . . . we were
happy to participate at the regional competition, but never
imagined we would get as far as we did . . .
The moral of the story is: If you have a
great idea, do some research to find out more! Then, write a
paper reporting your results and important conclusions, and
submit it to next year's Siemens-Westinghouse Competition or
the numerous other science competitions across the country.
Its a great experience and a wonderful way to make excellent
contacts with many great people!
Code
Code for our algorithm (with supporting classes and configuration files,
single-machine version)
Code for distributed-version of our algorithm
(with supporting classes, etc., multiple-machine version)
Insightful Quotes on Evolution
Robert Frost, from “Education by Poetry”
Another
metaphor that has interested us in our times and has done all our thinking for
us is the metaphor of evolution. Never
mind going into the Latin word. The
metaphor is simply the metaphor of the growing plant or the growing thing.
And somebody very brilliantly, quite a while ago, said that the whole
universe, the whole of everything, was like unto a growing thing.
That is all. I know the
metaphor will break down at some point, but it has not failed everywhere.
It is a very brilliant metaphor, I acknowledge, though I myself get too
tired of the kind of essay that talks about the evolution of candy, we will
say, or the evolution of elevators – the evolution of this, that, and the
other. Everything is evolution.
I emancipate myself by simply saying that I didn’t get up the
metaphor and so am not much interested in it.
Charles Darwin, “The Origin of Species” 1859
The whole history of the world, although of a length quite
incomprehensible by us, will hereafter be recognized as a mere fragment of
time, compared with the ages which have elapsed since the first creature was
created.
From the war of nature, from famine and death, the production
of higher animals directly follows. There's grandeur in this view of life,
having been originally breathed into a few forms or into a single one. From so
simple a beginning, endless forms, most beautiful and most wonderful have been
and are being evolved.
In the distant future
I see open fields for far more important researches.
Psychology will be based on a new foundation; light will be thrown on the
origin of man, and his history.
Patrick Mathew, “Gardner’s Chronicle” April 7, 1860
To me the conception of this law of Nature came intuitively
as a self-evident fact, almost without an effort of concentrated thought.
Mr. Darwin here seems to have more merit in the discovery than I have
– to me it did not appear as a discovery.
He seems to have worked it out by inductive reason, slowly and with due
caution to have made his way synthetically from fact to fact onwards, while
with me it was by a general glace at the scheme of Nature that I estimated
this select production of species as an a priori recognizable fact –
an axiom, requiring only to be pointed out to be admitted by unprejudiced
minds of sufficient grasp.
Daniel C. Dennet, “Darwin’s Dangerous Idea” 1995
The theoretical power of Darwin’s abstract scheme was due
to several features that Darwin quite firmly identified, and appreciated
better than many of his supporters, but lacked the terminology to describe
explicitly. Today we could
capture these features under a single term.
Darwin had discovered the power of an algorithm.
An algorithm is a certain sort of formal processes that can be counted
on – logically – to yield a certain sort of result whenever “run” or
instantiated. Algorithms are not
new, and were not new in Darwin’s day.
Many familiar arithmetic procedures, such as long division and
balancing your checkbook, are algorithms, and so are the decision procedures
for playing perfect tic-tac-toe, and for putting a list of words into
alphabetical order. What is
relatively new – permitting us valuable hindsight on Darwin’s discovery
– is the theoretical reflection by mathematicians and logicians on the
nature and power of algorithms in general, a twentieth-century development
which led to the birth of the computer, which has led in turn, of course, to a
much deeper and more lively understanding of the powers of algorithms in
general.
