Blog: Novel High-Performance Hybrid System for Semantic Factoring of Graph Databases

Novel High-Performance Hybrid System for Semantic Factoring of Graph Databases
Pacific Northwest National Laboratory (09/21/11) Kathryn Lang; Christine Novak

Researchers at the Pacific Northwest National Laboratory, Sandia National Laboratories, and Cray have developed an application that can analyze gigabyte-sized data sets. The application uses semantic factoring to organize data, revealing hidden connections and threads. The researchers used the application to analyze the massive datasets for the Billion Triple Challenge, an international competition aimed at demonstrating capability and innovation for dealing with very large semantic graph databases. The researchers utilized the Cray XMT architecture, which allowed all 624 gigabytes of input data to be held in RAM. The researchers are now developing a prototype that can be adapted to a variety of application domains and datasets, including working with the bio2rdf.org and future billion-triple-challenge datasets in prototype testing and evaluation.

View Full Article

Blog: Targeted Results; determining a mathemtical graph's maximal independent set

Targeted Results
MIT News (03/31/11) Larry Hardesty

Massachusetts Institute of Technology (MIT) and Tel Aviv University researchers recently met at the Innovations in Computer Science conference at Tsinghua University to present a mathematical framework for finding localized solutions to complex calculations. The researchers say the framework could be used to solve classic computer science problems involving mathematical abstractions known as graphs. Graphs can represent any type of data, but it is often useful to determine the graph's maximal independent set, which occurs when enough vertices have been deleted from the graph so that there are no edges left, meaning that none are connected to any other. Graphs also can have more than one maximal independent set. The researchers developed an algorithm to efficiently determine which vertices are and are not included in at least one of the graph's maximal independent sets. Although the research is theoretical, the problem of calculating independent sets cuts across a variety disciplines, including artificial intelligence, bioinformatics, and scheduling and networking. "There have been lots of related concepts that have been sort of floating around," but the MIT and Tel Aviv researchers "have formalized it in an interesting way and, I think, the correct way," says Sandia National Labs' Seshadhri Comandur.

View Full Article

Blog: Algorithm Pioneer Wins Kyoto Prize

Algorithm Pioneer Wins Kyoto Prize
EE Times (11/12/10) R. Colin Johnson

Eotvos Lorand University professor Laszlo Lovasz, who has solved several information technology (IT) problems using graph theory, has been awarded the Kyoto Prize. "Graph theory represents a different approach to optimization problems that uses geometry to compute results instead of differential equations," says Lovasz. "It turns out that very large networks in many different fields can be described by graphs, from cryptography to physical systems." His work has led to breakthroughs in RSA encryption technology, 4G channel capacity, extending the point-to-point IT of Claude Shannon, and the weak perfect graph conjecture. Lovasz may be best known for the breakthrough principles called the "Lovasz local lemma" and the "LLL-algorithm," which are widely used in cryptography, and for the multiple-input and multiple-output wireless communications scheme. The Kyoto Prize was founded by Kyocera chairman Kazuo Inamori in 1984 and comes with a $550,000 award.

View Full Article