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 -