CS Prof Krishna Palem Explores the Art of Inexactness

Krishna PalemFrom the exact sums of an abacus to the ones and zeroes of a binary numeral system to the rules governing the output of a Turing machine, the calculations of computing devices leave no room for guesswork. So why does a Rice University computer science professor now want only approximate results?

“To save time and money,” said Krishna Palem, the Kenneth and Audrey Kennedy Professor of Computer Science. The resources required to get bigger, better, and more exact answers have grown extraordinarily in the last decades. Palem said, “Yes, we could consume the energy of a small city to improve climate science research, but is that the best use of our resources?” Palem thinks not, and he’s received a Guggenheim fellowship in order to advance the use of inexactness in climate science.

Solving big problems is still high on his radar, but Palem realizes the need for a new approach to high-performance computing. To explain, he uses the example of collecting virtual creatures in one of the hottest games of the summer, Pokémon GO. “A player might spend a lot of time calculating an exact, best possible route to amass the most Pokémon, but most people prefer playing the game to planning it. They choose a ‘good enough’ route that might be less effective, but provides immediate satisfaction.” This concept, also known as satisficing, was first introduced in 1956 by Nobel prize laureate Herbert A. Simon.

Is ‘good enough’ an adequate result for weather modeling tools or for improved energy efficiency in cars, drones and airplanes? Palem is aware of the risks of cutting corners, so he’s advocating a controlled risk environment. “What we propose is producing cheaper answers that still meet the user’s requirements,” he said. “So how much compromise is acceptable?”

Like his colleague, Robert “Corky” Cartwright, Palem recognizes that humans accept compromise on a daily basis –from estimating drive times in traffic to using mobile phone calculator apps that can only carry a few decimal points. Apparently, browsing photos is another area where humans demonstrate a high tolerance for ‘good enough’ results.

Palem’s research team demonstrated a digital software video decoder that used inexact interpretations of insignificant data bits to project pixels on the audience screens. “It was something like a magician’s trick,” he said. “The human eye can connect missing or inexact dots in order to see a different image that what is actually there.” In the same way, computers can be taught to ignore missing information or even skip insignificant steps in order to complete a command with ‘good enough’ results.

This summer, his research team developed another ‘good enough’ application that dramatically saves energy yet produces faster results. When it comes to mobile location services, traditional GPS-based apps rapidly consume battery life, and apps that depend on public wifi networks pose privacy risks. Working with CS colleagues Anshumali Shrivistava and a team at Seoul National University, he linked pattern-matching features with an internal map in a Samsung Galaxy S4 mobile phone.

Similar to apps like Planet Earth, their system required a user to download a local map. Unlike Planet Earth, the user’s phone does not use GPS to pinpoint locations while traveling.

“Let’s say you and your friends are deep in conversation while walking through the Galleria complex. You’ve gone up and down escalators and crossed over several overhead walkways. Suddenly you want ice cream, but where are you? Snap a photo of the store windows in front of you, and load it into our system. The photo is matched to photos associated with the Galleria map you downloaded before you left home, and the app reveals you are at Nordstrom.”

The calculation has been made without sacrificing hours of battery life or exposing your device to public wifi. Compared to similar calculations on supercomputers in the cloud, the answer is both fast and accurate. Palem’s research team found that the cloud would use 2100 or more units of energy to produce the answer in 1000 seconds. Their pattern-matching app required only 3.77 units of energy and yielded the result in 1.92 seconds.

“As for accuracy, we lose less than 1% going with the faster, cheaper method,” said Palem. “The actual accuracy lost is .89% – that’s ‘point 89’ percent – but we gain over 500% savings in time and energy and it preserves privacy 100%.”

Krishna Palem joined the CS faculty at Rice University in 2007.