Efficient and Effective Search over Graph-like Databases

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