Grant: Discovery Grants Program - Individual
University of Victoria
$22,000.00
Information Extraction from Interconnected Data: An Algorithmic Study
FY 2012-13
Summary
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.
Program
Discovery Grants Program - Individual
Recipient
Location
British Columbia, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data
As published
Application id
283327-2012
Name nom
Srinivasan, Venkatesh
Department département
Computer Science
Organization id
7
Institution établissement
University of Victoria
Province en
British Columbia
Province fr
Colombie-Britannique
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2012
Competition year année de concours
2012
Award amount
22000
Program id
RGPIN
Program name en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
Discovery grants programs
Group fr
Programmes de subventions à la découverte
Committee code
1507
Committee name en
Computer Science
Committee name fr
Sciences informatiques
Area of application code
1200
Area of application group en
Advancement of knowledge
Area of application group fr
Avancement des connaissances
Area of application en
Advancement of knowledge
Area of application fr
Avancement des connaissances
Research subject code
2712
Research subject group en
Information technology
Research subject group fr
Technologie de l'information
Research subject en
Theory of computation
Research subject fr
Théorie de calcul
Partie
1
Nb partie
5
Application title
Information Extraction from Interconnected Data: An Algorithmic Study
Keyword
NSERC
Application summary
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.