Title :
GraphGrep: A fast and universal method for querying graphs
Author :
Giugno, Rosalba ; Shasha, Dennis
Author_Institution :
Dept. of Math. & Comput. Sci., Catania Univ., Italy
Abstract :
GraphGrep is an application-independent method for querying graphs, finding all the occurrences of a subgraph in a database of graphs. The interface to GraphGrep is a regular expression graph query language Glide that combines features from Xpath and Smart. Glide incorporates both single node and variable-length wildcards. Our algorithm uses hash-based fingerprinting to represent the graphs in an abstract form and to filter the database. GraphGrep has been tested on databases of size up to 16,000 molecules and performs well in this entire range.
Keywords :
graph theory; image matching; query processing; visual databases; Glide; GraphGrep; Smart; Xpath; application-independent method; graph database; graph querying; hash-based fingerprinting; inexact subgraph matching; regular expression graph query language; single node wildcards; subgraph occurrences; variable-length wildcards; Chemistry; Computer science; Computer vision; Data engineering; Data models; Database languages; Design methodology; Indexing; Mathematics; XML;
Conference_Titel :
Pattern Recognition, 2002. Proceedings. 16th International Conference on
Print_ISBN :
0-7695-1695-X
DOI :
10.1109/ICPR.2002.1048250
