反向Top—k查询算法研究

龙源期刊网—k查询算法研究作者：黄伟国来源：《软件导刊》2017年第09期摘要：互联网中沉淀了大量可分析利用的数据，如何有效地利用这些海量数据，为不同行业产品制造方提供对新产品的分析，已成为时下的热点。反向Top-k查询技术是一种常用的数据分析及处理技术，并且已经在很多领域得到了应用。研究了已有的基于反向Top-k的查询算法Skyband-based算法和Branch-and-bound算法，针对很多实际应用领域偏好权重向量会出现改变的情况，提出了一种适用于进行“二次计算”的交互式算法，通过实验将交互式算法跟效率高的Branch-and-bound算法对比得出，当用户修改部分偏好权重向量之后，利用交互式算法可以比Branch-and-bound算法更加高效率地计算出结果。关键词：交互式算法；Skyband-based算法；Branch-and-Bound算法；Top-k查询DOI：10.11907/rjdk.172266中图分类号：TP312文献标识码：A文章编号：1672-7800（2017）009-0075-04Abstract：AmongtheInternet，alargeamountofdatacanbeanalyzedandutilized.Howtoeffectivelyusethesevastamountsofdata，fordifferentindustries，manufacturersofproductstoprovidenewproductanalysis，hasbecomeahottopic.ReverseTop-kquerytechnologyisacommonlyuseddataanalysisandprocessingtechnology，andhasbeenappliedinmanyfields.StudyoftheexistingreverseTop-kqueryalgorithmSkyband-basedalgorithmandBranch-and-boundalgorithmbasedonthepreferenceweightvectorinmanypracticalapplicationswillappeartochangethesituation，amethodispresentedforthe“two”interactivealgorithmbyexperimentthatcomparedtoBranch-and-boundalgorithm，interactivealgorithmwithhighefficiency，whenpartoftheusertomodifythepreferenceweightvectoriscalculatedbytheinteractivemethodcanbemoreefficientthanBranch-and-boundalgorithmresults.KeyWords：interactivealgorithm；skyband-basedalgorithm；branch-and-boundalgorithm；Top-kqueries0引言Top-k查询作为一种高效的信息对比查询技术，经过多年的发展，已经较为成熟。本文研究的基于Top-k查询的反向Top-k查询技术，能够提供与Top-k不同的查询角度。反向Top-k查询算法可以为各行业提供“影响值”最大的产品参考。产品制造方通过参考这些“影响值”最大的产品，可以制造出更受大众欢迎的产品，从而为产品制造方带来更多利益。1国内外研究现状龙源期刊网查询[1]是指基于用户的偏好函数从所有产品集中提取优先的k个产品集。比如，知道一个用户的偏好权重向量，然后用Top-k查询来查找该用户喜欢的k个产品。反向Top-k查询[2]是指基于用户根据他们的偏好认为某个产品作为他们的Top-k个产品中的一个来评估一个潜在的产品在市场上的影响。但是根据反向Top-k查询去找出m个最有影响的产品所耗的时间特别多，因为它需要对数据库中的每个产品进行反向Top-k查询。因此，本文使用文献[3]中提到的两个可以提高计算效率的算法。同时，充分考虑现实中的一些情况，也即针对用户偏好权重发生改变的情况，提出一种交互式算法，用来进行“二次计算”，以提升“二次计算”效率。最近，研究产品制造方而不是用户方的一些创新查询算法被提出。文献[4]基于支配关系的分析，帮助制造商完成它们的产品市场定位。文献[5]中提到了如何创建有竞争力的产品。然而在这两种方法中，都是将用户偏好作为数据点代表更好的产品，而反向Top-k查询是根据权重向量分析出用户偏好。文献[6]中提到如何为一个对象的推广寻找Top-k个最有兴趣的区域。文献[7]中给出一个查询点q，反向最近邻查询是基于一个相似的函数，找出那些与q最近邻的点，这些点描述成被q影响。2反向Top-k查询算法一种找出前m个影响值最大的结果集的朴素方式是用暴力计算方法计算结果集。如对于每一个点p属于数据向量集合S都进行反向Top-k查询从而得到它的影响分数fki（p）。但是其效率非常低下，即使是一个中等大小的数据库，也要消耗很多时间。因此，下文主要介绍文献[3]和文献[8-9]中可以提高计算效率的算法，分别是Skyband-based算法[10]、Branch-and-Bound算法。2.1Skyband-based算法Skyband-based算法依赖于ComputeSkyband算法和RTA算法，用ComputeSkyband选出点集mSB，这样就减少了计算RTA的点，从而提升了计算效率。因此，本文首先介绍ComputeSkyband算法和RTA算法。2.1.1ComputeSkyband算法算法思想：计算电影集S中每部电影被支配的数量，如果被支配的数量小于m，则将这部电影插入到mSB集合中，否则不进行操作。2.1.2RTA算法作为一种计算向量的反向Top-k集合的算法，RTA算法能够避免一些重复计算，从而更快速地给出结果集合[11-12]。该算法的思想是：考虑在整个计算中用户权重值W的数量较多，如果用W中的每一个权重去和特定的点计算，那么计算量无疑很大，因此用RTA通过已经计算过的Top-k结果集，龙源期刊网向量值，从而能够避免一些对结果没有影响的计算过程，进而提高算法效率。2.1.3Skyband-based算法Skyband-based算法简称SB算法。算法基本思想：先利用ComputeSkyband算法计算出mSB（S）点集，然后利用RTA算法计算mSB（S）中的所有点集的影响值。在计算点的影响值时，把影响值压缩进一个从大到小的队列Q中。当mSB（S）中所有点集的影响值计算完后，取出Q中前m个点，这m个点就是SB算法计算出来的结果集。2.2Branch-and-bound算法上文介绍的Skyband-based算法不是渐增性的，导致当需要扩大或者缩小算法的m值时，该算法不能够利用上一次的计算结果，而是需要完全重新计算，即Skyband-based算法不是渐进的。与此相对，本节提出的Branch-and-bound算法是渐增性的，当需要获得更多的结果值时，即当扩大m值时，并不需要进行全盘的重新计算，只是进行递增计算即可。因此，面对需要经常修改m值的情况，该算法的效率会更高，能够在更短的时间内给出计算结果。Branch-and-bound算法依赖ComputeBound函数和RTA算法。RTA算法在上文已介绍过，因此，下文主要介绍ComputeBound函数。2.2.1ComputeBound函数ComputeBound函数的基本思想：输入一个点q，计算出一个点q的影响值，然后计算出所有点q的影响值集中的反向Top-k值，并且求交集，得到的交集个数就是影响值的上界。2.2.2Branch-and-bound算法Branch-and-bound算法的基本思想是：先将电影数据集S存放在R树中，之后把R树根节点上的MBR加载到从大到小的优先队列Q中；然后用ComputeBound函数改进每个MBR的上界，并用RTA算法计算出实际影响值。Branch-and-bound算法详细描述如下：首先将电影评分数据S集加载到R树上得到一棵树tree；然后计算tree根节点的所有子节点的上界值，并插入到优先队列Q中；接着，做一个循环，当结果集RES的数量小于m时循环一直执行。从Q中推出一个MBR为c，判断c是否为电影数据点。如果c是电影数据点，而且已经计算了它的影响值，则添加到结果集RES中；否则计算它的上界，如果上界变小了，则再次插入到Q中，否则用RTA计算其影响值然后插入Q中。如果c不是产品数据点，则计算它的上界值，如果上界值没有变小，则重新插入到Q中；否则把c的子节点及其相应的上界值插入到Q中。3交互式算法龙源期刊网本文算法在计算过程中有大量用户偏好权重向量，算法计算得到的结果集跟用户偏好权重向量有关。本文所介绍的Skyband-based算法和Branch-and-bound算法都是批量式的查询，因此每次计算都需要将所有数据计算一次。而当部分用户偏好权重向量被修改后，不需要重新计算所有数据而得到结果集。可以利用第一次计算得到的结果，然后使用增量式的方法进行查询，即可得到最新的查询结果集。鉴于此，本文提出交互式算法，也即当部分用户偏好权重向量改变时，可以用交互式算法快速计算出结果集。3.1Top-k集比较算法因下文介绍的交互式算法需要用到Top-k集比较算法，因此先介绍Top-k集比较算法。为了在后面的算法过程中描述得更加清楚，在对算法作进一步介绍前，先对交互式算法中用到的一些变量进行定义。变量定义如表1中所示。Top-k集比较算法的基本思想描述如下：如果一个用户偏好权重向量w的OldTop-k集中的MtimeId和NewTop-k中的MtimeId相同，则不作任何处理。如果一个MtimeId在OldTop-k集中存在，而在NewTop-k集中不存在，就把OldS中对应MtimeId的电影的影响值减去w的权值；如果一个MtimeId在NewTop-k中存在，而在OldTop-k集中不存在，那么就把OldS中对应的MtimeId的电影的影响值加上w的权值。3.2交互式算法介绍针对改变的用户偏好权重向量作增量式查询，为了能够让交互式算法对已有的结果做增量式查询，要在第一次计算时进行一些处理，也即在用Skyband-based算法和Branch-and-bound算法进行结果查询之后，将查询出来的每个产品的影响值写入到存有产品集的文件中，然后针对每个改变的用户偏好权重向量进行计算。交互式算法的基本思想是：在用户修改用户权重向量之后，系统管理员不定时地将改变的用户权重向量从Mysql数据库中导出到本地，得到新的用户偏好权重向量NewW，并根据得到的NewW读取文件中的OldW，调用Top-k算法分别计算OldW集中的每个用户偏好权重向量的Top-k集称之为OldWTop-k集，NewW集中的每个用户偏好权重向量的Top-k集称之为NewWTop-k集。对OldWTop-k集和NewWTop-k集中的每个OldTop-k集和NewTop-k集都调用Top-k集比较算法，得到新的电影集NewS。最后将用户偏好权重向量中的OldW修改为NewW并存于文件中，以保持数据库中用户偏好权重向量和文件中用户偏好权重向量的一致性。将计算得到的NewS存于文件中，以记录最新电影的影响值。4反向Top-k查询算法性能比较4.1实验数据获取及预处理龙源期刊网实验数据获取包括两部分：一部分是电影数据获取[13-15]，网络爬虫爬