Ontology-based query graph matching
8 viewsDOI:
https://doi.org/10.54939/1859-1043.j.mst.105.2025.130-138Keywords:
Ontology; Query matching; Semantic similarity; Pruning techniques.Abstract
The requirement for business competition among organizations has become more complicated in the past decade. One of these issues is how to react and response to queries from clients with the aim of producing quick and timely decision-making. To address this problem, this paper proposes a framework for identifying the frequent queries from multiple sources. The main contribution of this work is (1) query matching based on the ontology. In fact, query matching has been widely explored using various methods, most of which are based on a labeling approach and utilize isomorphism to map a query to subgraphs in a graph database. However, these traditional methods may not capture enough semantic similarity when mapping terms together. Ontology-based matching can address this issue more effectively than mere labeling isomorphism. In this work, three pruning techniques and their combination within dynamically weighted sets of vertex-associated elements are proposed. In addition, (2) a subgraph/subontologies clustering technique is recommended to extract the results of the framework. This technique is based on an existing clustering method, but requires improvements in the data processing step to be applicable to clustering subontologies/subgraph objects. Finally, (3) we experimentally verify the effectiveness and efficiency of our pruning techniques using synthetic data and compare the techniques themselves.
References
[1]. Fudholi, Dhomas & Rahayu, Wenny & Pardede, Eric. “Ontology-Based Information Extraction for Knowledge Enrichment and Validation”. Pattern Recognition, 48(4):1364–1373, (2016).
[2]. Evgeny B Krissinel and Kim Henrick. “Common subgraph isomorphism detection by backtracking search”. Software: Practice and Experience, 34(6):591–607, (2004).
[3]. Abu-khzam, Faisal & Samatova, Nagiza & Rizk, Mohamad & Langston, Michael. “The Maximum Common Subgraph Problem: Faster Solutions via Vertex Cover”. IEEE/ACS International Conference on Computer Systems and Applications, pages 367–373. IEEE, (2007).
[4]. Ina Koch. “Enumerating all connected maximal common subgraphs in two graphs”. Theoretical Computer Science, 250(1):1–30, (2001).
[5]. John W Raymond, Eleanor J Gardiner, and Peter Willett. “Rascal: Calculation of graph similarity using maximum common edge subgraphs”. The Computer Journal, 45(6):631– 644, (2002).
[6]. Davide Mottin, Matteo Lissandrini, Yannis Velegrakis, and Themis Palpanas. “Exemplar queries: Give me an example of what you need”. Proceedings of the VLDB Endowment, 7(5):365–376, (2014).
[7]. Md Saiful Islam, Chengfei Liu, and Jianxin Li. “Efficient answering of why-not questions in similar graph matching”. IEEE Transactions on Knowledge and Data Engineering, 27(10):2672–2686, (2015).
[8]. Ali Cakmak and Gultekin Ozsoyoglu. “Taxonomy-superimposed graph mining”. In Proceedings of the 11th International Conference on Extending Database Technology: Advances in Database Technology, pages 217–228. ACM, (2008).
[9]. Boanerges Aleman-Meza, Christian Halaschek-Wiener, Satya Sanket Sahoo, Amit Sheth, and I Budak Arpinar. “Template-based semantic similarity for security applications”. In International Conference on Intelligence and Security Informatics, pages 621–622. Springer, (2005).
[10]. O. Corby, R. Dieng-Kuntz, F. Gandon, C. Faron-Zucker. “Searching the semantic web: Approximate query processing based on ontologies”. IEEE Intelligent Systems, 21(1):20–27, (2006).
[11]. Eric Little, Kedar Sambhoos, and James Llinas. “Enhancing graph matching techniques with ontologies”. In Information Fusion, 2008 11th International Conference on, pages 1–8. IEEE, (2008).
[12]. Yinghui Wu, Shengqi Yang, and Xifeng Yan. “Ontology-based subgraph querying”. In Data Engineering (ICDE), 2013 IEEE 29th International Conference on, pages 697–708. IEEE, (2013).
[13]. Carlo Wouters, Tharam Dillon, Wenny Rahayu, and Elizabeth Chang. “A practical walkthrough of the ontology derivation rules”. In International Conference on Database and Expert Systems Applications, pages 259–268. Springer, (2002).
[14]. Carlo Wouters, Tharam Dillon, Wenny Rahayu, Elizabeth Chang, and Robert Meersman. “Ontologies on the move”. In International Conference on Database Systems for Advanced Applications, pages 812–823. Springer, (2004).
[15]. Andrew Peter Flahive. “Tailoring large domain ontologies in the semantic grid environment”. PhD thesis, La Trobe University, (2007).
[16]. Lambrix, P., Armiento, R., Li, H., Hartig, O., Abd Nikooie Pour, M., & Li, Y. “The materials design ontology”. Semantic Web, 15(2), 481-515, (2024).
