Discovering Hidden Patterns

From medical imaging to optimizing oil wells, many industries produce increasingly huge volumes of data from their high-tech applications.

To better organize and analyze the enormous sets of data from such applications, researchers use algorithms that cluster data — break it into smaller, related groups. But data clustering — which plays a central role in data mining techniques and classifying retrieved Web pages — does not always reveal links between seemingly unrelated information.

In his ESTC Award-winning paper, Rafail Ostrovsky, working with Telcordia Technologies, proposes a novel way to cost-effectively group arbitrary data. His paper connects the ideas of data clustering and hidden-pattern searching, as well as locating cluster centers.

At the heart of Ostrovsky's breakthrough is the idea of reducing the amount of dimensions (attributes) in a set of data to reveal hidden clusters of seemingly unconnected data. In addition, his method better identifies database entries that are "approximately related" to a query — when the content of an entry is the closest match among other entries in the database. (Searching for entries that are nearest neighbors of a query is a task performed in applications such as datamining, Web searches, pattern recognition, and machine learning.) According to Ostrovsky, his method — which offers significant improvements in accuracy, processing, and storage resources — "has had a deep impact on the foundational notions of data analysis and datamining, and it offers Telcordia a new tool to improve performance in many large scale data analysis settings."

Ostrovsky's paper offers significant progress in the understanding of clustering of data, discovering hidden patterns in data, and optimization of networks. In fact, a U.S. patent was approved and issued based on the paper's results.

The results of the research from Ostrovsky — a full professor in computer science at UCLA, in addition to his affiliation with Telcordia — and Yuval Rabani (who did part of his work while visiting Telcordia), "Polynomial Time Approximation Schemes for Geometric k-Clustering," was published in the Journal of the Association of Computing Machinery.