1

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

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

相关度以从1开始的数字进行评级。
子节点的相关度由子节点到父节点的距离减去关键字的推广深度来确定。
同一深度的子节点的显示顺序由前次搜索次数决定。
是否有能够搜索这种数据结构的算法?
如果我需要遍历所有节点,缓存生成的结果并按页面显示它们,考虑到这应该适用于大量用户,我是否会遇到效率问题?如果我确实有问题,该如何解决?
我需要使用什么样的数据库?NoSQL、关系型数据库还是图形数据库?
该计划会是什么样子?
这可以使用django 干草堆

4

1 回答 1

3

您似乎正在尝试在图表上计算前 k 个查询。有多种算法可以解决这个问题,我相信最简单的一个可以帮助您解决问题的是阈值算法 (TA),当以 BFS 方式完成对图的遍历时。其他一些 top-k 算法是Lawler-Murty 过程,并且存在其他 TA 变体。

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

就数据库而言,您绝对应该使用支持图形作为一等公民的数据库(那些往往被称为图形数据库),我相信图形数据库背后的存储引擎是相对的还是 NoSQL 并不重要。需要注意的一点是,您可能希望确保您选择的数据库可以扩展到您需要的规模(因此对于大规模,您可能需要研究更分布式的解决方案)。架构将取决于您将选择的数据库(假设它不是无架构数据库)。

最后但并非最不重要的 - 干草堆。由于 haystack 将适用于您选择使用的搜索引擎的所有内容,因此应该至少有一种可能的方法来做到这一点(将Apache Solr用于搜索,将Neo4jGoldenOrb用于数据库),也许更多(正如我'我不太熟悉 Haystack 或它支持的 Solr 以外的搜索引擎)。

于 2011-06-17T08:53:58.323 回答