搜索表示与特定关键字相关的图形的算法

Question

我有一个图(它是一个图，因为一个节点可能有多个父节点)包含具有以下数据的节点:

• 关键字 ID
• 关键字标签
• 过去的搜索次数
• 关键词推广深度

相关性用从 1 开始的数字进行评分。
子节点的相关性由子节点与父节点的距离减去关键字的推广深度来确定。
相同深度的子节点的显示顺序由先前搜索的次数决定。
有没有算法可以搜索这样的数据结构？
如果我需要遍历所有节点、缓存生成的结果并按页面显示它们，考虑到这应该适合大量用户，我是否会遇到效率问题？如果我确实有问题，该如何解决？
我需要使用什么样的数据库？ NoSQL、关系数据库还是图形数据库？
该方案会是什么样子？
这可以使用 django-haystack 来完成吗？ ？

Answer 1

您似乎正在尝试计算图上的前 k 个查询。有多种算法适合解决这个问题，我相信最简单的算法会帮助您解决问题是 Threshold Algorithm (TA) ，当以 BFS 方式遍历图形时。其他一些top-k算法是Lawler-Murty Procedure ，以及其他 TA 变体。

关于效率——计算查询本身的问题可能有一个指数级的时间，这仅仅是由于要返回的结果的指数级数量，但是当使用 TA 时，输出结果之间的时间应该相对较短。就涉及的缓存和规模而言，通常的注意事项适用 - 当规模和适当的 TA 版本(例如 Threshold Join Algorithm )获得时，您可能希望使用分布式系统。当然，在选择要使用的数据库解决方案时，您还需要考虑缩放和缓存问题。

就数据库而言，您绝对应该使用支持图形作为一等公民的数据库(通常称为 Graph Databases )，我相信图形数据库背后的存储引擎是否是无关紧要的相对或 NoSQL。需要注意的一点是，您可能希望确保您选择的数据库可以扩展到您需要的规模(因此对于大规模，您可能需要研究更多的分布式解决方案)。模式将取决于您选择的数据库(假设它不是无模式数据库)。

最后但同样重要的是 - 干草堆。由于 haystack 可以处理您选择使用的搜索引擎可以处理的所有内容，因此应该至少有一种可能的方法(将 Apache Solr 用于搜索，将 Neo4j 或 GoldenOrb 用于数据库)，以及可能更多(因为我不太熟悉 Haystack 或它支持的搜索引擎，除了 Solr)。