Information Extraction from Interconnected Data: An Algorithmic Study

点击翻译按钮获取中文摘要

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.