Re: Indexed algorithms for approximate structure matching

My favorite technique for approximate search is spreading activation.
You model the data as a brain-like graph. Then activate the query
node(s) and let the energy spread over the graph, until some
satisfaction condition is reach. Then typically the nodes with more
energy constitute the result. See this paper for details and
references:

Minibrain : a generic model of spreading activation in computers, and
example specialisations / Mário Amado Alves ; Alípio Jorge. - 10 p.
- In: ECML/PKDD 2005 workshop "Subsymbolic paradigms for learning in
structured domains"

PDFs available at http://www.liacc.up.pt/~maa/publications.htm

.