一种高效有向无线充电器的布置算法

传统的传感器节点通常采用电池供电,有限的电池能量限制了传感器网络整体的寿命.无线能量传输技术可将能量以无线方式从充电器发送至传感器,从而可以彻底解决这一问题.无线可充电传感网中的一个重要问题是无线充电器的布置问题,即,如何有效地布置充电器,使得传感器网络的整体充电效用最大化.已有的工作主要考虑的是全向充电器的布置问题,且充电器可布置的位置受限,如只能布置在三角形顶点或网格中的格点处,因此具有相当的局限性.首次考虑了有向充电器的一般布置问题,即,充电器充电区域为扇形,并且充电器可布置在区域内任何位置处,其朝向可任意调节.另外,首次基于实测数据建立了有向充电器的充电模型,并提出一系列创新方法将问题进行转化,设计了一种近似比为(1-1/e)/(1+e)的高效算法——CDG(charger deployment-greedy)算法来解决这一问题.仿真实验结果说明了CDG算法的有效性.与其他提出的两种随机算法相比,CDG算法的性能分别提升了将近300%和100%.     

求凸多边形直径的改进算法

求凸多边形直径是计算几何中的一个基本问题,在Preparata-Shamos算法的基础上,提出了采用动态规划和二分查找的算法,不需要对凸多边形进行预处理,使整个算法的时间复杂度降低到O(n)级别。对算法实现的理论分析结果进行了验证,实验结果表明算法具有较高效率。     

过滤器数据结构研究综述

过滤器数据结构可以近似地判断某个元素是否属于给定集合。典型的过滤器数据结构，如布隆过滤器、布谷鸟过滤器、商过滤器，以牺牲查询准确性为代价换取更低的内存空间消耗和查询时间开销。因此，得益于空间时间高效性，过滤器数据结构现已被广泛应用于计算机网络、物联网、数据库系统、文件系统、生物信息学、机器学习等领域的近似成员资格查询操作中。自20世纪70年代以来，过滤器数据结构受到了广泛的研究，在诸多领域取得了重要的进展，其研究思路也在不断变化。文中整理了近五十年来关于过滤器数据结构的经典研究成果，从过滤器数据结构的原理出发对已有工作进行分类总结，并比较不同工作之间的引证关系和改进思路，最后讨论了过滤器数据结构的未来研究方向。     

学习型过滤器综述

作为一种高效的概率性结构，过滤器可以高效地解决近似集合成员查询问题。近年来，随着机器学习技术的发展，一些学习型过滤器表现出色，超越了传统的过滤器。这些学习型过滤器考虑数据分布信息，将集合成员查询问题视为二分类问题，实现了超越传统过滤器的性能。受此启发，学习型过滤器研究领域迅速发展，出现了多个变种。然而，目前还缺乏对近些年相关工作的系统性回顾和比较。为了填补上述空缺，文中全面回顾了近年来的学习型过滤器相关工作，并展望了未来的发展方向。     

跨语言用户态文件系统框架读写性能优化

以深度学习为代表的数据分析应用越来越多依赖分布式文件系统存储管理大规模数据集.为了增强数据访问的兼容性，现有分布式文件存储系统通常需提供标准POSIX接口，以支持深度学习等应用的无缝对接.然而，以内核模块形态开发提供POSIX接口的文件系统非常复杂耗时.近年来，用户态文件系统（Filesystem in Userspace,FUSE）框架大幅简化了文件系统的开发工作，已被Alluxio和Ceph等诸多知名分布式文件系统使用.目前常用的用户态FUSE库libfuse仅提供C语言编程接口，但现有大数据分布式文件系统基本都是基于Java语言开发的（例如HDFS和Alluxio等），为了使基于Java语言开发的分布式文件系统可以对接C语言开发的FUSE库，需采用跨语言FUSE框架作为中介.跨语言FUSE框架利用跨编程语言的函数回调机制，使操作系统FUSE库的C语言函数可以跨语言的调用分布式文件系统提供的Java语言编程接口，从而为大数据分布式文件系统提供标准POSIX接口的访问能力.但在数据密集型应用中，现有跨语言FUSE框架的执行效率低，导致数据密集型作业（深度学习、大数据分析等）中数据I/...     

基于边缘智能计算的城市交通感知数据自适应恢复

智能交通系统（intelligent transportation systems, ITSs）被广泛用于智慧城市中，却普遍存在感知数据缺失问题.而交通感知站点有限的存储计算能力严重制约感知数据的恢复，极大影响ITSs的正常使用.虽然可以利用边缘节点强大的存储计算能力解决这个困境，但边缘节点部署的高复杂性和感知数据时空相关性的高动态性对数据精确恢复提出挑战.为了解决上述挑战，提出基于边缘智能计算的城市交通感知数据自适应恢复系统.具体地，首先利用子模优化理论，提出具有理论下界的边缘节点次优部署分配算法.然后，基于低秩理论恢复感知数据，并基于恢复结果估计非缺失下限，通过反馈自适应调整感知站点的数据上传比例，从而保证数据精确恢复.最后，基于澳大利亚600个交通站点1年的感知数据构建原型系统，对所提算法进行评估.实验结果表明，所提算法的边缘节点部署性能达到最优性能的90%以上，缺失数据恢复精度比3种对比方法提高43.8%以上.同时，自适应数据恢复能够平均提高精度40.3%.