4734发表于 2020-01-02 09:11:56
只看该作者楼主

<分布式> 检索TopN 问题 [复制链接]

需求:

      1. 在信息检索时,可以检索出TopN 

      2. 信息分布在 m 台计算上,访问这些计算机只允许1次。每台计算机返回 y 条信息。

      3.  现在假设访问计算机中的x台, 

问题1: 满足什么条件,使得必然求出TopN 

问题2: 满足设么条件,求出TopN 的概率。

分析:

    1, 如果 x >= m,  y>= TopN,   必然能够获得 TopN.   返回的信息量为: TopN * m  

    2,   如果已知信息均匀分布, 则访问 x >= m ,   y >= TopN / m ,  也可以获取 TopN.    返回的信息量为:TopN 

    3,如果 N >>m , 每台计算机返回1条数据, 也同样概率的可以求出 TopN 


遗留问题:

     1,   如果要求只访问 x << m,   是否能够获取TopN ,  并求其概率

     2,如果信息不是均匀分布,而是其他分布,问题将会如何呢。

应用:

     1,数据被分布到地球各处, 只会有部分主机返回, 即:  x << m 

     2,  每台计算机数据上亿条,检索TopN  也是一个吃力的事情。即需要返回 信息总量与检索总量 都接近 TopN 

思路1:串行思路: 假设已知m, 

           1.1  先访问1台计算机,先获取 TopN,  然后终端获取 min(TopN ) 

           1.2  访问第二台计算机,要求返回 TopN >= min(TopN)

           1.3  依次下去, 当获得TopN 不在增长时, 认为满足,分析其概率

思路2: 随机决策。 自行分析。

发表于 2020-01-02 09:18:18
只看该作者沙发

干货干货,值得分享,赞

发表于 2020-01-02 09:53:07
只看该作者板凳

分析的蛮好的,点赞

发表于 2020-01-02 13:48:02
只看该作者地板

真心不错,期待其他文章哦

发表于 2020-01-02 16:30:41
只看该作者5 #

<分布式> 检索,讲的真心不错


您需要登录后才可以回帖

登录注册
发表回复