New Video Surveillance Technology 'Recognizes' Abnormal Activity

BRS software can establish 'normal' on-camera activity – and alert security staff when something unusual occurs

The problem with video surveillance cameras is that, usually, there are too many of them for one security staffer to monitor. In a typical large enterprise setup, a single officer might be monitoring dozens -- even hundreds -- of cameras simultaneously, making it impossible to immediately recognize suspicious activity.

"To be honest, it's sheer luck if a security officer spots something in an environment like that," says John Frazzini, a former U.S. Secret Service agent and IT security consultant. "If you get a security manager alone behind closed doors, a lot of them laugh about what a waste of money it is."

Frazzini recently signed on to serve as president of a new company -- Behavioral Recognition Systems, or BRS Labs for short -- that aims to stop that waste. BRS Labs, which is launching both its business and its technology today, has received 16 patents on a new video surveillance application that can convert video images into machine-readable language, and then analyze them for anomalies that suggest suspicious behavior in the camera's field of view.

Unlike current video surveillance gear -- which requires a human to monitor it or complex programming that can't adapt to new images -- BRS Labs's software can "learn" the behavior of objects and images in a camera's field of view, Frazzini says. It can establish "norms" of activity for each camera, then alert security officers when the camera registers something abnormal in its field of view.

"It works a lot like the behavioral software that many IT people use on their networks," Frazzini says. "It establishes a baseline of activity, and then sends alerts when there are anomalies. The big difference is that, until now, there was no way to do this kind of analysis on video images, because the data collected by the cameras wasn't machine readable. We had to invent a way to do that."

The BRS Labs software can establish a baseline in anywhere from 30 minutes to several hours, depending on how much activity the camera recognizes and how regular the patterns of behavior are. "If you're monitoring a busy highway, where traffic comes and goes frequently on a regular basis, [the software] learns very quickly," Frazzini says. "If you're monitoring an outdoor fence line when the camera sees only three or four actions all day, it will take longer."

Once the software is operational, it can "recognize" up to 300 objects and establish a baseline of activity. If the camera is in a wooded area where few humans ever go, it will alert officers when it registers a human on the screen. If it is monitoring a high fence line, it will send an alert when someone jumps the fence.

"The great thing about it is that you don't need a human to monitor the camera at all," Frazzini says. "The system can recognize the behavior on its own."

Because there are so many possible images that might cross in front of the camera, the BRS Labs technology will likely create a fair number of false positives, Frazzini concedes. "We think a three-to-one ratio of alerts to actual events is what the market will accept," he says. "We could be wrong."

Overall, however, the new technology should save enterprises money, because security officers can spend their time diagnosing alerts and less time watching their screens for anomalies. And the system is more accurate than human monitoring, he says.

"What we've seen so far is enterprises spending billions on video surveillance equipment, but having a lot of trouble proving a [return on investment]," Frazzini says. "What we're doing is helping them to get more out of that equipment."

The BRS Labs technology will be generally available in September. Pricing hasn't been finalized -- early implementations have ranged anywhere from $1,500 to $4,500 per camera.

Credits.

Cold war era hack

IBM SELECTRIC TYPEWRITER... Because the Selectric coupled a motor to a mechanical assembly, pressing different keys caused the motor to draw different amounts of current specific to each key. By closely measuring the current used by the typewriter, it was possible to determine what was being typed on the machine. To prevent such measurements, State Department Selectric typewriters were equipped with parts that masked the messages being typed.


View slideshow

Credits.

An Algorithm to Turn Melodies Into Songs

New software creates chord progressions to accompany singers of all abilities

PHOTO: Emily Shur/Getty Images

11 July 2008—We all occasionally catch ourselves humming a tune, or singing along to the radio. What separates most of us from real musicians is the knowledge and skill to turn a hummed melody into a complete song. Three researchers in Washington state, however, aim to bridge at least some of that gap.

They've created a program called MySong that can generate a chord progression to fit any vocal melody. You simply sing into a computer microphone to the beat of a digitized metronome, and MySong comes up with an accompaniment of chords that sounds good with it. “Lots of songs have only three chords,” says Sumit Basu of Microsoft Research, a cocreator of MySong. “If you have the melody, it seems like you ought to be able to predict what the chords are.” Basu and his collaborators—Dan Morris, a Microsoft Research colleague, and Ian Simon, a Ph.D. student at the University of Washington, Seattle—will show off some of their program's features at The Twenty-Third AAAI Conference on Artificial Intelligence next week.

For any given melody, there's no such thing as a “correct” chord progression. But we tend to like songs with patterns we're used to hearing. When a musician begins fitting chords to a melody, the choices are guided by a lifetime of listening to other songs and figuring out why they sound good. MySong's creators gave their program a similar musical education by assembling a library of nearly 300 songs in the form of lead sheets, sheet music where written-out chords—such as C major, A minor, G major—accompany a single melody line. (For examples of lead sheets, check out Wikifonia, whose songs form the basis of MySong's library).

By analyzing this library, MySong creates probability tables that calculate two factors. For a given chord, which chords are most likely to proceed or follow it? And for each chord, which melody notes are likely to appear with it? These probability tables essentially give MySong mathematically derived music theory from pop music itself.

After a user records a vocal track, MySong initially provides two ways to alter the generated chord progressions, both in the form of slider bars. One slider affects how much weight each of the two probabilities is given: whether a chord best matches the vocal melody notes or whether it best fits in with the chords that surround it. The second slider allows the user to weight between major (happy-sounding) and minor (sad-sounding) keys.

“Typically in other machine-learning approaches, the blending would be fixed by whoever develops it,” says Morris. “Rather than fixing it in our code, we put that on a slider and exposed it to the user as an extra creative degree of freedom.” This concept of opening to amateur users the hidden mathematics of the underlying model is one of the topics the researchers will discuss at the AAAI conference. “With just a few clicks you can actually do a lot of manipulation and get a lot of different feels to accompany what you're doing,” adds Basu.

The technology behind MySong goes beyond simple modeling of song structure: before it can do anything else, it first has to make sense of the imprecise acoustic sounds we call singing. “The voice is a real challenge,” says Basu, who notes that most people, including trained singers, use some vibrato, where the voice vibrates above and below the intended note. Although computers can accurately track pitch, it's difficult for them to determine the exact notes the singer meant to sing.

MySong's team realized that they could work around the complexities of the voice by requiring the user to pick a tempo and sing along with a digitized metronome so that the melody maps to uniform units of time. MySong takes frequency samples 100 times a second, and, rather than trying to accurately assemble a melody from those frequencies, it keeps track of how often each frequency appears during a user-defined number of beats. This quantity over quality approach means that the chord selected for a measure best fits those notes hit most often or held the longest.

MySong's novelty, says Christopher Raphael, an associate professor of informatics at Indiana University, is in this ability to avoid technical problems rather than solve them. He also sees promise in the program's ability to engage novices, a sentiment echoed by Gil Weinberg, director of music technology at Georgia Tech. “I believe everyone has the ability to express themselves by singing songs or banging on something,” says Weinberg. “What's nice about the voice is that you don't even need an object to bang on.” Weinberg says he hopes that MySong will provide a gateway for further learning. “Many students just don't get to the expressive and creative portion of music, because there's so much technique and theory in the beginning,” he says.

Basu, Morris, and Simon may write software by day, but they each spend much of their free time writing and performing music. “We're kind of casual, amateur musicians who love making music,” says Morris. In one test of MySong's abilities, they pitted some of the chord progressions they wrote for their own songs against those chosen by the software. A blind jury of experienced musicians consistently rated MySong's chord progressions nearly as high as it rated those chosen by human musicians.

For Basu, such success was bittersweet triumph. “It made me feel proud for MySong, but these were the chords I had slaved over,” he laughs. “But when I listened to what MySong had chosen, it was often more interesting that what I had done.”

Since developing MySong, Basu used the program to assist him in the early stages of songwriting. “Dan [Morris] always jokes that I'm the one user of MySong,” says Basu. “There are progressions I use now in my music that I learned from MySong.”

As a user and creator, Basu emphasizes that MySong is meant for creativity assistance rather than creativity replacement. “The creative spark still has to come from people,” he says, “and one of the things that makes me feel better as a musician is that there's more to music than just the chords you choose.”

Microsoft has not yet decided to commercialize MySong, but the team hopes to improve its core modeling algorithms, as well as provide more user control over which libraries the program relies on. Basu imagines users being able to select chords based on libraries of specific musicians. A slider, for instance, that could blend chord-progression styles between the jazz singer Ella Fitzgerald and the metal band Slayer.

Listen to audio samples created by MySong users and judge the chords for yourself at http://research.microsoft.com/~dan/mysong/

Credits.

Microsoft Engineers Invent Energy-Efficient LCD Competitor

Telescopic pixel display lets more light out than an LCD

PHOTO: Anna Pyayt

21 July 2008—Researchers from Microsoft say they've built a prototype of a display screen using a technology that essentially mimics the optics in a telescope but at the scale of individual display pixels. The result is a display that is faster and more energy efficient than a liquid crystal display, or LCD, according to research reported yesterday in Nature Photonics. 


Anna Pyayt led the research as part of her Ph.D. thesis at the University of Washington in collaboration with two Microsoft engineers. Microsoft funded the work and has also applied for a patent on the technology.

The most common display technology, the LCD, is inefficient. The display is lit from the back, and less than 10 percent of the light reaches the surface of the screen. Pixels in a display technology work as on-off shutters, but the light has to travel through several layers before reaching the screen. In an LCD, one of those layers is a polarizing filter, which absorbs about 50 percent of the light as it passes through.

By contrast, the telescopic pixel design uses reflective optics. Each pixel functions as a miniature telescope. There are two mirrors: a primary mirror facing the backlight (away from the screen) with a hole in the middle, and a smaller secondary mirror 175 micrometers behind the primary mirror it faces. The secondary mirror is the same size and shape as the hole. Without an electric field, the mirrors stay flat, and light coming from behind the pixel is reflected back, away from the screen. But applying voltage bends the primary mirror into the shape of a parabola. The bending focuses light onto the secondary mirror, which reflects it out through the hole in the primary mirror and onto the screen.

The design greatly increases the amount of backlight that reaches the screen. The researchers were able to get about 36 percent of the backlight out of a pixel, more than three times as much light as an LCD can deliver. But Microsoft senior research engineer Michael Sinclair says that through design improvements, he expects that number to go up—theoretically, as high as 75 percent.

The telescopic display can also switch its pixels on and off faster than an LCD can, going from dark to light and back again in just 1.5 milliseconds, about six times as fast as a typical LCD pixel.

Researchers not associated with the study also see promise in the technology, particularly because it does not compromise picture quality for power efficiency. “This novel approach for transmissive displays is highly attractive because it can provide high-efficiency analog gray scale,” says Jason Heikenfeld, assistant professor of electrical engineering at the University of Cincinnati and director of the Novel Devices Laboratory. Most microelectromechanical systems display technologies—such as Texas Instruments' digital micromirror devices—are digital; they are either on or off. In the telescopic pixel design, the amount of light emitted is a function of voltage. The mirrors act like springs—when you apply more voltage, they bend further, reflecting more light to the screen.

Other reflective displays that have tried to improve efficiency have not been popular with consumers because they are not very bright, says Heikenfeld. So a technology like the telescopic pixel design may serve to satisfy demands for power efficiency and image quality, he adds. However, the telescopic pixels require high voltages to operate—up to 120 volts—and Heikenfeld believes that Microsoft will have to reduce that voltage for a commercial product.

One potential concern about the technology may be its durability, because of the constant bending and movement of the mirrors. A durability test has not yet been done, says Microsoft's Sinclair. However, he adds that the group did produce an array of pixels that performed without any glitches, a sign that the technology can be manufactured. “It shows definite signs of a future,” he says.

Pyayt agrees. “It's not a final, perfectly working system, but it's in progress, and I believe it's possible to optimize it to be fully functional,” she says.

The technology is still in its nascent stages, and the project is unusual for Microsoft, which is not in the display business. Sinclair says there is a possibility that Microsoft will collaborate with a display manufacturer, but commercial production is at least five years away.

Credits.

Direct video manipulation interface

Direct manipulation of video is one of the more uncanny HCI concepts I've ever seen. Instead of manipulating time with a traditional scrubber bar, the user can drag objects in the video across their path of movement. Nothing in the video actually changes, but the perception is that you can directly manipulate the objects in the video stream by pulling them around through time.

There's a Windows application called DimP which implements this interface. When you hover over a movable object in the video, a light path appears that emphasizes the object's motion curve, which you can then move the object across. From the DimP website:

So what's being manipulated, exactly? Both the video content (e.g., the things you see moving in the video) and the "tape head". When using DimP, the user directly manipulates the video content and indirectly manipulates the tape head. When using the seeker bar, the user directly manipulates the tape head and indirectly manipulates the video content.

The video above describes how DimP works in a bit more detail, showing a few different video scenarios where direct manipulation really shines. It's intuitive and bizarre at the same time. If the universe is completely deterministic, I can't help but think this is what time travel must look like.

DimP - A Direct Manipulation Video Player
DRAGON - Direct Manipulation Interface Demo for OS X

Reference.

Image Fulgurator - subverting other people's photos

http://www.youtube.com/watch?v=EAX_3Bgel7M

Berlin hacker Julius von Bismarck invented and patented the Image Fulgurator, a device so awesome that it can remotely insert images into other people's photos.

You aim the device at the same subject that another person is photographing, and when they snap a photo the resulting image will be manipulated with a separate, overlayed photo. The person taking the photo will have no idea anything happened until they examine their photo.

The result is pure magic. Here's a clip of the first public "image fulguration".

The device uses a standard 35mm camera body and lens as a projector. Instead of undeveloped film, the camera is loaded with exposed, developed slide film. A flash is built into the back of the camera, sending light backwards through the body, past the the slide and out the telephoto lens. A light sensor is used to trigger the flash when another camera's flash goes off. Thus, when someone else takes a photo, the Fulgurator zaps its slide's image onto the object for a few milliseconds.

In you want to make something like this, you can use some of the techniques that folks typically use to photograph lightning. Below is a link to a simple Arduino project that will give your SLR a light activated shutter release.

While you're at it, take a crack at making your own Fulgurator with a bit more stealth factor. I'm pretty sure I'd get tazed walking around downtown waving this thing around.

It'd almost be worth it.

Image Fulgurator by Julius von Bismarck [via The Future is Awesome]
Lightning Trigger for a Camera

Source

IP traffic to 'double' every two years

Web traffic volumes will almost double every two years from 2007 to 2012, driven by video and web 2.0 applications, according to a report from Cisco Systems..

Increased use of video and social networking has created what Cisco calls 'visual networking', which is raising traffic volumes at a compound annual growth rate of 46 per cent.

Cisco's Visual Networking Index (PDF) predicts that visual networking will account for 90 per cent of the traffic coursing through the world's IP networks by 2012.

The upward trend is not only driven by consumer demand for YouTube clips and IPTV, according to the report, as business use of video conferencing will grow at 35 per cent CAGR over the same period.

Cisco reckons that traffic volumes will be measured in exabytes (one billion gigabytes) by 2012 and will reach 552 exabytes by that time.

Soon after 2012 we will have to adopt zettabytes (one thousand billion gigabytes) to express traffic volumes.

The report is based on Cisco's own predictions and aggregates analysis from several market research firms.

Source.

Smart Card Hacking

Chris Tarnovsky, the owner of Flylogic Engineering spoke to Wired about some of his Smart Card Hacking techniques. It involves lots of dangerous acids to burn off some of the protective layers so it isn’t a DIY project. He is able to probe a data bus on the chip and read or inject information! Below is an image from his blog that shows another chip that has been modified to expose all 8 data bus lines. It shows that no mater what type of security is implemented there are methods of circumventing it.

Via: Hackaday

Source.

(IN)SECURE Magazine #16

(IN)SECURE Magazine #16 has been released. For those unfamiliar, its a PDF with no DRM, and always has excellent infosec content

Microsoft Discloses Government Backdoor on Windows Operating Systems

Microsoft may have inadvertently disclosed a potential Microsoft backdoor for law enforcement earlier this week. To explain this all, here is the layman term of a backdoor from Wikipedia:

A backdoor in a computer system (or cryptosystem or algorithm) is a method of bypassing normal authentication, securing remote access to a computer, obtaining access to plaintext, and so on, while attempting to remain undetected. The backdoor may take the form of an installed program (e.g., Back Orifice), or could be a modification to an existing program or hardware device.

According to an article on PC World: “The software vendor is giving law enforcers access to a special tool that keeps tabs on botnets, using data compiled from the 450 million computer users who have installed the Malicious Software Removal tool that ships with Windows.”

Not a big deal until you keep reading: “Although Microsoft is reluctant to give out details on its botnet buster — the company said that even revealing its name could give cyber criminals a clue on how to thwart it”

Stop the press for second or two and look at this logically: “users who have installed the Malicious Software Removal tool” followed by “ Microsoft is reluctant to give out details on its botnet buster — the company said that even revealing its name could give cyber criminals a clue on how to thwart it”, what? This is perhaps the biggest gaffe I’ve read thus far on potential government collusion with Microsoft.

We then have the following wording: “Microsoft had not previously talked about its botnet tool, but it turns out that it was used by police in Canada to make a high-profile bust earlier this year.” So again, thinking logically at what has been said so far by Microsoft; “We have a tool called Malicious Software Removal tool…”, “we can’t tell you the name of this tool since it would undermine our snooping…”, “it’s been used by law enforcement already to make a high-profile bust earlier this year.”

Remember a “Malicious Software Reporting Tool” is a lot different from a “Malicious Software Removal Tool”. Understanding networking, computing, botnets, let’s put this concept into a working model to explain how this is nothing more than a backdoor. You have an end user, we’ll create a random Windows XP user: Farmer John in North Dakota. Farmer John in North Dakota uses his machine once a week to read news, send family email, nothing more. He installed Microsoft’s Malicious Removal Tool. Farmer John’s machine becomes infected at some point and sends Microsoft information about the compromise: “I’m Farmer John’s machine coming from X_IP_Address”.

A correlation is done with this information and then supposedly used to track where the botnet’s originating IP address is from. From the article: “Analysis by Microsoft’s software allowed investigators to identify which IP address was being used to operate the botnet, Gaudreau said. And that cracked the case.” This is not difficult, detect a DST (destination) for malware sent from Farmer John’s machine. Simple, good guys win, everyone is happy.

The concept of Microsoft’s Malicious Software Removal tool not being a backdoor is flawed. For starters, no information is ever disclosed to someone installing the Windows Malicious Software removal tool: “Windows will now install a program which will report suspicious activity to Microsoft”. As far as I can recall on any Windows update, there has never been any mention of it.

“But this is a wonderful tool, why are you being such a troll and knocking Microsoft for doing the right thing!”. The question slash qualm I have about this tool is I’d like to know what, why, when and how things are being done on my machine. It’s not a matter of condemning Microsoft, but what happens if at some point in time Microsoft along with government get an insane idea to branch away from obtaining other data for whatever intents and purposes?

We’ve seen how the NSA is allowed to gather any kind of information they’d like (http://www.eff.org/issues/nsa-spying), we now have to contend with Microsoft attempting to do the same. Any way you’d like to market this, it reeks of a backdoor: (again pointing to the definition) A backdoor in a computer system … is a method of bypassing normal authentication, … obtaining access to … , and so on, while attempting to remain undetected. There’s no beating around the bush here on what this tool is and does.

This is reminiscent of the 90’s with the NSA’s ECHELON program. In 1994, the NSA intercepted the faxes and telephone calls of Airbus. What resulted was the information was then forwarded to Boeing and McDonnell-Douglas in which they snagged the contract from under Airbus’ feet. In 1996, the CIA hacked into the computers of the Japanese Trade Ministry seeking “negotiations on import quotas for US cars on the Japanese market”. Resulting with the information being passed off to “US negotiator Mickey Kantor” who accepted a lower offer.

As an American you might say “so what, more power to us” but to think that any government wouldn’t do it to its own citizens for whatever reason would be absurd. There are a lot of horrible routes this could take.

What happens if slash when for some reason or another the government decides that you should not read a news site, will Microsoft willingly oblige and rewrite the news in accordance to what the government deems readable?

How about the potential to give Microsoft a warrantless order to discover who doesn’t like a President’s “health care plan”, or who is irrate and whatever policy; Will Microsoft sift through a machine to retrieve relevant data to disclose to authorities?

That doesn’t include the potential for say technological espionage and gouging of sorts. What’s to stop Microsoft from say, mapping a network and reporting all “non-Microsoft” based products back to Microsoft. The information could then be used to say raise support costs, allow Microsoft to offer juicier incentives to rid the network of non MS based products, the scenarios are endless.

Sadly, most people will shrug and pass it off as nothing. Most security buffs, experts, etc., haven’t mentioned a word of it outside of “the wonderful method to remove, detect, botnets!” and I don’t necessarily disagree it’s a unique way to detect what is happening, but this could have been done at the ISP and NSP level without installing a backdoor. Why didn’t law enforcement approach botnets from that avenue? Perhaps they have, this I’m actually certain of which leads me to believe this is a prelude of something more secretive that has yet to be disclosed or discovered.

http://www.pcworld.com/businesscenter/article/145257/microsoft_botnethunting_tool_helps_bust_hackers.html
http://cryptome.org/echelon-ep-fin.htm (ECHELON MISHAPS)
MORE ON MICROSOFT’S POTENTIAL GOVERNMENT BACKDOOR

Researchers at HP have solved the 37-year mystery of the memory resistor, the missing 4th circuit element.

PHOTO: R. Stanley Williams

1 May 2008—Anyone familiar with electronics knows the trinity of fundamental components: the resistor, the capacitor, and the inductor. In 1971, a University of California, Berkeley, engineer predicted that there should be a fourth element: a memory resistor, or memristor. But no one knew how to build one. Now, 37 years later, electronics have finally gotten small enough to reveal the secrets of that fourth element. The memristor, Hewlett-Packard researchers revealed today in the journal Nature, had been hiding in plain sight all along—within the electrical characteristics of certain nanoscale devices. They think the new element could pave the way for applications both near- and far-term, from nonvolatile RAM to realistic neural networks.

The memristor's story starts nearly four decades ago with a flash of insight by IEEE Fellow and nonlinear-circuit-theory pioneer Leon Chua. Examining the relationships between charge and flux in resistors, capacitors, and inductors in a 1971 paper, Chua postulated the existence of a fourth element called the memory resistor. Such a device, he figured, would provide a similar relationship between magnetic flux and charge that a resistor gives between voltage and current. In practice, that would mean it acted like a resistor whose value could vary according to the current passing through it and which would remember that value even after the current disappeared.

But the hypothetical device was mostly written off as a mathematical dalliance. Thirty years later, HP senior fellow Stanley Williams and his group were working on molecular electronics when they started to notice strange behavior in their devices. “They were doing really funky things, and we couldn't figure out what [was going on],” Williams says. Then his HP collaborator Greg Snider rediscovered Chua's work from 1971. “He said, ‘Hey guys, I don't know what we've got, but this is what we want,' ” Williams remembers. Williams spent several years reading and rereading Chua's papers. “It was several years of scratching my head and thinking about it.” Then Williams realized their molecular devices were really memristors. “It just hit me between the eyes.”

The reason that the memristor is radically different from the other fundamental circuit elements is that, unlike them, it carries a memory of its past. When you turn off the voltage to the circuit, the memristor still remembers how much was applied before and for how long. That's an effect that can't be duplicated by any circuit combination of resistors, capacitors, and inductors, which is why the memristor qualifies as a fundamental circuit element.

The classic analogy for a resistor is a pipe through which water (electricity) runs. The width of the pipe is analogous to the resistance of the flow of current—the narrower the pipe, the greater the resistance. Normal resistors have an unchanging pipe size. A memristor, on the other hand, changes with the amount of water that gets pushed through. If you push water through the pipe in one direction, the pipe gets larger (less resistive). If you push the water in the other direction, the pipe gets smaller (more resistive). And the memristor remembers. When the water flow is turned off, the pipe size does not change.

Such a mechanism could technically be replicated using transistors and capacitors, but, Williams says, “it takes a lot of transistors and capacitors to do the job of a single memristor.”

The memristor's memory has consequences: the reason computers have to be rebooted every time they are turned on is that their logic circuits are incapable of holding their bits after the power is shut off. But because a memristor can remember voltages, a memristor-driven computer would arguably never need a reboot. “You could leave all your Word files and spreadsheets open, turn off your computer, and go get a cup of coffee or go on vacation for two weeks,” says Williams. “When you come back, you turn on your computer and everything is instantly on the screen exactly the way you left it.”

Chua deduced the existence of memristors from the mathematical relationships between the circuit elements. The four circuit quantities (charge, current, voltage, and magnetic flux) can be related to each other in six ways. Two quantities are covered by basic physical laws, and three are covered by known circuit elements (resistor, capacitor, and inductor), says Columbia University electrical engineering professor David Vallancourt. That leaves one possible relation unaccounted for. Based on this realization, Chua proposed the memristor purely for the mathematical aesthetics of it, as a class of circuit element based on a relationship between charge and flux.

Image: J. J. Yang/HP Labs

Chua calls the HP work a paradigm shift; he likens the addition of the memristor to the circuit design arsenal to adding a new element to the periodic table: for one thing, “now all the EE textbooks need to be changed,” he says.

So why hadn't anyone seen memristance? Chua actually produced a memristor in the 1970s with an impractical combination of resistors, capacitors, inductors, and amplifiers as a proof of concept. But memristance as a property of a material was, until recently, too subtle to make use of. It is swamped by other effects, until you look at materials and devices that are mere nanometers in size.

No one was looking particularly hard for memristance, either. In the absence of an application, there was no need. No engineers were saying, “If we only had a memristor, we could do X,” says Vallancourt. In fact, Vallancourt, who has been teaching circuit design for years, had never heard of memristance before this week.

"now all the EE textbooks need to be changed" -IEEE Kirchoff Award winner Leon Chua on the discovery of the memresistor.

But the smaller the scales of the devices scientists and engineers were working with got, the more the devices started behaving with the postulated “memristor” effect, says Chua, who is now a senior professor at Berkeley.

There had been clues to the memristor's existence all along. “People have been reporting funny current voltage characteristics in the literature for 50 years,” Williams says. “I went to these old papers and looked at the figures and said, ‘Yup, they've got memristance, and they didn't know how to interpret it.' ”

“Without Chua's circuit equations, you can't make use of this device,” says Williams. “It's such a funky thing. People were using all the wrong circuit equations. It's like taking a washing machine motor and putting it into a gasoline-powered car and wondering why it won't run.”

Williams found an ideal memristor in titanium dioxide—the stuff of white paint and sunscreen. Like silicon, titanium dioxide (TiO₂) is a semiconductor, and in its pure state it is highly resistive. However, it can be doped with other elements to make it very conductive. In TiO₂, the dopants don't stay stationary in a high electric field; they tend to drift in the direction of the current. Such mobility is poison to a transistor, but it turns out that's exactly what makes a memristor work. Putting a bias voltage across a thin film of TiO₂ semiconductor that has dopants only on one side causes them to move into the pure TiO₂ on the other side and thus lowers the resistance. Running current in the other direction will then push the dopants back into place, increasing the TiO₂'s resistance.

HP Labs is now working out how to manufacture memristors from TiO₂ and other materials and figuring out the physics behind them. They also have a circuit group working out how to integrate memristors and silicon circuits on the same chip. The HP group has a hybrid silicon CMOS memristor chip “sitting on a chip tester in our lab right now,” says Williams.

The implications for circuit design may be niche at the moment. “This will require a fair amount of work to exploit,” says Columbia's Vallancourt. Applications will have to be identified in which the memristor's unique characteristics offer possibilities not covered by today's components.

Williams is in talks with several neuroscience/engineering labs that are pursuing the goal of building devices that emulate neural systems. Chua says that synapses, the connections between neurons, have some memristive behavior. Therefore, a memristor would be the ideal electronic device to emulate a synapse.

By redesigning certain types of circuits to include memristors, Williams expects to obtain the same function with fewer components, making the circuit itself less expensive and significantly decreasing its power consumption. In fact, he hopes to combine memristors with traditional circuit-design elements to produce a device that does computation in a non-Boolean fashion. “We won't claim that we're going to build a brain, but we want something that will compute like a brain,” Williams says. They think they can abstract “the whole synapse idea” to do essentially analog computation in an efficient manner. “Some things that would take a digital computer forever to do, an analog computer would just breeze through,” he says.

The HP group is also looking at developing a memristor-based nonvolatile memory. “A memory based on memristors could be 1000 times faster than magnetic disks and use much less power,” Williams says, sounding like a kid in a candy store.

Chua agrees that nonvolatile memory is the most near-term application. “I'm very happy that this is a breakthrough,” he says. “The reality is that at the nanoscale, this effect becomes dominant, and you'll find it whether you like it or not. I'm glad I can point people in the right direction.”

Source.

Storing data in three dimensions with racetrack memory

Work from researchers at IBMs Almaden Research Laboratory suggests that a new type of computer memory storage may be on the horizon. Currently, computer memory comes in one of two flavors: solid state RAM or magnetic hard disk drives, both of which rely on what's effectively two-dimensional storage. The new method adds some useful features to memory storage by extending the physical storage into the third dimension.

Over the past few years, an IBM research team, led by Stuart S. P. Parkin, has been developing a new method for storing information. Called racetrack memory (RM), it relies on U-shaped nanowires that are arranged perpendicular to the surface of a chip and act as a shift register. Bits can be read or written at the base of the wire. Once on the wire, bits can then be moved around as if they're on a memory stack thanks to nanosecond pulses of current applied to the ends of the U that shift all the bits to new locations on the wire.

A pair of articles from the Almaden group that describe RM appear in this week's edition of Science, the first describing the technology in depth, and the second reporting the construction of a simplified working device. The review article¹ lays out the basics of racetrack memory. The smallest unit of RM is a U-shaped nanowire, with data stored in magnetic domain walls (DWs) arrayed along its length. A collection of these nanowires can be built onto a single chip, producing a memory density greater than anything solid state memory can currently handle. According to the researchers, even a two-dimensional RM setup would have a memory density higher than nearly all current solid state offerings.

Cartoon schematic of a single racetrack wire
Image credit: IBM Almaden Research Labs

DW-based bits are accessed using current pulses that exploit the phenomenon of spin-momentum transfer. The current shifts the entire set of bits along the wire, exposing a different DW to the reader and/or writer at the base. The system has some very appealing properties. The cost of storing a single bit is actually reduced as the number of DWs per racetrack increases. The average time needed to read a given bit is also independent of the number of DWs per racetrack—essentially, there's a "the more the merrier" situation when it comes to data density.Thanks to the fact that there are no moving parts, there is also no obvious fatigue or wearout mechanism for RM.

If RM devices pan out, they could potentially offer the low cost of HDD technology with the performance and reliability of solid-state devices. Because of these properties, interest in DW devices has fluctuated over the years. They were first proposed in the 1970s, and there was a flurry of research in the late seventies and early eighties on "magnetic bubble materials." That work never panned out due to technological hurdles that could not be overcome at the time. The accompanying research paper² suggest those hurdles might be a thing of the past, as it describes the successful creation of a two-dimensional racetrack memory nanowire device.

The device is a single nanowire laid flat on a substrate, with read/write heads in the center of the wire and the current pulse generators that move the bits around on the ends of the wire. The wire is made of permalloy (Ni₈₁Fe₁₉), measured 200 nm in diameter, and extended six microns between the electrical contacts at each end. Sending 1.6V pulses across the wire produced a current density of nearly 2x10⁸ A/cm².

The setup functioned as a DW shift register memory device, the equivalent of a three-bit unidirectional serial-in, serial-out memory setup. The researchers were able to encode a series of information one bit at a time, shifting the memory down and then reading the data back out. The time needed to encode and shift one bit to was approximately 30ns and the authors suggest that the average access time for RM will be between 10 and 50ns. This compares reasonably well to the 5ms typical of HDD-based technology, and around 10ns for advanced solid state devices.

The researchers conclude their article by stating, "the motion of a series of DWs at high speed using nanosecond current pulses not only proves the viability of a shift-register memory but also presages the possibility of current-controlled DW–based logic devices." There is still work to do before an entire three-dimensional memory chip will replace your current memory solutions. The biggest problem may be heat; moving DWs requires a high current, which may destroy the wire or mangle the data it contains. Still, there are some ideas on how to deal with the heat, and this work represents a big step in the direction of a new dimension in memory storage.

[1] Science, 2008. DOI: 10.1126/science.1145799
[2] Science, 2008. DOI: 10.1126/science.1154587

IBM smacks rivals with 5.0GHz Power6 beast

The rest of the server world can play with their piddling 2-3GHz chips. IBM, meanwhile, is prepared to deal in the 5GHz realm.

The hardware maker has unveiled a Power6-based version of its highest-end Unix server - the Power 595. The box runs on 32 dual-core 5GHz Power6 processors, making it a true performance beast. This big box completes a protracted roll out of the Power6 chip across IBM's Unix server line.

Along with the big daddy, IBM revealed a new water-cooled version of the Power 575 server dubbed the Hydro-Cluster. In addition, it refreshed the existing midrange Power 570 server.

IBM's top Power executives showed off the fresh gear during a customer and press event here in San Francisco. They wheeled out three Power customers who were thrilled to be part of IBM's Unix experience. We guess that a disgruntled Power user or two could not be located on short notice to provide balance.

The Power 595 ships in a massive cabinet that looks just like that of its predecessors, except IBM has added a few green touches to the case. This green reflects the environmentally friendly nature of IBM's hulking metal tower, we're told.

The Power 595, available on May 6, relies on a series of four-socket "books" or boards. You can fill a system with between one and eight boards, using both 4.2GHz and 5.0GHz chips. This monster can hold up to 4TB of DDR2 memory. You'll find the rest of the specifications here where IBM details the various options with its I/O drawers.

Usually, IBM will hit customers with a massive TPC benchmark score when it rolls out a new 595-class system - just to let HP know how much it cares. Apparently, the company is saving that gem for a later date, opting instead just to show how the Power 595 wallops HP's Itanium gear and Sun's SPARC systems on SAP and SPEC benchmarks. We're told that IBM's new system beats out the rivals by 2x to 3x. We thought it rather sporting of IBM to include Sun's gear in the benchmarks.

The Power 575 is a different type of high-end creature with IBM characterizing the system as a supercomputing machine. As mentioned, IBM has layered water-filled coils over each of the boards in the 575, allowing it to create a more dense design.

Customers can fit up to 14 2U boards in the huge 575 case with 16 4.7GHz dual-core chips per board. You'll also manage to outfit each board with up to 256GB of memory. The rest of the rather complex specifications are here.

According to IBM, the water-cooling can reduce typical data center energy consumption by 40 per cent when compared to air cooled 575s. In addition, the refreshed box offers up 5x the performance of older 575 systems. IBM has benchmarked a single 575 board at 600 GFlops.

The system will ship in May, running AIX or Linux.

The refreshed 570 still runs on 3.5-4.7GHz versions of Power6, just as it has done since last year. Now, however, customers can tap a "hot node" feature that lets them add additional systems to an already running box for extra horsepower and storage. IBM has shipped 8,000 of the systems to date.

Source

DARPA project reads the brain waves of image analysts to speed up intelligence triage

PHOTO: Jonathan Nourok/Getty Images

3 April 2008—We may need computers to tell us the square root of 529 679, but for now, at least, they still need us to recognize a kitten napping in a box of yarn. The point goes to the humans for our keen sense of the relationship between objects, our eye for texture, and our understanding of emotional relevance, but we don't wield these abilities with great speed. This slowness, unfortunately, has caused intelligence agencies a good deal of distress. They collect surveillance images from satellites, infrared sensors, and aerial-mounted cameras so quickly that analysts must struggle to keep up.

But what if we could combine the speed of a computer with the sensitivity of the human brain? Teams of researchers at Honeywell, Teledyne Scientific and Imaging, and Columbia University are busy hooking image analysts up to EEG machines, reading their brain activity, and speeding up data sorting sixfold. Their research is for a Defense Advanced Research Projects Agency (DARPA) program called Neurotechnology for Intelligence Analysts, which began its second of three phases this year. Each phase whittles down the number of participating research teams, and by the end, DARPA expects to have one team with a superior system.

“This [system] could be used for searching for desired images in a large database of images. It would be faster than a manual search,” says Deniz Erdogmus, a computer science professor at Oregon Health & Science University, in Portland, who collaborates with the group at Honeywell. Erdogmus presented an EEG approach to image triage on 2 April at the IEEE International Conference on Acoustics, Speech, and Signal Processing, in Las Vegas.

Erdogmus explains that it takes humans about 300 milliseconds to consciously recognize specific information in a picture—an adult face among children, for example. It takes another 200 ms for the person to react physically, say, by pushing a button as an analyst would do. But even before a person is conscious of what he or she is seeing—about 150 ms after being shown an image—the electrical activity in the brain's visual cortex has already spiked. The activity is called an event related potential, or ERP.

In Erdogmus's experiments, which DARPA funded, six professional image analysts watched as aerial photographs flashed on a computer screen, more than five of them per second. The analysts were told to search the terrain for large targets, such as golf courses. Meanwhile, a 32-electrode EEG cap, plastered to the analysts' heads, detected brain activity that was then recorded in a separate computer. After the experiment, Erdogmus ran the recordings through a program that flagged any pictures whose appearance coincided with an ERP. While his analysis pulled out many false targets, it rarely missed a real one. Even if it were used to isolate candidate targets for another analyst to scrutinize more closely, the technique could save a lot of time, says Erdogmus. For the system to meet DARPA standards, the analysis will have to happen concurrently with the recordings. The research team at Columbia University, in New York City, has already shown that it can analyze its data in real time, says Paul Sajda, an associate professor of biomedical engineering and the project leader at Columbia.

One main challenge in using the technique has been clearly detecting a signal against the background of normal brain activity. The Oregon lab uses a commercial EEG electrode cap that detects and evenly weighs signals from all parts of the brain. The baseline hum of activity in the human brain produces a voltage signal of 10 to 100 microvolts, while the ERP signal has an amplitude of only 1 to 10 microvolts.

Another problem is that the brain continues to respond electrically even after the image disappears, which makes it difficult to match signals with the pictures that evoked them. In an effort to get around that problem, Erdogmus has been refining a strategy to calibrate the system for each new user. During a training period, images are presented in controlled sequence so that the responding brain signals won't overlap. In these trials, the analyst must push a button in response to target pictures. This gives the computer a clear indication of what each person's ERP looks like so that it can better sort out overlapping ones.

The question remains whether watching images in rapid sequence will tire analysts out faster and ultimately make them less efficient. Catherine Huang, a graduate student in the Erdogmus lab who has tried the procedure, says it's essential to take small breaks between chunks of images but that even after an hour of watching satellite images flash past, she didn't feel tired. “Each block is only 5 seconds, and you can take a break for as long as you want,” she says. Honeywell has reported the same feedback from the subjects in its in-house experiments. Teledyne could not be reached for comment.

The real difficulty could be in making the system user-friendly. “Even though our system is faster, we still need to hook up the electrode to the head. So we are not sure if the user will accept this,” says Huang. Securing an electrical connection between the ERP cap and the analyst's head usually requires dousing the scalp in a conductive gel, and with all the necessary wires, the user must sit there looking like a futuristic Medusa.

MapReduce: A major step backwards

On January 8, a Database Column reader asked for our views on new distributed database research efforts, and we'll begin here with our views on MapReduce. This is a good time to discuss it, since the recent trade press has been filled with news of the revolution of so-called "cloud computing." This paradigm entails harnessing large numbers of (low-end) processors working in parallel to solve a computing problem. In effect, this suggests constructing a data center by lining up a large number of "jelly beans" rather than utilizing a much smaller number of high-end servers.

For example, IBM and Google have announced plans to make a 1,000 processor cluster available to a few select universities to teach students how to program such clusters using a software tool called MapReduce [1]. Berkeley has gone so far as to plan on teaching their freshman how to program using the MapReduce framework.

As both educators and researchers, we are amazed at the hype that the MapReduce proponents have spread about how it represents a paradigm shift in the development of scalable, data-intensive applications. MapReduce may be a good idea for writing certain types of general-purpose computations, but to the database community, it is:

1. A giant step backward in the programming paradigm for large-scale data intensive applications
   
   
2. A sub-optimal implementation, in that it uses brute force instead of indexing
   
   
3. Not novel at all -- it represents a specific implementation of well known techniques developed nearly 25 years ago
   
   
4. Missing most of the features that are routinely included in current DBMS
   
   
5. Incompatible with all of the tools DBMS users have come to depend on
   

First, we will briefly discuss what MapReduce is; then we will go into more detail about our five reactions listed above.


What is MapReduce?

The basic idea of MapReduce is straightforward. It consists of two programs that the user writes called map and reduce plus a framework for executing a possibly large number of instances of each program on a compute cluster.

The map program reads a set of "records" from an input file, does any desired filtering and/or transformations, and then outputs a set of records of the form (key, data). As the map program produces output records, a "split" function partitions the records into M disjoint buckets by applying a function to the key of each output record. This split function is typically a hash function, though any deterministic function will suffice. When a bucket fills, it is written to disk. The map program terminates with M output files, one for each bucket.

In general, there are multiple instances of the map program running on different nodes of a compute cluster. Each map instance is given a distinct portion of the input file by the MapReduce scheduler to process. If N nodes participate in the map phase, then there are M files on disk storage at each of N nodes, for a total of N * M files; F_i,j, 1 ≤ i ≤ N, 1 ≤ j ≤ M.

The key thing to observe is that all map instances use the same hash function. Hence, all output records with the same hash value will be in corresponding output files.

The second phase of a MapReduce job executes M instances of the reduce program, R_j, 1 ≤ j ≤ M. The input for each reduce instance R_j consists of the files F_i,j, 1 ≤ i ≤ N. Again notice that all output records from the map phase with the same hash value will be consumed by the same reduce instance -- no matter which map instance produced them. After being collected by the map-reduce framework, the input records to a reduce instance are grouped on their keys (by sorting or hashing) and feed to the reduce program. Like the map program, the reduce program is an arbitrary computation in a general-purpose language. Hence, it can do anything it wants with its records. For example, it might compute some additional function over other data fields in the record. Each reduce instance can write records to an output file, which forms part of the "answer" to a MapReduce computation.

To draw an analogy to SQL, map is like the group-by clause of an aggregate query. Reduce is analogous to the aggregate function (e.g., average) that is computed over all the rows with the same group-by attribute.

We now turn to the five concerns we have with this computing paradigm.


1. MapReduce is a step backwards in database access

As a data processing paradigm, MapReduce represents a giant step backwards. The database community has learned the following three lessons from the 40 years that have unfolded since IBM first released IMS in 1968.

• Schemas are good.
  
  
• Separation of the schema from the application is good.
  
  
• High-level access languages are good.
  

MapReduce has learned none of these lessons and represents a throw back to the 1960s, before modern DBMSs were invented.

The DBMS community learned the importance of schemas, whereby the fields and their data types are recorded in storage. More importantly, the run-time system of the DBMS can ensure that input records obey this schema. This is the best way to keep an application from adding "garbage" to a data set. MapReduce has no such functionality, and there are no controls to keep garbage out of its data sets. A corrupted MapReduce dataset can actually silently break all the MapReduce applications that use that dataset.

It is also crucial to separate the schema from the application program. If a programmer wants to write a new application against a data set, he or she must discover the record structure. In modern DBMSs, the schema is stored in a collection of system catalogs and can be queried (in SQL) by any user to uncover such structure. In contrast, when the schema does not exist or is buried in an application program, the programmer must discover the structure by an examination of the code. Not only is this a very tedious exercise, but also the programmer must find the source code for the application. This latter tedium is forced onto every MapReduce programmer, since there are no system catalogs recording the structure of records -- if any such structure exists.

During the 1970s the DBMS community engaged in a "great debate" between the relational advocates and the Codasyl advocates. One of the key issues was whether a DBMS access program should be written:

• By stating what you want - rather than presenting an algorithm for how to get it (relational view)
  
  
• By presenting an algorithm for data access (Codasyl view)
  

The result is now ancient history, but the entire world saw the value of high-level languages and relational systems prevailed. Programs in high-level languages are easier to write, easier to modify, and easier for a new person to understand. Codasyl was rightly criticized for being "the assembly language of DBMS access." A MapReduce programmer is analogous to a Codasyl programmer -- he or she is writing in a low-level language performing low-level record manipulation. Nobody advocates returning to assembly language; similarly nobody should be forced to program in MapReduce.

MapReduce advocates might counter this argument by claiming that the datasets they are targeting have no schema. We dismiss this assertion. In extracting a key from the input data set, the map function is relying on the existence of at least one data field in each input record. The same holds for a reduce function that computes some value from the records it receives to process.

Writing MapReduce applications on top of Google's BigTable (or Hadoop's HBase) does not really change the situation significantly. By using a self-describing tuple format (row key, column name, {values}) different tuples within the same table can actually have different schemas. In addition, BigTable and HBase do not provide logical independence, for example with a view mechanism. Views significantly simplify keeping applications running when the logical schema changes.


2. MapReduce is a poor implementation

All modern DBMSs use hash or B-tree indexes to accelerate access to data. If one is looking for a subset of the records (e.g., those employees with a salary of 10,000 or those in the shoe department), then one can often use an index to advantage to cut down the scope of the search by one to two orders of magnitude. In addition, there is a query optimizer to decide whether to use an index or perform a brute-force sequential search.

MapReduce has no indexes and therefore has only brute force as a processing option. It will be creamed whenever an index is the better access mechanism.

One could argue that value of MapReduce is automatically providing parallel execution on a grid of computers. This feature was explored by the DBMS research community in the 1980s, and multiple prototypes were built including Gamma [2,3], Bubba [4], and Grace [5]. Commercialization of these ideas occurred in the late 1980s with systems such as Teradata.

In summary to this first point, there have been high-performance, commercial, grid-oriented SQL engines (with schemas and indexing) for the past 20 years. MapReduce does not fare well when compared with such systems.

There are also some lower-level implementation issues with MapReduce, specifically skew and data interchange.

One factor that MapReduce advocates seem to have overlooked is the issue of skew. As described in "Parallel Database System: The Future of High Performance Database Systems," [6] skew is a huge impediment to achieving successful scale-up in parallel query systems. The problem occurs in the map phase when there is wide variance in the distribution of records with the same key. This variance, in turn, causes some reduce instances to take much longer to run than others, resulting in the execution time for the computation being the running time of the slowest reduce instance. The parallel database community has studied this problem extensively and has developed solutions that the MapReduce community might want to adopt.

There is a second serious performance problem that gets glossed over by the MapReduce proponents. Recall that each of the N map instances produces M output files -- each destined for a different reduce instance. These files are written to a disk local to the computer used to run the map instance. If N is 1,000 and M is 500, the map phase produces 500,000 local files. When the reduce phase starts, each of the 500 reduce instances needs to read its 1,000 input files and must use a protocol like FTP to "pull" each of its input files from the nodes on which the map instances were run. With 100s of reduce instances running simultaneously, it is inevitable that two or more reduce instances will attempt to read their input files from the same map node simultaneously -- inducing large numbers of disk seeks and slowing the effective disk transfer rate by more than a factor of 20. This is why parallel database systems do not materialize their split files and use push (to sockets) instead of pull. Since much of the excellent fault-tolerance that MapReduce obtains depends on materializing its split files, it is not clear whether the MapReduce framework could be successfully modified to use the push paradigm instead.

Given the experimental evaluations to date, we have serious doubts about how well MapReduce applications can scale. Moreover, the MapReduce implementers would do well to study the last 25 years of parallel DBMS research literature.


3. MapReduce is not novel

The MapReduce community seems to feel that they have discovered an entirely new paradigm for processing large data sets. In actuality, the techniques employed by MapReduce are more than 20 years old. The idea of partitioning a large data set into smaller partitions was first proposed in "Application of Hash to Data Base Machine and Its Architecture" [11] as the basis for a new type of join algorithm. In "Multiprocessor Hash-Based Join Algorithms," [7], Gerber demonstrated how Kitsuregawa's techniques could be extended to execute joins in parallel on a shared-nothing [8] cluster using a combination of partitioned tables, partitioned execution, and hash based splitting. DeWitt [2] showed how these techniques could be adopted to execute aggregates with and without group by clauses in parallel. DeWitt and Gray [6] described parallel database systems and how they process queries. Shatdal and Naughton [9] explored alternative strategies for executing aggregates in parallel.

Teradata has been selling a commercial DBMS utilizing all of these techniques for more than 20 years; exactly the techniques that the MapReduce crowd claims to have invented.

While MapReduce advocates will undoubtedly assert that being able to write MapReduce functions is what differentiates their software from a parallel SQL implementation, we would remind them that POSTGRES supported user-defined functions and user-defined aggregates in the mid 1980s. Essentially, all modern database systems have provided such functionality for quite a while, starting with the Illustra engine around 1995.


4. MapReduce is missing features

All of the following features are routinely provided by modern DBMSs, and all are missing from MapReduce:

• Bulk loader -- to transform input data in files into a desired format and load it into a DBMS
  
  
• Indexing -- as noted above
  
  
• Updates -- to change the data in the data base
  
  
• Transactions -- to support parallel update and recovery from failures during update
  
  
• Integrity constraints -- to help keep garbage out of the data base
  
  
• Referential integrity -- again, to help keep garbage out of the data base
  
  
• Views -- so the schema can change without having to rewrite the application program
  

In summary, MapReduce provides only a sliver of the functionality found in modern DBMSs.


5. MapReduce is incompatible with the DBMS tools

A modern SQL DBMS has available all of the following classes of tools:

• Report writers (e.g., Crystal reports) to prepare reports for human visualization
  
  
• Business intelligence tools (e.g., Business Objects or Cognos) to enable ad-hoc querying of large data warehouses
  
  
• Data mining tools (e.g., Oracle Data Mining or IBM DB2 Intelligent Miner) to allow a user to discover structure in large data sets
  
  
• Replication tools (e.g., Golden Gate) to allow a user to replicate data from on DBMS to another
  
  
• Database design tools (e.g., Embarcadero) to assist the user in constructing a data base.
  

MapReduce cannot use these tools and has none of its own. Until it becomes SQL-compatible or until someone writes all of these tools, MapReduce will remain very difficult to use in an end-to-end task.


In Summary

It is exciting to see a much larger community engaged in the design and implementation of scalable query processing techniques. We, however, assert that they should not overlook the lessons of more than 40 years of database technology -- in particular the many advantages that a data model, physical and logical data independence, and a declarative query language, such as SQL, bring to the design, implementation, and maintenance of application programs. Moreover, computer science communities tend to be insular and do not read the literature of other communities. We would encourage the wider community to examine the parallel DBMS literature of the last 25 years. Last, before MapReduce can measure up to modern DBMSs, there is a large collection of unmet features and required tools that must be added.

We fully understand that database systems are not without their problems. The database community recognizes that database systems are too "hard" to use and is working to solve this problem. The database community can also learn something valuable from the excellent fault-tolerance that MapReduce provides its applications. Finally we note that some database researchers are beginning to explore using the MapReduce framework as the basis for building scalable database systems. The Pig[10] project at Yahoo! Research is one such effort.



References

[1] "MapReduce: Simplified Data Processing on Large Clusters," Jeff Dean and Sanjay Ghemawat, Proceedings of the 2004 OSDI Conference, 2004.

[2] "The Gamma Database Machine Project," DeWitt, et. al., IEEE Transactions on Knowledge and Data Engineering, Vol. 2, No. 1, March 1990.

[4] "Gamma - A High Performance Dataflow Database Machine," DeWitt, D, R. Gerber, G. Graefe, M. Heytens, K. Kumar, and M. Muralikrishna, Proceedings of the 1986 VLDB Conference, 1986.

[5] "Prototyping Bubba, A Highly Parallel Database System," Boral, et. al., IEEE Transactions on Knowledge and Data Engineering,Vol. 2, No. 1, March 1990.

[6] "Parallel Database System: The Future of High Performance Database Systems," David J. DeWitt and Jim Gray, CACM, Vol. 35, No. 6, June 1992.

[7] "Multiprocessor Hash-Based Join Algorithms," David J. DeWitt and Robert H. Gerber, Proceedings of the 1985 VLDB Conference, 1985.

[8] "The Case for Shared-Nothing," Michael Stonebraker, Data Engineering Bulletin, Vol. 9, No. 1, 1986.

[9] "Adaptive Parallel Aggregation Algorithms," Ambuj Shatdal and Jeffrey F. Naughton, Proceedings of the 1995 SIGMOD Conference, 1995.

[10] "Pig", Chris Olston, http://research.yahoo.com/project/90

[11] "Application of Hash to Data Base Machine and Its Architecture," Masaru Kitsuregawa, Hidehiko Tanaka, Tohru Moto-Oka, New Generation Comput. 1(1): 63-74 (1983)

By David DeWitt

[Note: Although the system attributes this post to a single author, it was written by David J. DeWitt and Michael Stonebraker]

Intel hopes to unwire the world with long-range WiFi

Improving the number of people worldwide who have access to the Internet has been a stated goal of nations, international bodies, and NGOs for years, but practical attempts to do so have often faced daunting challenges. Hostile terrain, periodic extremes of temperature and weather, limited/intermittent electrical power, and the ever-present danger of being eaten by lions, bears, or giant fire-breathing iguanas are all issues that must be solved, and that's before the human factors are dealt with. It does no good, after all, to run a copper cable into a town to provide Internet access, only to have someone dig it up next week and sell it for scrap.

Intel's Rural Connectivity Platform (RCP) is designed to push traditional 802.11 wireless connections out to much greater distances than would normally be possible, thereby reducing the amount of cable that must be laid between any two points. Using the 802.11 standard means that spectrum availability is not usually an issue, and Intel's RCP supports frequencies of 900MHz, 2.4GHz, and the 5.2-5.8GHz spectrum.

The idea of focusing and transmitting a wireless signal in order to boost its range is nothing new, but Intel's RCP uses a modified TDMA (time division multiple access) system. A standard wireless system broadcasts a message and waits for a reply. If the reply is not acknowledged within a certain period of time, the station broadcasts again. Intel's RCP TDMA system does away with the acknowledgment phase, and gives each radio a set block of time to send data and a set block of time to receive it. According to Jeff Galinovsky, a senior platform manager at Intel, removing the acknowledgment phase substantially increases the amount of bandwidth that's available at any given point, thus increasing the wireless system's range. Intel's specifications for RCP deployment state that towers may be up to 60 miles (100km) apart. Towers can be deployed in several different configurations, as shown below:

Intel isn't ready for full commercial deployment at present—sales should begin in India later this year—but the company's RCP has a number of potential advantages. At less than $500 per unit and an estimated $1,000 for two nodes and the associated backend infrastructure, the RCP should deliver Internet access at a much lower cost-per-user then more traditional access methods can manage. Battery replacement or adequate power delivery is also a non-issue—Intel's RCP only draws 5-6W at most, which means the unit's needs can be met by solar power.

The RCP's estimated 6.5Mbps of total bandwidth won't exactly turn Asian gold farmers or remote village-dwellers into BitTorrent freaks, but it should provide plenty of speed to allow for basic e-mail and Internet connectivity. Developing nations have reportedly expressed a high degree of interest in the RCP. If the Indian deployment goes well later this year, general availability is likely to follow in short order.

Source and credits.

High Capacity Color Barcode

High Capacity Color Barcode technology, developed within Microsoft Research, advances the state of the art in storing digital information on analog media.

---

Higher Density Storage Capability The High Capacity Color Barcode barcode format takes advantage of advanced computer imaging devices along with processing power to enable higher density storage of data on analog printed media. The format achieves this by using a different barcode symbol shape in combination with multiple colors per symbol. Currently laboratory tests have yielded using eight colors, 2,000 binary bytes, or 3,500 alphabetical characters per square inch in its highest density form using a 600dpi business card scanner. This equates to two pages of a novel. The symbol size can be changed to accommodate the differing fidelities of imaging devices. The barcode can be printed using a regular inkjet or laser jet printer.

Digital Signing Capability The High Capacity Color Barcode barcode has integrated digital signing features using state-of-the-art Elliptic Curve Cryptography, Public Key Infrastructure (PKI) techniques. The purpose of digital signing authenticates the integrity of the data stored in the barcode, ensuring the data is unmodified from the original author. Microsoft's advanced signing techniques employ industry known proven techniques achieving RSA-1024 strength security in only 20 bytes payload overhead. Multiple Payloads - Small File System Typical existing barcode formats have the capability of storing just one item of data or requiring the reader software to have knowledge of the data stored within the barcode. The High Capacity Color Barcode barcode can store multiple individual items of data each being compressed as optimally as possible within the physical code, implementing essentially a small file system. Robust Mobile Device Performance The High Capacity Color Barcode barcode runs on any processor or operating system platform, the lightweight mobile phone implementation can decode barcodes in realtime from a video stream, for example 30ms on a 200Mhz ARM processor. As the format uses half the symbols of its black and white counter parts, decode success rates are higher for the same black and white physical barcode size as the symbols are larger. The smallest capacity barcode can be read on cellphones without modified lenses at a print size of just 3/4" square, outperforming QRCode and Datamatrix formats. Advanced segmentation and color processing techniques ensure good decode rates across a range of image and lighting qualities: From sharp to blurred; From light to dark. Source and credits.

Off-topic: Synesthesia

A documentary about Pat and his synesthesia, a rare neurological condition. Synesthesia essentially means "the joining of the senses". People with this condition often explain sensations in abstracts way such as "hearing colors" or "seeing music".

DataGlyphs: Xerox's technology for embedding data into documents

Basic DataGlyphs are a pattern of forward and backward slashes representing ones and zeroes. This pattern forms an evenly textured field. PARC DataGlyphs® are a robust and unobtrusive method of embedding computer-readable data on paper surfaces. Unlike most barcodes, DataGlyphs are flexible in shape and size. Their structure and robust error correction also make them suitable for curved surfaces and other situations where barcodes fail. PARC invented DataGlyphs in 1993, and has licensed the basic software patents to Microglyph Technology GmbH to form the foundation of their microglyph® code. While PARC developed DataGlyphs for document management systems, Microglyph Technology has developed additional, proprietary code structures and algorithms to enable parts-marking for the manufacturing industry, to enable the embedding of computer-readable data on surfaces such as plastic, glass, or metal.

	Roll mouse over image to zoom in. Original size: 3.3" x 3.3" @ 600dpi. Glyphtones, DataGlyphs of varying weights, emulate the look of a grayscale image.

Features:

• Flexibility -- adjustable size, shape, color
• High data density
• Robustness
• Adjustable error correction
• Compatible with cryptography

At 600dpi, DataGlyphs offer up to 1KB per square inch of data. At this density, the Gettysburg Address fits in a block the size of a small United States postage stamp.

Applications:

• document management
• fraud prevention
• inventory tracking
• ID cards
• parts marking
• product tagging

DataGlyphs have been used in several Xerox products, licensed to a major manufacturer of airplane parts, licensed to Progressive Casualty Insurance for use in turnaround documents, and more. Other markets include financial services, software, government, health care, and pharmaceuticals.

Roll mouse over image to zoom in. Original size: 5.9"x4.8" @600dpi. Color DataGlyphs provide a similar functionality as Glyphtones but extend the applications to color images.	Roll mouse over image to see "invisible" glyphs as seen by the blue channel of a scanner. "Invisible" DataGlyphs are fine yellow glyphs printed on white. This drawing shows them at 200% and 1000% enlargement.
Combining different types of DataGlyphs increases the options for encoding digital information.

Technical Overview of DataGlyphs®

PARC DataGlyphs are a robust and unobtrusive method of embedding computer-readable data on surfaces such as paper, labels, plastic, glass, or metal.

How Data Is Encoded

DataGlyphs encode information - text, data, graphics - in thousands of tiny glyphs. Each glyph consists of a 45-degree diagonal line, as short as one one-hundredth of an inch or less, depending on the resolution of the printing and scanning that's used. Each glyph represents a single binary 0 or 1, depending on whether it slopes to the right or left.

Leaning either forward or back, DataGlyphs represents the ones and zeroes in binary digital data.

The glyphs are laid down in groups on a regular, finely spaced grid forming unobtrusive, evenly textured gray areas. Even when individual glyphs are large enough to be resolved by the human eye, in groups they form a pleasing pattern that is not distracting.

Robustness and Error Correction

In addition to the data, each DataGlyph contains an embedded synchronization lattice or skeleton - a repeating fixed pattern of glyphs that marks the DataGlyph's boundaries and serves as a clocking track to improve the reliability of reading. Groups of glyphs, representing bytes of data, are laid down within this frame.

The data is grouped into blocks of a few dozen bytes each, and error-correction code is added to each block. Individual applications determine the amount of error correction necessary. Of course, higher levels of error correction require larger overall DataGlyphs for a given amount of data, but improve the reliability with which the information can be read back - often a worthwhile trade-off, especially when the DataGlyph will sustain a high level of image noise (for example, during fax transmissions) or when the glyph block will be subjected to rough handling.

For reliability, each DataGlyph contains a measure of error correction appropriate to the application. Glyphs are also randomized to sustain the integrity of the data through damage to the document and laid into a synchronization frame.

As a final step, the bytes of data are randomly dispersed across the entire area of the DataGlyph. Thus, if any part of the DataGlyph is severely damaged, the damage to any individual block of data will be slight, and the error-correcting code will easily be able to recover all the information encoded, despite the damage.

Together, built-in error correction code and data randomization give DataGlyphs a very high level of reliability, even in the face of damage from ink marks, staples, coffee spills, and the other vicissitudes of a paper document's life.

Superior Data Density

The amount of data that can be encoded in a DataGlyph of a given size will vary with the quality of the imprinting and scanning equipment to be used.

DataGlyphs offer a data density nearly twice that of PDF417, one of the most popular forms of 2d barcodes.

For example, with one- and two-dimensional bar codes, the minimum feature size that can be used is 0.0075inch - three dots at 400 dpi. At that density, and with minimal height, Code 39 (the most commonly used general-purpose linear bar code) can only achieve a density of about 25 binary bytes per square inch. Code 128 can achieve about 40 bytes per square inch.

The two-dimensional bar codes, such as PDF417, do much better. achieves a maximum data density of 2,960 bits (or 370 binary bytes) per square inch, with no error correction, at 400 dpi. But with realistic error correction of 27%, the effective data rates for PDF417 are about 270 bytes per square inch.

At the same resolution and level of error correction, DataGlyphs can carry nearly 500 bytes per square inch.

As with other visual encoding schemes, the density of DataGlyph encoding is determined by four factors:

• The resolution at which the encoding is created and scanned. High-resolution devices such as office laser printers and document scanners permit denser marking patterns, and thus denser encoding, than low-resolution devices such as dot-matrix printers and fax machines.

• The amount of error correction used. The process of printing and scanning unavoidably degrades image-encoded data. In high-density encoding, where the print and scan defects are likely to be large compared to the encoding feature size, more of the encoding features will be lost or misread as a result of such degradation. As a countermeasure, some system of redundancy must be used to keep the failure rate within reasonable bounds - that is, for error correction. And redundant coding consumes extra space, reducing the effective data density. Again, how much error correction must be employed will vary from application to application. But there must always be some in any real-world application of any encoding scheme. The data densities that can be achieved using no error correction are theoretical upper bounds, unlikely to be of practical use.

• The data compression used. Data can be compressed as it's encoded, For example, if all the data is numeric, there's no need to use one byte (8 bits) per digit, 3.32 bits will suffice. When text is encoded, it can be compressed by factors of two or more by means of character encoding or other compression techniques. For example the full text of the Gettysburg Address, often used to demonstrate high-density encoding contains 268 words, or about 1,450 characters. But the entire speech can easily be represented in less than 900 bytes.

• The fixed overhead of the synchronization frame and header. For DataGlyphs, the synchronization frame is a fixed proportion of the data area. DataGlyphs also have a very small fixed header.

The size of the DataGlyph required to encode 80 bytes of information depends on the device(s) to be used for printing and/or scanning. DataGlyphs for faxing are often drawn disproportionately large for added reliability in the face of the "noise" that frequently affects fax images.

DataGlyphs is a registered trademark of Palo Alto Research Center Incorporated.

Source and credits.

Online demonstration.

Technology's FAQ