基于频繁子图的图查询技术研究的任务书.docx

基于频繁子图的图查询技术研究的任务书
一、选题背景和意义
随着互联网大数据时代的到来，图数据越来越成为研究或应用的必要手段。表示网络、社交关系、物联网设备等很多实际应用的数据都可以被建模成图数据。在这些场景下需要对图数据进行复杂查询以获得信息，比如社交网络中，一个节点的某些特定属性组合的图模式可能预示着该用户的情感、兴趣或是行为等；在物联网中，若一个子图存在某种模式，则该子图就有可能是相似的设备。
因此，在图数据中，与节点，边单独查询不同的是子图查询，即查询包含某些顶点和边的子图。子图查询是图数据库和图计算库中一个重要问题。然而，当查询图查询中考虑子图时，由于子图的大小和复杂性，查询开销会更大，例如通过节点范围查询的基于索引的图查询很难应用于子图查询中。因此，子图查询是一项具有挑战性的任务，需要一种高效的查询策略和算法。
同时，频繁子图挖掘技术应用广泛，除了子图相似性查询，还广泛应用于图分类、图聚类、模式识别等领域。频繁子图指的是在一组图中，出现次数多于用户提供的阈值的所有子图，而频繁子图挖掘的任务就是从大量图数据中自动发现这些重要的频繁子图。频繁子图挖掘技术被广泛应用于生物信息学、社交网络分析、药物发现、化学等领域。
因此，在本课题中，我们将探索在图数据库中基于频繁子图挖掘技术的图查询技术，重点研究子图查询的查询策略和算法，并将其应用于实际场景中，如社交网络、物联网等领域。
二、研究目标和内容
1.研究基于频繁子图挖掘技术的图查询算法
通过频繁子图挖掘技术，自动发现重要的子图，该任务需要通过挖掘大规模图数据集，确定频繁子图和需要查询的子图之间的相似程度，并构建频繁子图数据库。
2.研究子图查询的高效算法
围绕图查询过程中的子图查询，研究高效的图查询算法，例如深度优先搜索、广度优先搜索、最短路径搜索等。具体包括提高查询性能、满足用户需求、处理大量数据和避免内存中的查询重复等方面的算法研究。
3.应用场景
社交网络中的话题热度趋势分析，通过查询包含某些人、议题之间的关系进行分析，可基于相应频繁子图快速筛选出聚类在一起的人群，提高人类社会热点趋势预测的准确性。以及电子商务中的推荐系统，同样可以使用子图频繁度来计算物品之间的相似度，从而实现更加精准的商品推荐。
三、研究方法和技术路线
1.理论分析
频繁子图挖掘算法的复杂度和正确性，偏序关系的度量，子图相似性的度量等。
2.算法设计
设计子图查询算法，考虑数据规模、传输效率和查询响应时间等因素，提出合理的查询策略；目前已有的一些优化算法也可以看作查询策略工具，值得借鉴。
3.系统实现
将设计好的算法实现到实际系统中，如社交网络中，通过访问固定的数据源，建立子图数据库和对应的查询文本，实现特定时间段、特定人和议题集内人、议题的子图查询，实现数据的可视化和趋势分析。
四、研究预期成果
1.在图数据库中研究基于频繁子图挖掘的图查询技术，并提供高效的查询策略和算法。
2.提出基于子图频繁度的社交网络话题热度分析方法，通过对网络中不同社交群体、话题之间关系的建立，快速筛选出人群并分析热度趋势，从而实现预测热点新闻、娱乐事件发展趋势等目标。
3.将算法和查询策略实现到系统中，并进行性能测试和应用场景测试。实现有界内存占用和应对超大规模数据的查询响应时间。
五、研究意义
1.提供基于子图频繁度的图查询技术，为社交网络、物联网等领域的图数据处理提供重要支持。
2.推动频繁子图挖掘技术的深入发展及其在不同领域的应用并促进其大规模使用。
3.为人类社会的致富奔小康，提供分析热点、跟踪热点、发现契机的重要支持和帮助。