图片丢失啦 数据库技术

默认 最新文章 浏览次数
Please wait a minute...
选择: 显示/隐藏图片
1. 时间依赖路网上的移动对象K近邻查询算法
张彤,秦小麟
计算机科学    2020, 47 (1): 79-86.   DOI: 10.11896/jsjkx.181102231
摘要561)      PDF(pc) (2656KB)(966)    收藏
随着基于位置服务的广泛应用,时间依赖路网上的对象查询逐渐成为研究热点。以往研究大多只针对时间依赖路网上的静态对象(如加油站、餐厅等),未考虑到移动对象(如出租车)的情况,而移动对象的查询在日常生活中有着非常广泛的应用场景。因此,文中提出了一种针对时间依赖路网上的移动对象K近邻查询算法TD-MOKNN,该算法分为预处理阶段和查询阶段。在预处理阶段,通过建立路网和网格索引,提出了一种新的移动对象到路网的映射方法,解除了以往研究假设移动对象恰好在路网顶点上的限制;在查询阶段,采用启发式搜索,借助倒排网格索引计算了一种新的高效启发值,通过预处理信息和启发值设计了高效K近邻查询算法,并给出了算法的正确性证明和时间复杂度分析。实验验证了所提算法的有效性,相比现有算法,TD-MOKNN算法在遍历顶点数和响应时间上分别减少了55.91%和54.57%,查询效率平均提升了55.2%。
参考文献 | 相关文章 | 多维度评价
2. 基于列存储的大数据采样查询处理
齐文, 鲍玉斌, 宋杰
计算机科学    2019, 46 (12): 13-19.   DOI: 10.11896/jsjkx.190500155
摘要468)      PDF(pc) (2881KB)(1126)    收藏
大数据时代的到来给传统的数据查询带来了性能挑战,即使查询算法有着O(n)的线性复杂度,但当n极大时其时间开销也难以满足用户需求。在很多实际应用中,人们并不需要精确的查询结果,但要求在给定时间内完成查询,因此可适当牺牲查询精度以满足性能约束。采样查询通过约简查询范围来提高查询性能,现有的采样方法多针对特定的算法和特定的应用场景,缺乏大数据环境下一般性的采样查询方法以及保证性能和精度的研究。文中研究大数据环境下列存储的采样查询处理,从数据划分和数据采样两方面改进大数据的查询效率。提出了基于加速比和势分布的采样方法,其支持各类采样算法,实现了分布式环境下采样查询的随机性保证、性能保证和近似性评价,并兼容了精确查询。该方法可以快速应用到已有大量数据的列存储中,具备良好的扩展性和可维护性。以Top-K为查询用例的实验结果证明,在不同数据量、不同数据分布和不同采样算法下,实际采样率与给定采样率的误差低于2%,查询准确度 (Accuracy) 稳定,方差在0.10和0.12之间,因此提出的基于段势的数据划分的采样效率高于平均划分和线性划分。
参考文献 | 相关文章 | 多维度评价
3. 基于哈希算法的异构多模态数据检索研究
陈凤, 蒙祖强
计算机科学    2019, 46 (10): 49-54.   DOI: 10.11896/jsjkx.190100139
摘要552)      PDF(pc) (2090KB)(1054)    收藏
随着大数据时代的发展,网络上的文本、图像、视频、音频等异构多模态数据呈指数级增长。在海量数据中进行异构多模态数据的检索,成为了热门的研究方向。但是,异构多模态数据检索面临两大挑战:1)数据存在“语义鸿沟”,即如何表达异构多模态数据之间的相似性;2)在海量数据中,如何进行准确高效的检索。针对哈希检索算法忽略了异构多模态数据之间语义一致性的问题,文中提出了一种基于CCA(典型相关性分析)语义一致性的哈希检索算法(CCA-SCH)。该算法为了保持模态内的语义一致性,分别生成文本和图像数据的语义模型;为了保持模态间的语义一致性,通过CCA算法融合文本和图像语义,生成最大相关矩阵;同时引入2,ρ范式来减少原始数据集的噪声和冗余信息,使哈希函数具有更好的鲁棒性。实验结果表明,CCA-SCH算法在实验数据集上的均值平均准确率(Map)相较于基准算法提升了10%以上,体现了该算法更好的检索性能。
参考文献 | 相关文章 | 多维度评价
4. 基于NVM的无日志哈希表
王涛, 梁潇, 吴倩倩, 王彭, 曹伟, 孙建伶
计算机科学    2019, 46 (9): 66-72.   DOI: 10.11896/j.issn.1002-137X.2019.09.008
摘要443)      PDF(pc) (2092KB)(951)    收藏
新兴的非易失内存正逐步进入人们的视野。由于这类存储技术同时具备了低延迟、持久化、大容量和字节可寻址的特性,数据库系统可以运行在只有NVM的存储架构上。在这种环境下,一些新颖的无日志索引结构应运而生,并被期望在异常故障后能即时地恢复索引能力而无须重建索引。然而,在现有的计算机体系结构中,这些索引结构为了确保NVM上数据的一致性,需要进行大量的同步操作,从而严重影响了正常执行时的系统性能。基于NVM的无日志哈希表利用指针数据的原子修改确保数据结构的一致性。哈希表使用了一种优化的Rehash方法,既减少了正常工作时的同步操作,又确保了异常故障后的即时恢复能力。实验评估表明,相比于已有的持久化索引结构,无日志哈希表在大部分工作负荷下的吞吐率表现良好,而在恢复时间、NVM资源使用量和写磨损方面具备显著的优势。
参考文献 | 相关文章 | 多维度评价
5. 基于道路网的多移动用户动态Skyline查询
周剑刚, 秦小麟, 张珂珩, 许建秋
计算机科学    2019, 46 (9): 73-78.   DOI: 10.11896/j.issn.1002-137X.2019.09.009
摘要351)      PDF(pc) (2338KB)(945)    收藏
随着无线通信和定位技术的发展,道路网Skyline查询在基于位置的服务等方面越来越重要。但现有的道路网Skyline研究所涉及的空间属性仅考虑距离,并未考虑多个移动用户位置和速度的变化对用户运动时间的影响,当用户运动状态发生变化时,需要动态地调整Skyline结果,进行重新规划。文中分析了用户运动状态与查询间的关联关系,提出了查询处理算法EI,将查询过程分为两步:1)根据时间,通过协同过滤扩展方法确定初始Skyline结果集,并对数据集进行剪枝;2)监测用户的运动状态,一旦用户速度发生变化,就快速根据出入点信息动态调整Skyline集。最后,在真实路网上对算法进行了实验,并将其与现有算法N3S和EDC进行了比较,结果表明EI算法可以高效解决基于道路网的多移动用户动态Skyline查询问题。
参考文献 | 相关文章 | 多维度评价
6. 基于两类寄存器互为缓存方法的DSP寄存器分配溢出处理优化算法
邱亚琼, 胡勇华, 李阳, 唐镇, 石林
计算机科学    2019, 46 (6): 196-200.   DOI: 10.11896/j.issn.1002-137X.2019.06.029
摘要358)      PDF(pc) (1380KB)(774)    收藏
寄存器是处理器硬件中有限的宝贵资源,这使得寄存器分配成为编译器中最为关键的过程之一。影响寄存器分配效果的关键因素之一是溢出带来的访存开销。针对DSP处理器具有两类通用寄存器的情况,以图着色全局寄存器分配方法为基本方法,提出两类寄存器间的一种互补利用策略和相应的寄存器溢出优化算法。该策略改进了传统图着色方法,通过生命周期分析的结果,将同类寄存器分配候选者之间的冲突关系和不同类寄存器分配候选者之间的冲突关系区分开来,并把它们表示在一张无向图中。与传统的图着色算法相比,改进的算法能充分考虑不同类寄存器之间的相互约束关系,减少寄存器溢出时的访存操作,从而有利于提高代码的性能。
参考文献 | 相关文章 | 多维度评价
7. 基于SVM访问预测机制的Web缓存数据库级替换策略
杨瑞君, 祝可, 程燕
计算机科学    2019, 46 (6): 201-205.   DOI: 10.11896/j.issn.1002-137X.2019.06.030
摘要398)      PDF(pc) (1616KB)(928)    收藏
Web缓存用于解决网络访问延迟和网络拥塞问题,缓存替换策略直接影响缓存的命中率。为此,文中提出一种基于访问预测机制的Web缓存替换策略。首先,根据用户之前的访问日志,通过预处理操作提取多项特征以构建特征数据集。然后,通过训练支持向量机(SVM)分类器来预测缓存对象是否可能被再次访问,将分类为不会再次被访问的缓存对象删除以腾出空间。仿真结果表明,与传统的LRU,LFU和GDSF方案相比,提出的策略具有较高的请求命中率和字节命中率。
参考文献 | 相关文章 | 多维度评价
8. 基于RDD非序列化本地存储的Spark存储性能优化
赵俊先, 喻剑
计算机科学    2019, 46 (5): 143-149.   DOI: 10.11896/j.issn.1002-137X.2019.05.022
摘要370)      PDF(pc) (1501KB)(924)    收藏
Spark框架被越来越多的企业用作大数据的计算框架,但随着现有服务器的可用内存资源增加,Spark并不能与新环境相匹配。Spark运行在Java虚拟机上,随着堆空间内存被大量使用,Java虚拟机通过回收内存来为新对象提供空间(垃圾回收机制,GC)的时间开销占Spark作业总耗时的比例显著增加,但Spark作业的效率并未随着可用内存的增加而保持一定比例的提升。在使用非堆(本地)内存存储模式后,GC开销问题得以缓解,但缓存数据的序列化开销成为新的矛盾点。文中利用本地存储方式解决GC问题,同时通过减少序列化开销以加快作业速度,提出并修改了Spark的存储结构,改进了RDD的淘汰机制和缓存方式,将去序列化的数据引入到本地内存中,在保持较低的垃圾回收开销的同时,降低了序列化的开销。实验结果表明,与原Spark的堆上存储方式相比,非序列化的本地存储方法在单结点、大内存的服务器上的GC时间缩短到5%~30%,同时,序列化开销显著降低,吞吐量得到提升,作业耗时缩短8%以上。
参考文献 | 相关文章 | 多维度评价
9. DFTS:面向大数据集的Top-k Skyline查询算法
魏亮, 林子雨, 赖永炫
计算机科学    2019, 46 (5): 150-156.   DOI: 10.11896/j.issn.1002-137X.2019.05.023
摘要535)      PDF(pc) (1524KB)(813)    收藏
Top-k Skyline查询结合了Top-k与Skyline的特性,可以在数据集中找到最好的点。但是,现有的算法在大数据环境下具有较高的时间开销。文中提出一种新的算法DFTS,其可以高效地在大数据集中进行Top-k Skyline查询。DFTS包括3个步骤:首先,利用度值评价函数对数据集进行排序,快速过滤掉大量的点,仅保留足够少的候选集;然后,对候选集进行Skyline查询计算,进一步排除掉Skyline集合外的点;最后,筛选出Top-k的数据点作为最终结果。通过这种方式,DFTS有效减少了算法的运行时间。从理论上证明了DFTS查询的最终结果符合Top-k Skyline查询的要求。基于大数据集的大量实验表明,DFTS具有比现有算法更好的性能。
参考文献 | 相关文章 | 多维度评价
10. 基于CAN的地理语义数据存储与检索机制
卢海川, 符海东, 刘宇
计算机科学    2019, 46 (2): 171-177.   DOI: 10.11896/j.issn.1002-137X.2019.02.027
摘要453)      PDF(pc) (1871KB)(754)    收藏
语义技术能够更智能、更精确地检索信息,辅助工作人员进行科学决策,已被应用于地理信息处理,并形成了基于RDF(Resource Description Framework)数据的地理查询语言GeoSPARQL。然而,基于地理语义信息处理的应用平台多采用中心化的存储和检索服务,使得这些平台存在单节点失效、扩展性差等缺陷。尽管已有研究人员提出了多种方法,试图利用对等网络技术来解决语义数据的分布式处理,从而提升应用系统的可靠性和扩展性,但这些方法并没有考虑地理语义数据自身的特征。针对上述问题,文中利用地理语义数据的特征在对等网络上对其进行存储,提出基于CAN(Content Addressable Network)的地理语义存储和检索方案,根据位置信息将地理语义数据映射到对等网络中,从而提高了语义数据的检索效率。实验结果表明,所提方案不仅具有良好的扩展性,而且地理信息的拓扑关系查询效率优于现有方案。
参考文献 | 相关文章 | 多维度评价