对于搜索引擎来说,索引存放在成千上万台机器上,如何进行分布式搜索呢?
假设搜索结果是以分页的方式显示,以PageNumber代表当前页,从1开始,以PageSize代表页面大小,默认为10,以N代表搜索服务器数量。最简单的分布式搜索算法为:有一台合并服务器负责接受用户的搜索请求,然后分别向N台机器获取前PageNumber*PageSize条结果,得到的结果数为N*PageNumber*PageSize,然后把这些数据重新进行排序,根据所要显示的页面PageNumber,获取从(PageNumber - 1) * PageSize + 1开始的PageSize条结果返回给用户。
这个算法很简单,但有一些问题:
问题一:每次翻页都要向每台搜索服务器搜索一遍
通常情况下,用户在搜索内容时都是顺序翻页的,即从第一页往下顺序翻,这个算法没有设计缓存来减轻搜索服务器的压力。
问题二:越往后翻页,搜索服务器的搜索压力越大
如果我们是查第100页,即第991-1000 条记录,那么这个算法需要从N台搜索服务器分别获取1000条记录才能完成,对于每台搜索服务器的搜索压力很大。
问题三:越往后翻页,合并服务器的排序压力越大
大型搜索引擎往往是由成千上万台机器组成的分布式搜索集群,如果按这个算法来进行翻页,假设N为1000,查询第100页时,合并服务器得到的结果数为N*PageNumber*PageSize = 1000 * 100 * 10 = 1000000,要对这100万条结果进行排序,对合并服务器来说压力很大。对系统的可伸缩性是一种极大的破坏。
相关推荐
#资源达人分享计划#
本书对分布式算法进行全面介绍,包括最为重要的算法和不可能性结果。绝大部分的解都给出了数学证明。这些算法都根据精确定义的复杂度衡量方法进行分析。本书还讲述针对许多典型问题的算法、各类系统模型及其能力。...
针对传统无线传感器网络部署方法存在节点冗余率高、覆盖率低等问题,以网络覆盖率为优化目标,将烟花算法良好的结果搜索能力与分布式高效的计算速度相结合,实现对网络覆盖率优化模型的高效求解。实验表明,该算法...
针对水下传感器网络能量消耗大、延迟时间长、信道利用率低等问题,提出了一种带选择适应性的水下传感器网络分布式路由算法(AS-UWSN)。AS-UWSN使数据包成为一种具有以最大阈值为能耗界限的选择性和具有以最大信息素...
本文重点阐述了通信数据分布式存储与查询在Hadoop ...在数据查询过程中,还将数据遍历过程放Reduce函数中,从而使广度优先搜索算法的层次遍历过程也能够并行运行。这在很大程度上优化了数据查询和分层扩展的效率
基于这种证书图,给出了针对SDSI名字证书的分布式搜索算法,并证明其可靠性和完备性,表明当证书适当存储时,该算法能搜索和找到相关证书并形成证书链。与现有的自下至上的证书搜索算法相比,该算法更好地适应了SDSI...
针对合同网下的多agent系统,基于集合覆盖理论提出了一种解决子任务分配的严格启发式搜索算法;并分析了该算法的收敛性及渐进时间复杂度;证明了其搜索结果的上确界。该算法具有分布性,搜索空间缩减快,适合于中小型的...
本算法在传统蚁群算法的基础上,为提高算法精度,改进了状态转移规则,结合了邻域搜索算法;为提高算法速度,将本算法设计为分布式结构,利用多分布式agent系统实现了分布式求解VRPTW问题。针对国际标准算例设计了四...
分布式信息检索是信息检索领域的重要研究内容。为了提高分布式信息检索的性能,提出了一种基于文档副本局部性的分布式检索方法。对于任一站点,如果将查询结果中的非本地文档建立本地副本,那么可以减少查询处理中...
已有的求解最优联盟结构...该算法的特色是在局部最优假设下,通过局部信息的指导,n个Agent在深度方向上自顶向下对联盟结构图的并行搜索,从而达到缩短搜索时间,降低搜索复杂度的目的,该算法的时间复杂度为O(n2)。
M.Dorigo等人于1991年首先提出了蚁群算法。其主要特点就是:通过正反馈、分布式协作来寻找最优路径。这是一种基于种群寻优的启发式搜索算法
然后基于主网、区域管理(包括外层管理智能体和内层管理智能体)两级多智能体结构,利用改进迭代投影搜索法构建分布式潮流内外层双重迭代算法,以实现多区域间通信少量非重要信息,各区域内指数快速收敛的目标。...
然后,改进基本人工蜂群算法以使其适用于求解分布式柔性作业车间调度问题,具体的改进包括设计一种包含三维向量的编码方案,结合问题特点针对性地设计多种策略用于种群初始化,在雇佣蜂改良搜索操作中设计多种有效的进化...
主要进行干扰对齐算法中MINIL算法的仿真,求出收敛的U、V矩阵,使干扰对齐能够收敛
在对Map/Reduce算法进行分析的基础上,利用开源Hadoop软件设计出高容错高性能的分布式搜索引擎,以面对搜索引擎对海量数据的处理和存储问题
该技术充分利用遗传算法,采用启发式方法建立无线链路信道信噪比预测模型,然后根据信道质量选择最优者作为协作节点,以较小代价在动态无线网络拓扑中搜寻到最优路由。数学分析表明,遗传算法收敛速度快、可靠性高,...
提出了一个从同构数据集中学习贝叶斯网络结构的分布式算法。该算法首先使用搜索评分的方法学习每个局部贝叶斯网络结构,然后取节点对互信息变量和条件互信息变量的数学期望作为全局学习的评价标准,融合所有局部结构...
分布式遗传算法(DGA)是MATLAB脚本,其中包含搜索最佳/次优单极性二进制代码序列(以下称为遗传优化代码(GO-code))所需的所有功能,旨在提供最大可能的编码增益。 在此脚本中,一组输入参数是可调的,其中能量...
提出一种基于边框定界的WSN分布式全搜索定位算法。该算法通过节点测距得到邻居节点的坐标和距离信息,然后通过边框定界方法确定节点存在的位置区域,最后将位置区域网格化,并用全搜索方法在该区域搜索最佳估计点,...
计及重要负荷和负荷频率特性的分布式发电孤岛搜索算法,徐强,陈中,根据辐射状配电网的结构和故障恢复的特点,提出了一种计及负荷频率特性并且优先保证重要负荷供电持续供电的分布式发电孤岛搜索算