Slideshow

Top 10 wicked cool algorithms

A round up of interesting algorithms and look at how they impact your community.

  • Argonne National Laboratory researchers have developed a computer algorithm that uses a technique of data assimilation and the Ensemble Adjustment Kalman Filter (EAKF) algorithm to quickly and accurately assimilate biological data into climate models to generate more reliable forecasts. Because of the high stakes involved in meeting air-quality targets, scientists, city officials and regulators all want a more accurate way not only to measure air quality but also to predict where pollution "hot spots" will occur and plan for additional control strategies. For example, when air-quality monitors and environmental regulators inspect the pollution levels of cities, the difference of one or two parts per million in the concentration of pollutants like ozone and carbon monoxide can mean the difference between achieving a target and having to implement additional costly provisions to get failing areas back on track, researchers at Argonne National Laboratory said.

  • Researchers have developed an algorithm that can look at photographic images and determine where the picture was taken. Such capability could have numerous applications such as enhancing online image search techniques or helping users find family photos from a specific trip or even forensic purposes. Determining the location of photos also makes it possible to combine them with geographic databases related to climate, population density, vegetation, and topography and land use, researchers said. The IM2GPS algorithm developed by Carnegie Mellon University analyzes the composition of the photo, notes how textures and colors are distributed and records the number and orientation of lines in the photo. It then searches GPS-tagged images in Flickr for photos that are similar in appearance, researchers said. (More information at:http://graphics.cs.cmu.edu/projects/im2gps/)

  • Imagine you could sniff out potential threats to your network before they become serious problems or expose the family jewels. That's the idea behind Air Force Institute of Technology research that uses data mining and social networking techniques to spot and stop insider security threats and industrial espionage. Researchers have developed software that can spot insider threats using an extended version of automated document indexing known as Probabilistic Latent Semantic Indexing (PLSI). This technology can discern employees' interests from e-mail and create a social network graph showing their various interactions, researchers said. The technology could help any organization sniff out insider threats by analyzing email activity or find individuals among potentially tens of thousands of employees with latent interests in sensitive topics.

  • Using blacklists to prevent spammers or other malware distributors is nothing new. But researchers at SRI International and SANS Institute want to take such lists a bit further. Recently they wrote a paper about a blacklisting system they said was based on a relevance ranking scheme borrowed from the link-analysis community. Specifically they said their system uses a link analysis method similar to Google's PageRank for blacklist formulation. The system produces customized blacklists for individuals who choose to contribute data to a centralized log-sharing infrastructure. The ranking scheme measures how closely related an attack source is to a contributor, using that attacker's history and the contributor's recent log production patterns. The researchers said their ultimate goal is to yield individualized blacklists that not only produce significantly higher hit rates, but that also incorporate source addresses that pose the greatest potential threat.

  • A sorting algorithm is a set of instructions that computer programmers use to arrange data in a particular order. The burnt pancake problem is a type of problem where an algorithm must sort elements from largest to smallest by flipping them over, much as a cook would flip a stack of differently-sized pancakes. What makes designing an algorithm for this problem particularly tricky is that before the sorting is complete, all of the elements must be flipped so that one specific side faces upward. In other words, imagine that you have a stack of pancakes where one side is burnt and one side is a perfect golden brown. In the course of sorting all of the pancakes from smallest to largest, you would obviously want to have all the golden sides facing upward at the end of the sort. The goal of designing an algorithm for the burnt pancake problem, then, is to get all the pancakes stacked from smallest to largest -- with all golden sides facing up -- in the fewest possible number of flips. (More information at: http://www.math.uiuc.edu/~west/openp/pancake.html)

  • What do you think? There are hundreds of wicked cool algorithms out there. Tell us about your favourites.

  • When it comes to creating absolutely unbelievable animation for movies, the folks at Dreamworks have it down to a science. In this case they used what they called image generation algorithms in combination with Oak Ridge National Labs Jaguar supercomputer to create the art for Kung Fu Panda. According to Dreamworks, what they had previously done was render (generate the image from the computer model) in batch mode, with lots of animators working with low-resolution models to try things out. They then had to pick their favorites and render higher resolution images overnight. This took a lot of time. Dreamworks researchers said the new breed of image-generation algorithms take advantage of multiple processing cores to dramatically accelerate the rendering process and reflect changes to the model in real time. (More information at:http://www.cyber-ta.org/pubs/hpb.pdf)

  • Algorithms are not just the playthings of lab rats. Many of them play a significant role in your daily life from helping to predict the weather to determining whether or not you ran that stop light on the way to work today. We decided to round up a few of the more interesting algorithms and look at how they impact your community.

  • IBM researchers have created specialized algorithms to help model and manage natural disasters such as wildfires, floods and diseases. The idea is to use high-level math techniques, which IBM calls Stochastic programming, to help speed up and simplify complex tasks such as determining the fastest route to deliver packages, detecting fraud in health insurance claims, automating complex risk decisions for international financial institutions, scheduling supply chain and production at a manufacturing plant to maximize efficiency or detecting patterns in medical data for new insights and breakthroughs. The model allows all unforeseen challenges to be solved, mostly within an hour, and has very good scalability that promises to gracefully manage even larger models in the future.IBM scientists developed a large-scale strategic budgeting framework based on Stochastic algorithms for managing natural disaster events, with a focus on better preparedness for future uncertain disaster scenarios. (More information at:http://www.research.ibm.com/stopro/)

  • The old saying goes everyone's a comedian. Well in this case perhaps every computer. The University of California Berkeley joke recommendation site, dubbed Jester, rates humor on a scale of "less funny" to "more funny." It then recommends jokes based on the user's taste (or lack thereof), dynamically making recommendations based on the user's most recent ratings. Jester's more than a joke jukebox though. Underlying it is a Berkeley-patented "collaborative filtering algorithm" dubbed Eigentaste. The more people who use the system and rate jokes (4 million-plus ratings have been made so far, according to a recent story on the UC Berkeley Web site) the more data Berkeley researchers have to advance their understanding of recommendation systems, such as those used by Amazon.com and other Web sites.

  • The idea is to get older, slower routers up to speed with newer, faster boxes with as little effort as possible. A team of computer scientists from the University of California at San Diego have proposed an algorithm that makes routers operate more efficiently by automatically limiting the number of network route or link-state updates they receive. The Approximate Link State (XL) algorithm suppresses the updates so only those routers that are directly affected receive them. Without XL, routers typically flood the network with route updates, with every router receiving every update. In very large networks the sheer number of routers and inevitable link-state changes would episodically grind routers to a halt. To deal with that problem, large networks are manually engineered to create areas -- conceptually isolated groups of routers -- that limit the number of routers any flood reaches. Routers still receive floods, but only from the routers within their areas. (More information at: http://www.ornl.gov/ornlhome/news_items/news_080808.shtml)

  • A number of cities are using a camera/computer system to fight the red light running scourge that exists in many intersections. The interesting thing about the system, built by Redflex, is that it uses algorithms to review pictures of red light runners and can decide who is guilty. Yes, Big Brother is watching. (More information at: http://www.cs.brown.edu/~th/papers/Hofmann-SIGIR99.pdf)

Show Comments