Relaxation labelling using distributed neural networks

Research output: Chapter in Book/Report/Conference proceedingChapter


This chapter presents the Relaxation by Elimination methods (RBE) for searching large collections of graph data that has been implemented on a distributed platform and is in daily use for searching a database of molecules. The core of the approach uses an ‘inverted’ relaxation labelling method that finds a good match of the input data with stored examples. The method is shown to scale linearly with the number of graphs, and to scale linearly under given circumstances to the number of nodes in the graph. Key to the idea is that the system cuts the search time by removing a set of sub-optimal matches leaving those that could match. The system uses arrays of biologically plausible neural networks, Correlation Matrix Memories (CMMs) to store the constraints between the nodes of the graphs being searched. This is coupled to a novel search method. The system is highly parallel. Recently we have developed a parallel Grid enabled computer system (Cortex II) which utilises Digital Signal Processors (DSPs) and Field Programmable Gate Arrays (FPGAs) and have implemented the method on this system. A service for matching small molecules to a molecule database, in which the molecules are represented as attributed graphs, is currently running online. The methods have also been applied to searching trademark databases allowing people to find trademarks that are geometrically similar. The chapter describes the method in detail and its implementation and application. It also brings together work that has appeared separately and presents a new mathematical formulation of the mapping of RBE onto correlation matrix methods.
Original languageEnglish
Title of host publicationBiologically-Inspired Optimisation Methods
Subtitle of host publicationParallel Algorithms, Systems and Applications
EditorsAndrew Lewis, Sanaz Mostaghim, Marcus Randall
Place of PublicationBerlin
Number of pages28
ISBN (Electronic)9783642012624
ISBN (Print)9783642012617, 9783642101779
Publication statusPublished - 2009

Publication series

NameStudies in Computational Intelligence
ISSN (Print)1860-949X

Cite this