Efficient and Effective Search over Graph-like Databases

世界上许多高质量的企业和社交数据都以半结构化和结构化数据的形式存储。这包括企业的RDBMS、知识图谱和社交网络。所有这些数据集合要么已经定义为图形，要么可以重新建模为图形。在过去的十年里，我们见证了存储类似图形的数据库的进步，但在搜索它们方面并没有太大的进步。正如Surajit Chaudhuri(微软研究院的一位杰出科学家)在2015年ICDE的主旨演讲中所说的那样，对图形状数据库的搜索已经落后于对非结构化数据的搜索。在科学家和商业用户从他们的不同数据集中寻找令人兴奋的、可操作的发现的同时，提供有效的搜索的需求是深刻的。在这项拟议的研究中，我们专注于设计有效和高效的方法来探索图形数据库。我们解决了在图形状数据库上改进知识探索的重要问题、挑战和机会。这些问题的产生是由于这些数据的复杂性、规模性和海量异构性。首先，我们解决了使用关键字搜索范型在异构图上寻找相关答案的问题。实图(例如，社交网络)是异类的，并且对各种类型的实体和关系进行建模。在这些图中，每个节点都与与其语义相对应的重要性值相关联。以前的工作使用结构和基于内容的度量的组合来对答案进行排序，而忽略了节点的类型和重要性。通过考虑节点的重要性，我们提出了高效的算法来为给定的查询找到相关的答案。其次，基于一种称为两跳覆盖的图索引方法，我们设计了新的算法来回答加权图上的距离查询(即寻找任意结点对之间的最短距离)。我们研究了如何应用图分区来构建索引，以及如何在图数据流上高效地更新索引。第三，研究了在知识图中搜索时用户意图的识别问题。目前在这一领域的大部分工作只专注于快速找到答案，而不是寻找更有意义的答案。我们研究了寻找关键字的作用以提高搜索质量的问题。这项研究的结果将对加拿大和国际企业和政府机构有用。建议的框架可供金融(如TD银行和股票市场)、医疗保健、政府机构(如加拿大统计局)和技术公司(如IBM和微软)使用。我们的计划将培训数据库和数据挖掘领域的学生，使他们在申请学术和工业工作时处于有利地位。我预计将有多达12名学生(包括本科生)在这个项目中接受培训。

Much of the world's high-quality enterprise and social data are stored as semi-structured and structured data. This includes enterprises' RDBMSs, knowledge graphs, and social networks. All these data collections either are defined already as graphs or can be re-modeled as graphs. Over the past decade, we have witnessed advances in storing graph-like databases, but we have not seen much progress in search over them. As Surajit Chaudhuri (a distinguished scientist at Microsoft Research) addressed in his keynote talk at ICDE in 2015, search over graph-like databases has fallen behind search over unstructured data. While scientists and business users look for exciting, actionable discoveries from their heterogeneous datasets, the need to provide effective search is profound.In this proposed research, we focus on designing effective and efficient methods to explore graph databases. We address important problems, challenges and opportunities for improving knowledge exploration over graph-like databases. These issues arise due to the complexity, scale and massive heterogeneity of such data.First, we tackle the problem of finding relevant answers to search over heterogeneous graphs using the keyword search paradigm. Real graphs (e.g., social networks) are heterogeneous and model various types of entities and relationships. In these graphs, each node is associated with an importance value corresponding to its semantics. Previous work ranks answers using a combination of structural and content-based metrics, and ignore the type and importance of nodes. By incorporating the importance of nodes into account, we propose efficient algorithms to find relevant answers for the given query. Second, we design new algorithms to answer distance queries (i.e., finding shortest distance between any pair of nodes) over weighted graphs based on a graph indexing method called 2-hop cover. We investigate how graph partitioning can be applied to build the index and how to efficiently update the index over a stream of graph data. Third, we investigate the problem of identifying a user's intention when searching over knowledge graphs. Most of the current work in this area focuses only on finding answers quickly rather than finding more meaningful answers. We investigate the problem of finding a keyword's role to improve search quality.The results of this proposed research will be useful for Canadian and international businesses and government institutions. The proposed frameworks can be used by financial (e.g., TD Bank and stock market), healthcare, governmental institutions (e.g., Statistics Canada), and technological companies (e.g., IBM and Microsoft). Our program will train students in the databases and data mining area to place them in a strong position when applying for academic and industrial jobs. I expect up to twelve students (including undergraduate students) to be trained in this program.