DocumentCode
2462355
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
Volume
2
fYear
2002
fDate
2002
Firstpage
112
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;
fLanguage
English
Publisher
ieee
Conference_Titel
Pattern Recognition, 2002. Proceedings. 16th International Conference on
ISSN
1051-4651
Print_ISBN
0-7695-1695-X
Type
conf
DOI
10.1109/ICPR.2002.1048250
Filename
1048250
Link To Document