Applying the XML-based Technique to Support Keyword Search in Graph Data

Authors

  • Ya-Hui Chang Department of Computer Science and Engineering, National Taiwan Ocean University, Keelung, Taiwan
  • Si-Yen Zhuang Department of Computer Science and Engineering, National Taiwan Ocean University, Keelung, Taiwan

DOI:

https://doi.org/10.37591/joadms.v1i2.165

Abstract

Graphs have been important and proper structures to represent data with complex relationships in the Web, and keyword search provides a convenient way to querying graphs. Some researchers considered to return r-cliques as answers for keyword search in graph databases. Such concepts can retrieve meaningful information effectively, but the existing approach is computationally expensive. In this paper, we propose to utilize the efficient technique originally designed for keyword search in XML data to help identify answers. The main idea is first transforming the input graph into a tree, and then applying the efficient ELCA technique on the transformed tree to find the subtrees which consist of closely-related matches. The specially-designed SRE and SRE* algorithms are then applied on these subtrees to identify r-cliques. We have proposed several strategies for transforming graphs into trees and designed a series of experiments to examine their performance. Experimental results show that our approaches perform very well in terms of efficiency and recall.

Keywords: Keyword search, Graph database, ELCA

Author Biography

  • Ya-Hui Chang, Department of Computer Science and Engineering, National Taiwan Ocean University, Keelung, Taiwan
    Curricular Vitae Ya-hui Chang [email protected] No. 2 Beining Road, Keelung, Taiwan Department of Computer Science and Engineering National Taiwan Ocean University  Academic background:  Department of Computer Science and Engineering, National Taiwan University, Taiwan, Bachelor of Engineering: June, 1990.  Department of Computer Science, University of Maryland at College Park, USA, Master of Science: May, 1993.  Department of Computer Science, University of Maryland at College Park, USA, Ph.D.: Dec., 1995.  Teaching Experience:  Department of Computer Science and Information Management, Providence University, Taiwan, Associate Professor: 08/1995 – 07/1998  Department of Computer Science and Engineering, National Taiwan Ocean University, Taiwan, Associate Professor: 08/1998 till now  Publication Lists: A. Journal Papers 1. Louiqa Raschid, Ya-Hui Chang, “Interoperable Query Processing from Object to Relational Schemas Based on a Parameterized Canonical Representation”, International Journal of Cooperative Information systems, Vol. 4, No. 1, 81-120, 1995, World Scientific Publisher (SCI, impact factor: 1.371). 2. Ya-Hui Chang, Louiqa Raschid, “Producing Interoperable Queries for Relational and Object-Oriented Databases”, Journal of Intelligent Information Systems, Vol. 14, No. 1, 2000, Springer Publisher (SCI, EI, impact factor: 1.234). 3. Ya-Hui Chang, Ben-Hsu Chen, Chun-Chieh Wu, “The Design and Implementation of an Efficient Library Management System by XML”, Journal of Internet Technology, volume 2, number 4, 2001. 4. Ya-Hui Chang, “A Graphical query language for mobile information systems”, SIGMOD Record 32(1): 20-25, 2003, ACM Publisher (SCI, EI, impact factor: 1.155). 5. Hsiao-Fei Liu, Ya-Hui Chang, Kun-Mao Chao, “An Optimal Algorithm for Querying Tree Structures and its Applications in Bioinformatics”, SIGMOD Record 33(2): 21-26, 2004, ACM Publisher (SCI, EI, impact factor: 1.155). 6. 謝璨隆、張雅惠、蘇智宏，“XML資料之管理與查詢”，Communication of IICM, Vol. 7 No.2（資訊學會通訊，第七卷第二期），pp. 85~100, 2004. 7. Cheng-Tao Chu, Ya-Hui Chang*, “IndexPro: An Efficient Protein Indexing System Based on Knot Theory”, Journal of the Chinese Institute of Engineers, Vol. 30, No. 4, pp. 703-715, 2007. (SCI, EI, impact factor: 0.19) 8. Ya-Hui Chang, Cheng-Ta Lee, Wang-Chien Lee, “A Path-based Approach for Efficient Evaluation of Twig Queries over XML Data”, Journal of Information Science and Engineering, Institute of Information Science Publisher, Vol. 23, No. 5, pp. 1523-1540, 2007 (SCI, EI, impact factor: 0.268). 9. Ya-Hui Chang, Chieh-Chang Luo, Chih-Chung Huang, “Efficient Evaluation of XML Twig Queries with Keyword Constraints”, Journal of the Chinese Institute of Engineers, Vol. 32, No. 4, pp. 469-480, 2009 (SCI, EI, impact factor: 0.19) 10. Rung-Ren Lin, Ya-hui Chang*, Kun-Mao Chao, “Improving the Performance of Identifying Contributors for XML Keyword Search”, SIGMOD Record, 40(1), pp. 5-10, 2011. 11. Ya-Hui Chang, Cheng-Yi Wu, Cheng-Cheng Lo, “Processing XML Queries with Structural and Full-Text Constraints”, Journal of Information Science and Engineering, Vol. 28, No. 2, pp. 221-242, 2012. 12. Ya-Hui Chang, “Optimizing XML Twig Queries with Full-Text Predicates”, SIGMOD Record, 41(1), pp. 5-10, 2012. 13. Ya-Hui Chang, Chih-Chung Huang, Po-Hsien Chien, “Efficient Grouping and Ordering Processing on XML Data”, Journal of the Chinese Institute of Engineers, Vol. 35, No. 6, pp. 697-709, 2012. B. Conference Papers 1. Louiqa Raschid, Ya-hui Chang, and Bonnie Dorr, “Interoperable query processing with multiple heterogeneous knowledge servers”, Proceedings of the second international conference on information and knowledge management (CIKM), 1993 (EI). 2. Louiqa Raschid, Ya-hui Chang, and Bonnie Dorr, “Query transformation techniques for interoperable query processing in cooperative information systems”, Proceedings of the second international conference on cooperative information systems (COOIPIS), 1994. 3. Ya-Hui Chang, Louiqa Raschid, and Bonnie Dorr, “Transforming queries from a relational schema to an equivalent object schema: a prototype based on F-logic”, Proceedings of the eighth international symposium on methodologies for intelligent systems (ISMIS), LNAI, 1994. 4. Ya-Hui Chang, Louiqa Raschid, “Building Parameterized Canonical Representations to Achieve Interoperability Among Heterogeneous Databases”, Proceedings of the Sixth International Hong Kong Computer Society Database Workshop on Database Reengineering and Interoperability, Hong Kong, March, 1995. (EI) 5. Ya-Hui Chang, “An Algorithm to Extract Semantics from relational Query Languages”, Proceedings of the Thirteenth Workshop on Combinatorial Mathematics and Computation Theory, Shalu, Taiwan, R. O. C., June, 1996. 6. Ya-Hui Chang, Jia-Ling Koh, Arbee Chen, “An Object-Oriented Approach to Modeling and Querying in Multimedia Information Systems”, Proceedings of the Second Conference on Multimedia Information Systems, 1997. 7. Ya-Hui Chang, “A Query Translator to Achieve Interoperability for Relational and Object-Oriented Databases”, Proceedings of the Conference on Distributed System Technologies and Applications, 1998. 8. 羅壽之, 吳育瑋, 陳良弼, 張雅惠, “行動式警政資訊系統之查詢設計”, Workshop on Distributed System Technologies & Applications, 1999. 9. Ya-Hui Chang, “A Query Language for Mobile Information Systems”, Proceedings of IEEE ICDCS workshop on wireless network and mobile computing, 2000. 10. 張雅惠, 林吉村, “行動式警政資訊系統之使用者介面設計”, 2000網際網路與分散式系統研討會論文集, 2000。 11. 張雅惠, 吳俊頡, 謝璨隆, “查詢多份XML文件的資料結構設計”, 廿一世紀數位生活與網際網路科技研討會論文集, 2001. 12. 張雅惠, 吳俊頡, 謝璨隆, “支援XML文件查詢的索引結構”, 中華民國九十年全國計算機會議論文集, 2001. 13. 張雅惠, 邱豐傑, “整合關聯式資料庫與XML資料之仲介者架構”， 2002數位生活與網際網路科技研討會論文集, 2002. 14. Ya-Hui Chang, Tsan-Lung Hsieh, “A document-based approach to indexing XML data”, Proceedings of the fourth international conference on information integration and web-based applications & services (IIWAS), 2002. 15. Ya-Hui Chang , Cheng-Ta Lee, “Supporting selection-projection XQuery Processing based on encoding paths”, Proceedings of the Eighth International Conference on Database Systems for Advanced Applications (DASFAA), 2003. 16. 張雅惠，邱豐傑, “企業異質性資料之整合管理系統”，2003年電子商務與數位生活研討會論文集, 2003． 17. 張雅惠, 呂信賢, “以XML為基礎的數位文件管理系統”, 2003數位生活與網際網路科技研討會, 2003. 18. 呂信賢, 劉邦鑑, 張雅惠, “解決關聯式與XML資料差異性之對應資料與建構演算法”, 二○○四數位生活與網際網路科技研討會, 2004. 19. 劉邦鑑, 張雅惠, “典藏數位化中異質性資料之對應與建構演算法”, 第三屆數位典藏技術研討會, 2004. 20. Ya-Hui Chang, Feng-Chieh Chiu, Wang-Chien Lee, “Schema Mapping for XML and Relational Data Sharing”, Proceedings of the International Computer Symposium, 2004. 21. Ya-Hui Chang, Bang-Chien Liu, Sue-Shain Wu, “Query Transformation to Support Information Sharing in Digital Archives”, Proceedings of ICDAT, 2005 22. 李政達, 羅介璋, 張雅惠, “數位典藏中後設資料之查詢處理設計”, 第四屆數位典藏技術研討會, 2005. 23. Ya-Hui Chang, Greg Liu, Sue-Shain Wu, “Translating XQuery to SQL based on Query Forests”, Database Systems for Advanced Applications (DASFAA), LNCS 3453, pp. 894-899, 2005, Springer-Verlag publisher (SCI ,EI, impact factor: 0.402). 24. Ya-Hui Chang, Cheng-Ta Lee, Chieh-Chang Luo, “Efficient Evaluation of XML Twig Queries”, Advanced Web and Network Technologies and Applications, LNCS 3842, pp. 48-57, 2006, Springer-Verlag publisher (SCI, EI, impact factor: 0.402). 25. 劉邦鑑, 李佳臻, 張雅惠,“支援SQL與ＸQuery之雙向查詢句轉換系統”, 全國計算機會議論文集, 2007. 26. Ya-Hui Chang, Chia-Zhen Lee, “Representing Multiple Mappings between Relational and XML Schemas to Support Interoperability”, Proceedings of the International Computer Symposium, 2008. 27. Ya-Hui Chang, Chia-Zhen Lee, “Representing Multiple Mappings between XML and Relational Schemas for Bi-directional Query Translation”, Proceedings of the APWEB-WAIM joint conference, 2009, LNCS5446 (EI). 28. 黃治中, 簡伯先, 張雅惠, “XML資料分群之查詢處理設計”, 全國計算機會議論文集, 2009. 29. 吳政儀, 羅誠正, 張雅惠, “支援具有複雜關鍵字與結構限制之XML查詢系統”, 全國計算機會議論文集, 2009. 30. Rung-Ren Lin, Ya-Hui Chang, and Kun-Mao Chao, “Faster Algorithms for Searching Relevant Matches in XML Databases”, Proceedings of the 21st International Conference on Database and Expert Systems Applications (DEXA), LNCS 6261, pp. 290-297, 2010. (EI). 31. Rung-Ren Lin, Ya-Hui Chang*, and Kun-Mao Chao, “Identifying Relevant Matches with NOT Semantics over XML Documents”, Proceedings of the DASFAA conference, LNCS 6587, pp. 466–480, 2011 (EI). 32. 吳佩珊, 張雅惠, “一個基於Web Service 的洪氾預警系統”, 2011台灣軟體工程暨物件導向技術及應用研討會論文集, 2011. 33. 簡伯先, 張雅惠, 張祐愷, “快速輸出 XML 關鍵字查詢之有效節點”, 全國計算機會議論文集, 2011. 34. Ya-Hui Chang, Po-Hsien Chien, and Yu-Kai Chang, “Efficiently Identifying Contributors for XML Keyword Search”, Proceedings of the DASFAA conference, LNCS 7238, 2012 (EI). 35. Han-Yu Lin, Chien-Ming Chen, Yu-Lun Chen, Ya-Hui Chang, and Tun-Wen Pai*, “Construction of a Taiwan biodiversity genetic database in cloud environments”, 2012 International Symposium on Biometrics and Security Technologies (2012 ISBAST), pp. 108-112, Taipei, Taiwan, Mar.26-29, 2012. 36. Ya-Hui Chang, Pei-Shan Wu, Yu-Te Liu, and Shang-Pin Ma, “An Effective Flood Forecasting System Based on Web Services”, Proceedings of the International Computer Symposium, 2012. 37. Rung-Ren Lin, Ya-Hui Chang and Kun-Mao Chao, “A Compact and Efficient Labeling Scheme for XML Documents”, Proceedings of the DASFAA conference, LNCS 7825, 2013. C. Books 1. 趙坤茂、張雅惠、黃寶萱，計算機概論，全華科技圖書股份有限公司，2004-2011。 D. Collection Papers 1. Chang, Y., Raschid, L., "Using Parameterized Canonical Representations to Resolve Conflicts and Achieve Interoperability between Relational and Object Databases", Database Interoperability and engineering, T. Cheung, J. Fong and B. Siu, Eds., Plenum Press, New York. 1996. E. Technical Reports 1. Ya-Hui Chang (1997), “Interoperable Query Processing among Heterogeneous Databases”, NSC report under grant 86-2213-E-126-006. 2. Ya-Hui Chang (1998), “The research and design of data models, query languages and user interface for a mobile information system (I)”, NSC report under grant 87-2213-E-126-005. 3. Ya-Hui Chang (1999), “The research and design of data models, query languages and user interfaces for a mobile information system (II)”, NSC report under grant 88-2213-E-019-005-. 4. Ya-Hui Chang (2000), “電子商務中結構化與非結構化資料管理之研究(I)”, NSC report under grant 89-2213-E-019-013- 5. Ya-Hui Chang (2001), “電子商務中結構化與非結構化資料管理之研究(II)”, NSC report under grant 89-2218-E-019-002 6. Ya-Hui Chang (2002), “電子商務中結構化與非結構化資料管理之研究(III)”, NSC report under grant 90-2213-E-019-011 7. Ya-Hui Chang (2003), “XML資料查詢之研究與製作(I)”, NSC report under grant 91-2213-E-019-007 8. Ya-Hui Chang (2004), “XML資料查詢之研究與製作(II)”, NSC report under grant 92-2213-E-019-010- 9. Ya-Hui Chang (2005), “典藏數位化中結構化關聯式與半結構化XML資料管理之研究”, NSC report under grant 93-2422-H-019-001 10. Ya-Hui Chang (2005), “典藏數位化中結構化關聯式與半結構化XML資料管理之研究”, NSC report under grant 93-2422-H-019-001 11. Ya-Hui Chang (2006), “典藏數位化中結構化關聯式與半結構化XML資料管理之研究 (II)”, NSC report under grant 94-2422-H-019-001 12. Ya-Hui Chang (2007), “典藏數位化中結構化關聯式與半結構化XML資料管理之研究(III)”, NSC report under grant 95-2422-H-019-001 13. Ya-Hui Chang (2008), “XML資訊庫查詢技術之研究”, NSC report under grant 95-2221-E-019-094 14. Ya-Hui Chang (2008), “XML文件之結構限制與關鍵字查詢之研究”, NSC report under grant 96-2221-E-019-048 15. Ya-Hui Chang (2009), “XML 文件之結構限制與關鍵字查詢之研究 (II)”, NSC report under grant 97-2221-E-019-028-

References

Ding B., Lin X., Qin L., et al. Finding Top-k Min-cost Connected Trees in Databases. Proceedings of the ICDE Conference, 2007, 836–845p.

Gubichev A., Neumann T. Fast Approximation of Steiner Trees in Large Graphs. Proceedings of the CIKM Conference, ACM New York, NY, USA, 2012, 1497–1501p.

Kargar M., An A. Keyword Search in Graphs: Finding r-cliques. Proceedings of the VLDB Conference, 2011, 681–692p.

Li G., B. Ooi B, Feng J., et al. Ease: An Effective 3-in-1 Keyword Search Method for Unstructured, Semi-structured and Structured Data. Proceedings of the SIGMOD Conference, Vancouver, Canada, 2008, 903–914p.

Qin L., Yu J., Chang L., et al. Querying Communities in Relational Databases. Proceedings of the ICDE Conference, 2009.

Xu Y., Papakonstantinou Y. Efficient Keyword Search for Smallest LCAS in xml Databases. Proceedings of the SIGMOD Conference, 2005, 527–538p.

Xu Y., Papakonstantinou Y. Efficient lca based Keyword Search in XML Data. Proceedings of the EDBT Conference, 2008, 535–546p.

Zhou J., Bao Z., Wang W., et al. Fast SLCA and ELCA Computation for XML Keyword Queries based on Set Intersection. Proceedings of the ICDE Conference, Washington, DC, 2012, 905–916p.

H.-I. Lu, Ravi R. Approximating Maximum Leaf Spanning Trees in almost

Linear Time. J. Algorithms. 1998; 29(1): 132–41p.

Chu A., Chao K., Wu B. A Linear-time Algorithm for finding an Edge-Partition with Max-min Ratio at Most Two. Discrete Appl. Math. 2013; 161(7-8): 932–43p.

Downloads

Published

2014-08-27

Issue

Vol. 1 No. 2 (2014)

Section

Research Articles

License

Declaration and Copyright Transfer Form

(to be completed by authors)

I/ We, the undersigned author(s) of the submitted manuscript, hereby declare, that the above manuscript which is submitted for publication in the STM Journals(s), is not published already in part or whole (except in the form of abstract) in any journal or magazine for private or public circulation, and, is not under consideration of publication elsewhere.

  • I/We will not withdraw the manuscript after 1 week of submission as I have read the Author Guidelines and will adhere to the guidelines.
  • I/We Author(s ) have niether given nor will give this manuscript elsewhere for publishing after submitting in STM Journal(s).
  • I/ We have read the original version of the manuscript and am/ are responsible for the thought contents embodied in it. The work dealt in the manuscript is my/ our own, and my/ our individual contribution to this work is significant enough to qualify for authorship.
  •  I/We also agree to the authorship of the article in the following order:

Author’s name                                    

 

1. ________________

2. ________________

3. ________________

4. ________________

 

We  Author(s) tick this box and would request you to consider it as our signature as we agree to the terms of this Copyright Notice, which will apply to this submission if and when it is published by this journal.