TY - CHAP

T1 - Relaxation labelling using distributed neural networks

AU - Austin, Jim

PY - 2009

Y1 - 2009

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=78049302127&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-01262-4_5

DO - 10.1007/978-3-642-01262-4_5

M3 - Chapter

SN - 9783642012617

SN - 9783642101779

T3 - Studies in Computational Intelligence

SP - 111

EP - 138

BT - Biologically-Inspired Optimisation Methods

A2 - Lewis, Andrew

A2 - Mostaghim, Sanaz

A2 - Randall, Marcus

PB - Springer

CY - Berlin

ER -