反向Top-k查询算法和分布式应用研究

来源 :华中科技大学 | 被引量 : 0次 | 上传用户:tianshanfeiren
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
信息技术的快速发展带来了数据的爆炸式增长,而在海量数据中如何得到Top-k的结果已经成为了计算机领域研究的热点问题之一,经过多年的发展,Top-k查询技术已经相当成熟。但Top-k查询是从用户的角度出发,检索最符合其搜索条件的前k个结果,而本文则提出了反向Top-k查询,提供了另外一个视角,即站在商家的角度,如何判断某个产品在市场上的受欢迎程度,从而能够为产品生产商提供更大的收益,因此对于反向Top-k查询算法的研究具有重要的商业价值和研究意义。本文主要研究了反向Top-k查询算法,并在分布式的环境中对其进行改进。本文给出了反向Top-k查询的定义并介绍两种反向Top-k查询,即单色和双色反向Top-k查询。针对单色反向Top-k查询,本文从两个定理出发探究了二维空间中的反向Top-k算法,并拓展到k维空间中。而对于双色反向Top-k查询,本文则提出了反向Top-k阈值算法(TA),并给出了案例说明和优化方法。为了提高双色反向Top-k查询算法的运行效率,本文还提出了反向Top-k角列表的方法,该方法基于一种空间划分的索引结构。本文详细阐述了这一网格的构建方法,并给出了两种不同的递归终止策略,即空间限制策略以及代价保证策略,以适应不同的使用场景,同时分析了数据更新场景下的算法调整方式。当数据量增大到一定程度时,集中式算法的计算代价将过于高昂,从而导致处理时间过长,因此本文提出了在分布式场景下的反向Top-k查询算法,即DRT算法。其基本思路为Map Reduce,算法具体分为三个阶段,Map阶段,Shuffle阶段和Reduce阶段。同时,为了保证结果的正确性,本文对数据点和权重向量分别采用了相应的过滤手段,即基于支配关系的过滤和权重向量的过滤。本文分别采用真实和合成数据集对上述算法进行实验,测试了在不同数据分布、数据维度和数据集大小中算法的性能,实验结果验证了算法的有效性和效率。
其他文献
随着计算机科学、生物学、控制理论等学科的不断发展,脑机接口(Brainmachine Interface,BMI)在残障人士运动功能重建的临床应用中表现出巨大潜力。根据获取神经信号方式的不同,脑机接口可以分为非植入式脑机接口和植入式脑机接口(Intracortical Brain-machine Interface,i BMI)。本文的研究是基于植入式脑机接口进行的。植入式脑机接口通过在大脑皮层中
随着数字社会的发展,视频在日常生活中越来越常见,提取视频中的文字信息在自动导航、场景理解等多种应用场景下具有重要意义。视频文字识别系统可以看作是一个多目标跟踪系统,对于视频中的文字进行识别的子任务包括了:视频文字实例检测,由文字实例形成文字轨迹,由文字轨迹得到识别结果。视频与静态图像有很大不同,其主要表现在视频中的环境是不断变化的,其中的文字实例也是不断运动,导致了视频中常会出现运动模糊、光照变化
政府投资项目采用市场化代建模式进行建设已是较常见的一种模式,近几年在深圳被广泛应用,并取得明显成效。本文结合深圳市福田区典型大型市政项目—新洲红树碧道工程代建管理的实践,针对项目策划、报批报建管理、招投标和合同管理、施工项目管理等方面提出全过程代建管理的要点,希望以此促进政府投资类项目市场化代建发展。
合成孔径雷达(Synthetic Aperture Radar,SAR)是一种全天时全天候的高分辨成像雷达。SAR通过方位向的运动构建出等效的合成孔径天线,然后利用脉冲压缩技术,获取距离向和方位向的二维高分辨率图像,被广泛的应用在军事和民事等多种领域,是不可或缺的观测手段。在不同平台SAR系统的研究中,星载SAR由于不受领空主权的限制,受到了世界各国的重视,目前世界上的在轨星载雷达高达几十颗,高分
卫星激光通信相比于微波通信终端有着更小的体积、重量和功耗,并且具有通信容量大、频谱资源丰富、方向性好和保密性强的优点,可以很好地弥补微波通信的不足。目前激光通信中接收机一般需要将自由空间传输的信号光耦合进光纤后再借助成熟的光纤通信器件对信号进行处理以提升系统性能,但是受到大气湍流效应、光束发散角和平台振动的影响,卫星通信中信号光到单模光纤的耦合效率较低且难以保持稳定,这极大地限制了激光通信系统的性
随着电子消费的广泛普及,以高精度电子产品生产为代表的自动化装配技术得到了快速发展,传统的协同式机械臂受限于其重复定位和运动控制精度,想要达到精度要求往往成本高昂,面临着更换设备的代价。本文结合光学双目定位和六轴机械臂运动控制原理,设计并搭建了双目立体定位实验系统,并为该系统设计了一套完整的双目定位算法,包含了标定、坐标系校正、图像预处理和特征立体匹配等一系列流程。算法基于HALCON机器视觉软件,
金属玻璃也称非晶合金,其基本特征是原子排布长程无序,因而具有优异的物理、化学和力学性能。作为非平衡态的材料,弛豫是金属玻璃固有的特征,对金属玻璃弛豫动力学的研究有助于分析其结构,探索其应用。近年来,研究发现金属玻璃表面具有类液行为,表现出快速动力学。但是,受限于金属玻璃的微观结构难以表征,到目前为止,对于金属玻璃的表面特性,人们了解的还不够清楚。本文利用分子动力学模拟,对铜-锆金属玻璃体系在退火过
本文针对乡村住宅热工性能差、居住舒适度不佳的现状,以期改善村民的生活质量。选取鄂西南乡村住宅作为研究对象,并以居住热舒适性为切入点展开研究。在鄂西南地理气候条件的理论基础上,就该地区乡村住宅的现状进行了实地调研走访,采用现场实测和问卷调查相结合的方法,较为全面地分析了当地居民的居住热舒适状况。经调研统计分析可知,当地居民夏季热中性温度为25.3℃,80%居民可接受的温度区间为22.0~28.6℃;
超声因实时动态、无创安全等特点,广泛应用于临床医疗。通常,超声医疗的核心部件超声换能器是基于压电效应的电驱动器件,其存在易受电磁干扰的问题。基于光声效应的光致超声换能器因制备工艺简单、电磁兼容等特点逐渐引起人们关注,并具有在溶栓、神经刺激、药物递送等领域应用的潜力。因此,对光致超声换能器的研究具有重要意义。光致超声换能器的核心是由光吸收材料与热膨胀材料组成的光声复合材料,其中光吸收材料通过无辐射跃
光谱诊断可以提供如杂质种类、杂质密度、离子温度、电子温度、等离子体转动速度等参数,被广泛应用于高温等离子体中。对于华中科技大学场反位形(HFRC)装置,其等离子体中的杂质会影响其约束性能;等离子体漂移速度将决定融合等离子体参数;旋转离心力驱动的旋转模(n=2)则限制了FRC等离子体的寿命。为此,我们为HFRC装置设计搭建了光谱诊断系统,由一套全波段光谱仪及一套快速响应多普勒光谱系统组成,用于监测杂