Efficient and Effective Search over Graph-like Databases

世界上许多高质量的企业和社会数据都以半结构化和结构化数据的形式存储。这包括企业的rdbms、知识图和社会网络。所有这些数据集合要么已经定义为图形，要么可以重新建模为图形。在过去的十年里，我们见证了存储类图数据库的进步，但在搜索方面却没有太大的进步。正如微软研究院著名科学家苏拉吉特·乔杜里（Surajit Chaudhuri）在2015年ICDE的主题演讲中所说，对类图数据库的搜索已经落后于对非结构化数据的搜索。当科学家和商业用户从他们的异构数据集中寻找令人兴奋的、可操作的发现时，提供有效搜索的需求是深刻的。在本研究中，我们的重点是设计有效和高效的方法来探索图数据库。我们讨论了在类图数据库上改进知识探索的重要问题、挑战和机遇。这些问题的产生是由于这些数据的复杂性、规模和巨大的异质性。***首先，我们使用关键字搜索范式解决了在异构图上搜索找到相关答案的问题。真实的图（例如，社交网络）是异构的，并且建模各种类型的实体和关系。在这些图中，每个节点都与与其语义相对应的重要性值相关联。以前的工作使用结构和基于内容的指标组合对答案进行排名，而忽略了节点的类型和重要性。通过考虑节点的重要性，我们提出了针对给定查询找到相关答案的高效算法。其次，我们设计了新的算法来回答距离查询（即，在加权图上找到任何对节点之间的最短距离），该算法基于一种称为2跳覆盖的图索引方法。我们研究了如何应用图分区来构建索引，以及如何在图数据流上有效地更新索引。第三，我们研究了在搜索知识图时识别用户意图的问题。目前该领域的大部分工作只关注于快速找到答案，而不是找到更有意义的答案。我们研究了寻找关键字对提高搜索质量的作用。***这项拟议研究的结果将对加拿大和国际企业和政府机构有用。建议的框架可用于金融（例如道明银行和股票市场）、医疗保健、政府机构（例如加拿大统计局）和技术公司（例如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.