ASES: An Approximate Search Engine for Structure

Project Summary

A structural database is one whose data objects include trees, graphs, or a set of interrelated labeled points in two, three, or higher dimensional space. Examples include databases holding (i) protein secondary and tertiary structure, (ii) phylogenetic trees, (iii) neuroanatomical networks, (iv) parse trees, (v) CAD/CAM parts, and (vi) XML documents. The ASES project aims to produce algorithms, data structures, and tools that allow rapid approximate search across a variety of structural databases. We have developed a suite of algorithms for pattern matching in trees, graphs and high dimensional points as well as indexing techniques. Related software information can be found below.

Software

• for tree matching, searching and mining
  
      Approximate tree comparison for ordered trees (where sibling order matters) [software]
      Data structure setup for searching ordered and unordered trees [software]
      Finding patterns in ordered trees
      Unordered tree comparison based on cousin distance
      Phylogenetic tree comparison based on updown distance

• for graph matching, searching and clustering
  
      Approximate graph comparison
      GraphGrep

• for searching and clustering in metric spaces
  
      MetricMap

Demos

• SIGMOD 2000 demo poster

Support

This material is based upon work partly supported by the United States National Science Foundation under grant IIS-9988636 (2000-2004). Any opinions, findings, and conclusions or recommendations expressed in this material are those of the authors and do not necessarily reflect the views of the National Science Foundation. This support is greatly appreciated.