{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,15]],"date-time":"2026-10-15T13:54:00Z","timestamp":1792072440566,"version":"4.4.0"},"reference-count":52,"publisher":"Emerald","issue":"2","license":[{"start":{"date-parts":[[2010,6,22]],"date-time":"2010-06-22T00:00:00Z","timestamp":1277164800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.emerald.com\/insight\/site-policies"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010,6,22]]},"abstract":"<jats:sec><jats:title content-type=\"abstract-heading\">Purpose<\/jats:title><jats:p>The purpose of this paper is to provide a detailed discussion for different types of graph queries and a different mechanism for indexing and querying graph databases.<\/jats:p><\/jats:sec><jats:sec><jats:title content-type=\"abstract-heading\">Design\/methodology\/approach<\/jats:title><jats:p>The paper reviews the existing approaches and techniques for indexing and querying graph databases. For each approach, the strengths and weaknesses are discussed with particular emphasis on the target application domain. Based on an analysis of the state\u2010of\u2010the\u2010art of research literature, the paper provides insights for future research directions and untouched challenging research aspects.<\/jats:p><\/jats:sec><jats:sec><jats:title content-type=\"abstract-heading\">Findings<\/jats:title><jats:p>Several graph indexing and querying techniques have been proposed in the literature. However, there is still a clear room for improvement and further research issues in that domain.<\/jats:p><\/jats:sec><jats:sec><jats:title content-type=\"abstract-heading\">Research limitations\/implications<\/jats:title><jats:p>The paper identifies the advantages and disadvantages of the different graph indexing mechanisms and their suitability for different practical applications. The paper provides some guidelines and recommendations which are useful for future research in the area of graph databases.<\/jats:p><\/jats:sec><jats:sec><jats:title content-type=\"abstract-heading\">Practical implications<\/jats:title><jats:p>The paper has practical implications for social networks, protein networks, chemical compounds, multimedia database, and semantic web.<\/jats:p><\/jats:sec><jats:sec><jats:title content-type=\"abstract-heading\">Originality\/value<\/jats:title><jats:p>The paper contributes to the implementation of an efficient indexing and querying mechanism for graph databases in different application domains.<\/jats:p><\/jats:sec>","DOI":"10.1108\/17440081011053104","type":"journal-article","created":{"date-parts":[[2010,6,26]],"date-time":"2010-06-26T07:26:23Z","timestamp":1277537183000},"page":"101-120","source":"Crossref","is-referenced-by-count":27,"title":["Graph indexing and querying: a review"],"prefix":"10.1108","volume":"6","author":[{"given":"Sherif","family":"Sakr","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ghazi","family":"Al\u2010Naymat","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"140","reference":[{"key":"key2022030820180266000_b4","doi-asserted-by":"crossref","unstructured":"Angles, R. and Guti\u00e9rrez, C. (2008), \u201cSurvey of graph database models\u201d, ACM Computing Surveys, Vol. 40 No. 1, pp. 1\u201039.","DOI":"10.1145\/1322432.1322433"},{"key":"key2022030820180266000_b5","doi-asserted-by":"crossref","unstructured":"Bruno, N., Chaudhuri, S. and Ramamurthy, R. (2009), \u201cPower hints for query optimization\u201d, Proceedings of the 25th International Conference on Data Engineering (ICDE), Shanghai, March 29\u2010April 2, pp. 469\u201080.","DOI":"10.1109\/ICDE.2009.68"},{"key":"key2022030820180266000_b6","doi-asserted-by":"crossref","unstructured":"Bunke, H. and Shearer, K. (1998), \u201cA graph distance metric based on the maximal common subgraph\u201d, Pattern Recognition Letters, Vol. 19 Nos 3\u20104, pp. 255\u20109.","DOI":"10.1016\/S0167-8655(97)00179-7"},{"key":"key2022030820180266000_b7","doi-asserted-by":"crossref","unstructured":"Cai, D., Shao, Z., He, X., Yan, X. and Han, J. (2005), \u201cCommunity mining from multi\u2010relational networks\u201d, Proceedings of the 9th European Conference on Principles and Practice of Knowledge Discovery in Databases (PKDD), Porto, October 3\u20107, pp. 445\u201052.","DOI":"10.1007\/11564126_44"},{"key":"key2022030820180266000_b8","unstructured":"Chen, C., Yan, X., Yu, P.S., Han, J., Zhang, D.\u2010Q. and Gu, X. (2007), \u201cTowards graph containment search and indexing\u201d, Proceedings of the 33rd International Conference on Very Large Data Bases (VLDB), University of Vienna, September 23\u201027, pp. 926\u201037."},{"key":"key2022030820180266000_b10","doi-asserted-by":"crossref","unstructured":"Cheng, J., Ke, Y. and Ng, W. (2009), \u201cEfficient query processing on graph databases\u201d, ACM Transactions of Database Systems (TODS), Vol. 34 No. 1.","DOI":"10.1145\/1508857.1508859"},{"key":"key2022030820180266000_b9","doi-asserted-by":"crossref","unstructured":"Cheng, J., Ke, Y., Ng, W. and Lu, A. (2007), \u201cFG\u2010index: towards verification\u2010free query processing on graph databases\u201d, Proceedings of the ACM SIGMOD International Conference on Management of Data, Beijing, June 11\u201014, pp. 857\u201072.","DOI":"10.1145\/1247480.1247574"},{"key":"key2022030820180266000_b11","doi-asserted-by":"crossref","unstructured":"Consens, M.P. and Mendelzon, A.O. (1990), \u201cGraphLog: a visual formalism for real life recursion\u201d, Proceedings of the Ninth ACM SIGACT\u2010SIGMOD\u2010SIGART Symposium on Principles of Database Systems (PODS), Nashville, TN, April 2\u20104, pp. 404\u201016.","DOI":"10.1145\/298514.298591"},{"key":"key2022030820180266000_b12","doi-asserted-by":"crossref","unstructured":"Fern\u00e1ndez, M.\u2010L. and Valiente, G. (2001), \u201cA graph distance metric combining maximum common subgraph and minimum common supergraph\u201d, Pattern Recognition Letters, Vol. 22 Nos 6\/7, pp. 753\u20108.","DOI":"10.1016\/S0167-8655(01)00017-4"},{"key":"key2022030820180266000_b13","unstructured":"Fortin, S. (1996), The Graph Isomorphism Problem, Tech. Rep., Department of Computing Science, University of Alberta, Edmonton."},{"key":"key2022030820180266000_b14","doi-asserted-by":"crossref","unstructured":"Gao, X., Xiao, B., Tao, D. and Li, X. (2010), \u201cA survey of graph edit distance\u201d, Pattern Analysis and Applications, Vol. 13 No. 1, pp. 113\u201029.","DOI":"10.1007\/s10044-008-0141-y"},{"key":"key2022030820180266000_b15","unstructured":"Garey, M.R. and Johnson, D.S. (1979), Computers and Intractability: A Guide to the Theory of NP\u2010Completeness, W.H. Freeman, San Francisco, CA."},{"key":"key2022030820180266000_b16","unstructured":"Giugno, R. and Shasha, D. (2002), \u201cGraphGrep: a fast and universal method for querying graphs\u201d, IEEE International Conference in Pattern Recognition (ICPR), pp. 112\u201015."},{"key":"key2022030820180266000_b17","doi-asserted-by":"crossref","unstructured":"Guttman, A. (1984), \u201cR\u2010trees : a dynamic index structure for spatial searching\u201d, Proceedings of the ACM SIGMOD International Conference on Management of Data, Boston, MA, pp. 47\u201057.","DOI":"10.1145\/971697.602266"},{"key":"key2022030820180266000_b18","doi-asserted-by":"crossref","unstructured":"Gyssens, M., Paredaens, J., den Bussche, J.V. and Gucht, D.V. (1994), \u201cA graph\u2010oriented object database model\u201d, IEEE Transactions of Knowledge and Data Engineering (TKDE), Vol. 6 No. 4, pp. 572\u201086.","DOI":"10.1109\/69.298174"},{"key":"key2022030820180266000_b19","unstructured":"He, H. and Singh, A.K. (2006), \u201cClosure\u2010tree: an index structure for graph queries\u201d, Proceedings of the 22nd International Conference on Data Engineering (ICDE), Atlanta, GA, April 3\u20107, pp. 38\u201052."},{"key":"key2022030820180266000_b20","doi-asserted-by":"crossref","unstructured":"Huan, J., Wang, W., Bandyopadhyay, D., Snoeyink, J., Prins, J. and Tropsha, A. (2004), \u201cMining protein family specific residue packing patterns from protein structure graphs\u201d, Proceedings of the Eighth Annual International Conference on Computational Molecular Biology (RECOMB), San Diego, CA, March 27\u201031, pp. 308\u201015.","DOI":"10.1145\/974614.974655"},{"key":"key2022030820180266000_b21","doi-asserted-by":"crossref","unstructured":"Jiang, H., Wang, H., Yu, P.S. and Zhou, S. (2007), \u201cGString: a novel approach for efficient search in graph databases\u201d, Proceedings of the 23rd International Conference on Data Engineering (ICDE), Istanbul, April 15\u201020, pp. 566\u201075.","DOI":"10.1109\/ICDE.2007.367902"},{"key":"key2022030820180266000_b22","unstructured":"Klinger, S. and Austin, J. (2005), \u201cChemical similarity searching using a neural graph matcher\u201d, Proceedings of the 13th European Symposium on Artificial Neural Networks (ESANN), Bruges, April 27\u201029, pp. 479\u201084."},{"key":"key2022030820180266000_b23","unstructured":"Kuramochi, M. and Karypis, G. (2001), \u201cFrequent subgraph discovery\u201d, Proceedings of the IEEE International Conference on Data Mining (ICDM), San Jose, CA, November 29\u2010December 2, pp. 313\u201020."},{"key":"key2022030820180266000_b24","doi-asserted-by":"crossref","unstructured":"Kuramochi, M. and Karypis, G. (2004), \u201cGREW\u2010A scalable frequent subgraph discovery algorithm\u201d, Proceedings of the IEEE International Conference on Data Mining (ICDM), Brighton, November 1\u20104, pp. 439\u201042.","DOI":"10.21236\/ADA439436"},{"key":"key2022030820180266000_b2","unstructured":"Kyoto Encyclopedia of Genes and Genomes (KEGG) (2010), available at: www.genome.jp\/kegg\/."},{"key":"key2022030820180266000_b25","doi-asserted-by":"crossref","unstructured":"Lee, J., Oh, J.\u2010H. and Hwang, S. (2005), \u201cSTRG\u2010Index: spatio\u2010temporal region graph indexing for large video databases\u201d, Proceedings of the ACM SIGMOD International Conference on Management of Data, Baltimore, MD, June 14\u201016, pp. 718\u201029.","DOI":"10.1145\/1066157.1066239"},{"key":"key2022030820180266000_b26","unstructured":"Manola, F. and Miller, E. (2004), \u201cRDF primer: world wide web consortium proposed recommendation\u201d, available at: www.w3.org\/TR\/rdf\u2010primer\/."},{"key":"key2022030820180266000_b3","unstructured":"National Cancer Institute (NCI) (2010), available at: http:\/\/dtp.nci.nih.gov\/."},{"key":"key2022030820180266000_b27","unstructured":"Prud'hommeaux, E. and Seaborne, A. (2008), \u201cSPARQL query language for RDF: world wide web consortium proposed recommendation\u201d, available at: www.w3.org\/TR\/rdf\u2010sparql\u2010query\/."},{"key":"key2022030820180266000_b28","doi-asserted-by":"crossref","unstructured":"Raymond, J.W., Gardiner, E.J. and Willett, P. (2002), \u201cRASCAL: calculation of graph similarity using maximum common edge subgraphs\u201d, Computer Journal, Vol. 45 No. 6, pp. 631\u201044.","DOI":"10.1093\/comjnl\/45.6.631"},{"key":"key2022030820180266000_b29","doi-asserted-by":"crossref","unstructured":"Sakr, S. (2009), \u201cGraphREL: a decomposition\u2010based and selectivity\u2010aware relational framework for processing sub\u2010graph queries\u201d, Proceedings of the 14th International Conference on Database Systems for Advanced Applications (\u2009DASFAA), Brisbane, April 21\u201023, pp. 123\u201037.","DOI":"10.1007\/978-3-642-00887-0_11"},{"key":"key2022030820180266000_b30","doi-asserted-by":"crossref","unstructured":"Sakr, S. and Awad, A. (2010), \u201cA framework for querying graph\u2010based business process models\u201d, Proceedings of the 19th International World Wide Web Conference (www), Raleigh, NC.","DOI":"10.1145\/1772690.1772906"},{"key":"key2022030820180266000_b31","doi-asserted-by":"crossref","unstructured":"Sayed, A. (2009), \u201cFast and efficient computation of reachability queries over linked XML documents' graphs\u201d, International Journal of Web Information Systems (\u2009IJWIS), Vol. 5 No. 1, pp. 56\u201076.","DOI":"10.1108\/17440080910947312"},{"key":"key2022030820180266000_b32","unstructured":"Sheng, L., \u00d6zsoyoglu, Z.M. and \u00d6zsoyoglu, G. (1999), \u201cA graph query language and its query processing\u201d, Proceedings of the 15th International Conference on Data Engineering (\u2009ICDE), IEEE Computer Society, Washington, DC, pp. 572\u201081."},{"key":"key2022030820180266000_b33","unstructured":"Srinivasa, S., Maier, M., Mutalikdesai, M.R., Gowrishankar, K.A. and Gopinath, P.S. (2005), \u201cLWI and safari: a new index structure and query model for graph databases\u201d, Proceedings of the Eleventh International Conference on Management of Data (COMAD), Goa, January, pp. 138\u201047."},{"key":"key2022030820180266000_b34","doi-asserted-by":"crossref","unstructured":"Stocker, M., Seaborne, A., Bernstein, A., Kiefer, C. and Reynolds, D. (2008), \u201cSPARQL basic graph pattern optimization using selectivity estimation\u201d, Proceedings of the 17th International Conference on World Wide Web (www), Beijing, pp. 595\u2010604.","DOI":"10.1145\/1367497.1367578"},{"key":"key2022030820180266000_b35","doi-asserted-by":"crossref","unstructured":"Teubner, J., Grust, T., Maneth, S. and Sakr, S. (2008), \u201cDependable cardinality forecasts for XQuery\u201d, Proceedings of the VLDB Endowment (PVLDB), Auckland, August 23\u201028, Vol. 1 (1) pp. 463\u201077.","DOI":"10.14778\/1453856.1453908"},{"key":"key2022030820180266000_b1","unstructured":"The Gene Ontology (2010), available at: www.geneontology.org\/."},{"key":"key2022030820180266000_b36","doi-asserted-by":"crossref","unstructured":"Tian, Y. and Patel, J.M. (2008), \u201cTALE : a tool for approximate large graph matching\u201d, Proceedings of the 24th International Conference on Data Engineering (ICDE), Canc\u00fan, April 7\u201012, pp. 963\u201072.","DOI":"10.1109\/ICDE.2008.4497505"},{"key":"key2022030820180266000_b37","doi-asserted-by":"crossref","unstructured":"Tian, Y., McEachin, R.C., Santos, C., States, D.J. and Patel, J.M. (2007), \u201cSAGA: a subgraph matching tool for biological graphs\u201d, Bioinformatics, Vol. 23 No. 2, pp. 232\u20109.","DOI":"10.1093\/bioinformatics\/btl571"},{"key":"key2022030820180266000_b38","doi-asserted-by":"crossref","unstructured":"Tian, Y., Patel, J.M., Nair, V., Martini, S. and Kretzler, M. (2008), \u201cPeriscope\/GQ: a graph querying toolkit\u201d, Proceedings of the VLDB Endowment (PVLDB), Vol. 1 No. 2, pp. 1404\u20107.","DOI":"10.14778\/1454159.1454184"},{"key":"key2022030820180266000_b39","doi-asserted-by":"crossref","unstructured":"Wang, C., Wang, W., Pei, J., Zhu, Y. and Shi, B. (2004), \u201cScalable mining of large disk\u2010based graph databases\u201d, Proceedings of the Tenth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), Seattle, Washington, DC, August 22\u201025, pp. 316\u201025.","DOI":"10.1145\/1014052.1014088"},{"key":"key2022030820180266000_b40","doi-asserted-by":"crossref","unstructured":"Washio, T. and Motoda, H. (2003), \u201cState of the art of graph\u2010based data mining\u201d, SIGKDD Explorations, Vol. 5 No. 1, pp. 59\u201068.","DOI":"10.1145\/959242.959249"},{"key":"key2022030820180266000_b41","doi-asserted-by":"crossref","unstructured":"Westbrook, J.D., Feng, Z., Chen, L., Yang, H. and Berman, H.M. (2003), \u201cThe protein data bank and structural genomics\u201d, Nucleic Acids Research, Vol. 31 No. 1, pp. 489\u201091.","DOI":"10.1093\/nar\/gkg068"},{"key":"key2022030820180266000_b42","doi-asserted-by":"crossref","unstructured":"Williams, D.W., Huan, J. and Wang, W. (2007), \u201cGraph database indexing using structured graph decomposition\u201d, Proceedings of the 23rd International Conference on Data Engineering (ICDE), Istanbul, pp. 976\u201085.","DOI":"10.1109\/ICDE.2007.368956"},{"key":"key2022030820180266000_b43","unstructured":"Yan, X. and Han, J. (2002), \u201cgSpan: graph\u2010based substructure pattern mining\u201d, Proceedings of the IEEE International Conference on Data Mining (ICDM), Maebashi City, December 9\u201012, pp. 721\u20104."},{"key":"key2022030820180266000_b44","doi-asserted-by":"crossref","unstructured":"Yan, X. and Han, J. (2003), \u201cCloseGraph: mining closed frequent graph patterns\u201d, Proceedings of the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), New York, NY, pp. 286\u201095.","DOI":"10.1145\/956750.956784"},{"key":"key2022030820180266000_b45","doi-asserted-by":"crossref","unstructured":"Yan, X., Yu, P.S. and Han, J. (2004), \u201cGraph indexing: a frequent structure\u2010based approach\u201d, Proceedings of the ACM SIGMOD International Conference on Management of Data, Paris, June 13\u201018, pp. 335\u201046.","DOI":"10.1145\/1007568.1007607"},{"key":"key2022030820180266000_b46","doi-asserted-by":"crossref","unstructured":"Yan, X., Yu, P.S. and Han, J. (2005a), \u201cGraph indexing based on discriminative frequent structure analysis\u201d, ACM Transactions on Database Systems (TODS), Vol. 30 No. 4, pp. 960\u201093.","DOI":"10.1145\/1114244.1114248"},{"key":"key2022030820180266000_b47","doi-asserted-by":"crossref","unstructured":"Yan, X., Yu, P.S. and Han, J. (2005b), \u201cSubstructure similarity search in graph databases\u201d, Proceedings of the ACM SIGMOD International Conference on Management of Data, Baltimore, MD, June 14\u201016, pp. 766\u201077.","DOI":"10.1145\/1066157.1066244"},{"key":"key2022030820180266000_b48","unstructured":"Yan, X., Zhu, F., Han, J. and Yu, P.S. (2006), \u201cSearching substructures with superimposed distance\u201d, Proceedings of the 22nd International Conference on Data Engineering (ICDE), Washington, DC, pp. 88\u201098."},{"key":"key2022030820180266000_b49","doi-asserted-by":"crossref","unstructured":"Zhang, S., Hu, M. and Yang, J. (2007), \u201cTreePi: a novel graph indexing method\u201d, Proceedings of the 23rd International Conference on Data Engineering (ICDE), Istanbul, 15\u201020 April, pp. 966\u201075.","DOI":"10.1109\/ICDE.2007.368955"},{"key":"key2022030820180266000_b50","doi-asserted-by":"crossref","unstructured":"Zhang, S., Li, J., Gao, H. and Zou, Z. (2009), \u201cA novel approach for efficient supergraph query processing on graph databases\u201d, Proceedings of the 12th International Conference on Extending Database Technology (EDBT), Saint Petersburg, March 24\u201026, pp. 204\u201015.","DOI":"10.1145\/1516360.1516385"},{"key":"key2022030820180266000_b51","unstructured":"Zhao, P., Yu, J.X. and Yu, P.S. (2007), \u201cGraph indexing: tree+delta\u2265graph\u201d, Proceedings of the 33rd International Conference on Very Large Data Bases (VLDB), Vienna, pp. 938\u201049."},{"key":"key2022030820180266000_b52","doi-asserted-by":"crossref","unstructured":"Zou, L., Chen, L., Yu, J.X. and Lu, Y. (2008), \u201cA novel spectral coding in a large graph database\u201d, Proceedings of the 11th International Conference on Extending Database Technology (EDBT), Nantes, March 25\u201029, pp. 181\u201092.","DOI":"10.1145\/1353343.1353369"}],"container-title":["International Journal of Web Information Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/www.emeraldinsight.com\/doi\/full-xml\/10.1108\/17440081011053104","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.emerald.com\/insight\/content\/doi\/10.1108\/17440081011053104\/full\/xml","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.emerald.com\/insight\/content\/doi\/10.1108\/17440081011053104\/full\/html","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,7,25]],"date-time":"2025-07-25T00:25:00Z","timestamp":1753403100000},"score":1,"resource":{"primary":{"URL":"http:\/\/www.emerald.com\/ijwis\/article\/6\/2\/101-120\/166449"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,6,22]]},"references-count":52,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2010,6,22]]}},"alternative-id":["10.1108\/17440081011053104"],"URL":"https:\/\/doi.org\/10.1108\/17440081011053104","relation":{},"ISSN":["1744-0084"],"issn-type":[{"value":"1744-0084","type":"print"}],"subject":[],"published":{"date-parts":[[2010,6,22]]}}}