Sign In

Communications of the ACM

ACM News

Sizing Samples

View as: Print Mobile App Share:
Pattern recognition

Graphs shaped like stars and chains establish, respectively, worst- and best-case scenarios for computers doing pattern recognition.

Christine Daniloff

Across science and engineering, computers are often enlisted to find patterns in data. The data might be genetic information about a population, and the pattern could be which gene variants predispose people to asthma. Or the data might be frames of video, and the patterns could be objects that move or stand still from frame to frame, which data-compression or image-sharpening algorithms might want to locate.

In most cases, more data means more reliable inference of patterns. But how much data is enough? Vincent Tan, a graduate student in the Department of Electrical Engineering and Computer Science, and his colleagues in Professor Alan Willsky’s Stochastic Systems Group have taken the first steps toward answering that question.

Tan, Willsky and Animashree Anandkumar, a postdoc in Willsky’s group, envision data sets as what mathematicians call graphs. A graph is anything with nodes and edges: Nodes are generally depicted as circles and edges as lines connecting them. A typical diagram of a communications network, where the nodes represent electronic devices and the edges represent communications links, is a graph.

From MIT News Office
View Full Article


No entries found

Sign In for Full Access
» Forgot Password? » Create an ACM Web Account