Scalable Querying and Mining of Graphs

可扩展的图查询和挖掘

• 批准号: 0612327
• 负责人: Ambuj Singh
• 金额: --
• 依托单位: University of California-Santa Barbara
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2006
• 资助国家: 美国
• 起止时间: 2006-07-15 至 2010-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0612327&HistoricalAwards=false
• 关键词: Scalable; Querying; Mining; Graphs

A number of scientific endeavors are generating data that can be modeled as graphs: high-throughput biological experiments on protein interactions, high-throughput screening of chemical compounds, social networks, ecological networks and food webs, database schemas and ontologies. Mining and analysis of these annotated and probabilistic graphs is crucial for advancing the state of scientific research, accurate modeling and analysis of existing systems, and engineering of new systems. The goal of this research project is to develop a set of scalable querying and mining tools for graph databases by integrating techniques from the fields of databases, bioinformatics, machine learning, and algorithms. New algorithms are being developed, and these are being examined for their quality and running time on real datasets. The first set of algorithms addresses subgraph and similarity querying in graph databases. The second set considers the mining of significant subgraphs or motifs. A novel significance model which transforms graphs into histograms of primitive components and examines the significance of motifs in the transformed domain is being developed. The third set of algorithms targets the discovery of well-connected clusters in large probabilistic graphs. The project integrates research and education by introducing the results of the research into undergraduate and graduate courses. Robust open-source tools based on the developed algorithms will be released for other researchers. These will be helpful in the study of the structure and organization of large networks that are becoming increasingly common.

许多科学努力正在生成可以建模为图表的数据：蛋白质相互作用的高通量生物实验、化合物的高通量筛选、社交网络、生态网络和食物网、数据库模式和本体。 挖掘和分析这些带注释的概率图对于推进科学研究水平、现有系统的精确建模和分析以及新系统的工程至关重要。 该研究项目的目标是通过集成数据库、生物信息学、机器学习和算法领域的技术，开发一套可扩展的图数据库查询和挖掘工具。新算法正在开发中，并且正在测试它们在真实数据集上的质量和运行时间。第一组算法解决图数据库中的子图和相似性查询。第二组考虑重要子图或主题的挖掘。正在开发一种新颖的显着性模型，该模型将图转换为原始成分的直方图，并检查转换域中主题的显着性。第三组算法的目标是发现大型概率图中连接良好的簇。该项目通过将研究成果引入本科生和研究生课程，将研究与教育融为一体。基于所开发算法的强大开源工具将为其他研究人员发布。 这些将有助于研究日益普遍的大型网络的结构和组织。