Information Extraction from Interconnected Data: An Algorithmic Study

当今世界的数据非常复杂。它起源于各种来源，如网络和社交网络。它结构灵活，高度动态。以前处理存储为表的数据的方法不再适用。迫切需要开发从这种形式的数据中提取信息的新方法。这里提出的研究将集中在从这些数据中提取信息的重要方面，这些数据对公共卫生（用于研究疾病模式）和公共政策（用于防止错误信息的传播）等领域都有好处。 具有部分结构的动态数据的自然表示是图形数据，其中节点表示实体，链接表示它们之间的已知关系。这种数据的一个例子是社交网络，其中节点对应于人，链接对应于友谊。处理这些数据的重要问题是大小、不完整性和隐私。由于这些数据集是巨大的，并且通常存储在外部设备上，我们是否可以设计算法来计算重要的属性，而只需使用少量内存对数据进行几次遍历？如果我们从不同的数据源中得到许多部分信息，是否有可能找到一种快速的方法来整合它们，以回答特定的查询？ 为了确保在发布这些数据之前满足某些隐私要求，巧妙地扰乱图数据有多容易？我们的研究将使用算法设计和分析，计算复杂性和密码学领域的工具和技术来解决这些基本问题。 这项研究计划的影响将是双重的：（1）它将为信息提取问题的研究提供坚实的基础，并开发具有明确性能保证的新的快速算法;（2）它将通过培训HQP在关键领域的国际经验和技能组合为先进技术产业做出贡献。分析复杂的数据并将其转化为知识带来了许多挑战;在加拿大拥有应对这些挑战的专业知识和工具将是对加拿大社会的宝贵贡献。

Data in today's world is highly complex. It originates from a variety of sources, such as the web and social networks. It is diversely structured and highly dynamic. Previous methods for dealing with data stored as tables no longer apply. There is an urgent need to develop new methods of extracting information from this form of data. The research proposed here will focus on important aspects of information extraction from such data with benefits to areas such as public health (for studying disease patterns) and public policy (for preventing the spread of misinformation). A natural representation for dynamic data with partial structure is graph data where the nodes represent entities and links represent known relationships between them. An example of such data is a social network in which nodes correspond to people and links correspond to friendships. Important issues while dealing with this data are size, incompleteness and privacy. As these datasets are massive and are often stored on external devices, can we design algorithms for computing important properties with only a few passes over the data using small amount of memory? If we are given many pieces of partial information from a variety of data sources, is it possible to find a quick way to integrate them so as to answer a particular query? How easy is it to perturb graph data cleverly in order to ensure that certain privacy requirements are satisfied before such data is released? Our research will tackle such fundamental questions using tools and techniques from the areas of algorithm design and analysis, computational complexity and cryptography. The impact of this research program will be two-fold: (1) It will provide strong foundations to the study of problems in information extraction and develop new, fast algorithms with clear performance guarantees; (2) It will contribute to advanced technology industry by training HQP with international experience and skill sets in a critical area. Analyzing complex data for converting it into knowledge presents many challenges; having expertise and tools in Canada to meet these challenges will be an invaluable contribution to Canadian society.