导航数字地图数据组织方法和预取策略探讨

成本、环境因素、数据特性和应用特性使得有效实现汽车导航系统的地图显示成为一项挑战。为解决这些问题，本文从数据组织和数据缓冲角度，提出了分级数据组织、分级预取策略和基于启发信息的预取策略，并简要介绍了得到实用验证的多级Hilbert-R-Tree索引。     

中心导航系统终端地图预取和更新策略研究

为解决中心导航系统终端通过网络下载电子地图时,网络延时问题对终端地图实时显示的影响,根据空间相关性原理,提出了一种电子地图数据的预取和更新策略.该策略采用对电子地图分块传输和分块存储方法,对地图数据进行预取,并且使用二级缓存的方法,提高地图显示效率.仿真实验和实际车载实验结果表明,在CDMA的数据链路性能条件下,该预取和更新策略可以保证中心导航系统车载终端地图显示的实时性.     

矩形二叉树实现海量地形数据组织与管理

针对海量地形数据组织与管理,提出了一种矩形二叉树模型和无指针数据索引相结合的地形数据组织方法。矩形二叉树模型很好地保证数据的连续性,依据二叉树编码设计的无指针数据索引实现数据块的快速准确定位。此外,简化视见体的可见性判断和数据预取策略,实现可见数据的动态管理。实验结果表明文中的方法能够实现真实感海量地形数据的实时可视化。     

一种面向移动导航设备的电子地图空间索引结构

传统的R-tree系列和四叉树系列对数据对象的多级显示没有给予足够的支持,在小比例尺地图的显示过程中,影响了检索效率 .即使是支持多级显示的R-tree的各种变形,也由于对资源的要求而不能满足嵌入式设备的应用需求 .针对嵌入式设备数据I/O的特点,从地图数据的分级显示、顺序与批量访问、索引数据的优化等多方面入手,提出了一种基于多级Hilbert网格的线性索引结构 .实验证明该索引结构在空间利用率和查询性能等方面与传统的空间索引技术相比有明显的改善,并在上海市交通信息网格移动交通信息服务终端上获得了良好的实施效果 .     

网格虚拟组织副本协作预取机制

副本复制是数据网格中提高数据访问效率的有效方法,如何提高副本复制的效率是一个关键性问题.现有的复制策略大多基于文件访问历史选择高价值副本进行复制,但其针对的都是节点已经访问过的文件.通过对虚拟组织文件访问特性进行深入分析,引入隐性高价值文件概念,提出虚拟组织副本协作预取机制(cooperative replica prefetching mechanism,简称CoRPM),使得本地节点通过与虚拟组织中其他节点进行协作来获取隐性高价值文件副本.该机制首先给出了副本协作预取架构,各个虚拟组织节点上的文件预取模块以协作的方式为虚拟组织内节点提供文件预取服务;然后,在副本协作预取架构的基础上设计了副本协作预取流程,其核心算法包括以作业类型为中心的本地文件预取算法和预取文件选择算法.模拟实验结果表明,CoRPM与已有的基于文件访问历史的副本复制策略相结合,可以更加有效地降低数据访问延迟.     

副本协作预取中文件相关性查询机制

副本协作预取是一种网格副本复制策略,旨在通过获取隐性高价值文件进一步降低数据访问延迟.副本协作预取的关键在于隐性高价值文件的确定和获取,因此,提高隐性高价值文件获取的速度能够大幅度提升副本协作预取的性能.利用DHT(distributed hash table)组织网格节点,以快速定位隐性高价值文件查询所必需的文件相关性信息.针对隐性高价值文件的特殊查询模式,提出基于预取规则树的文件相关性信息存储结构及其查询机制,以提高查询效率.基于真实网格作业运行记录的实验,验证了所提出方法的有效性和高效性.     

超量外存地表模型的实时绘制技术

提出一种分块策略对规则网格进行区域分割,采用空间填充曲线对分块内网格点进行多分辨率排列,并基于分块多分辨率对地形网格实时调度和页面预取．文中算法利用块模型进行分块视域剔除和分块LOD场景渲染．在多线程分块多分辨率调度和渲染策略下,大大减少了模型的I／O负载,可以在有限环境下满足实时场景绘制要求．     

GridDaEn数据网格中的元数据预取与缓存策略

因数据网格系统部署在广域网环境,所以网络传输延时将成为影响其服务质量(QoS)的主要因素之一。在对预取技术进行了深入细致的探讨之后,本文利用空间换取时间的思想提出了一种元数据的预取与缓存策略。考虑到Grid-DaEn系统中元数据自身的特点,还提出了一种新颖的元数据预取算法DHMP。     

多用户存储中自适应动态预取策略

通过分析多用户数据请求规律以及实时分解随机请求序列来获取顺序请求序列。基于对多用户顺序请求进行命令预分解和命中率统计,实现读预取长度自我学习。分析多用户预取率及系统负载与预取失效代价之间的关系,对常规自适应Cache策略进行优化,选择合适预取阈值等参数。与常规自适应预取策略相比,动态调整Cache策略的预取命中率提高了30%。有效解决了多用户访问共享存储系统的预取失效率高问题。     

嵌入式GIS中矢量地图快速显示方法研究

为提高嵌入式GIS中矢量地图的显示速度,建立了要素分级的多层网格索引模型.该模型算法简单,耗用内存小,便于实现.显示地图时,直接依据当前的显示比例,读取对应网格索引中相应级别的地图数据,避免了大量非屏幕区域的冗余地图数据读取,极大地提高了显示速度,同时设计了折线与矩形求交的算法来提高地图数据显示处理的效率.实验结果表明,该方法能显著提高嵌入式平台矢量地图的显示速度,并且已成功应用于手持GPS定位终端软件.     

移动环境下支持实时事务处理的数据预取

随着移动通信技术的迅速发展,人们提出了新的应用要求:在移动环境下处理实时事务.而移动通信带宽有限性引起较大的数据访问延迟,有时甚至由于网络传输的断接使得事务得不到所需要的数据,数据预取能够很好地解决这个问题.已有的移动环境下数据预取没有考虑到数据的流行性和事务的时间特性.该文分析影响实时事务数据预取的因素,首先考虑数据易变性、活跃性等因素,获得高价值预取数据集合;然后考虑访问预取数据的事务优先级、数据流行性等因素,构造预取数据的选择函数,通过该函数在前面选取的集合中筛选出对满足实时事务截止期更有价值的数据对象进行预取.实验表明,该数据预取策略能降低移动实时事务满足截止期的比率,更好地支持移动实时事务处理.     

Taxonomy of Data Prefetching for Multicore Processors

Data prefetching is an effective data access latency hiding technique to mask the CPU stall caused by cache misses and to bridge the performance gap between processor and memory.With hardware and/or software support,data prefetching brings data closer to a processor before it is actually needed.Many prefetching techniques have been developed for single-core processors.Recent developments in processor technology have brought multicore processors into mainstream. While some of the single-core prefetching t...     

分级存储系统中一种数据自动迁移方法

分级存储系统通过将数据在不同性能设备间动态迁移以达到高性能.已有分级存储系统未能充分利用负载信息导致数据迁移严重影响应用性能.提出了一种分级存储系统中的数据自动迁移方法AutoMig,目标是提高前台应用的I?O性能.AutoMig综合文件访问历史、文件大小、设备利用情况等参数,对文件进行动态分级,并使用LRU队列维护快速存储设备中的文件状态;挖掘关联文件用于自动预取;针对不同文件迁移操作采取不同的速率控制策略.对降级操作,根据负载变化动态调整迁移速率,对回迁操作则采取尽力而为的策略.在分级存储系统中的应用表明,与已有方法相比,AutoMig有效缩短了前台I?O响应时间.     

基于Alluxio远程场景下缓存策略的优化*

当今时代数据呈现出指数级增长效应,更多的组织采用多数据中心和分布式来存储数据,Alluxio作为以内存为中心的虚拟分布式存储系统,整合了底层大数据生态系统。在Alluxio与底层存储结合的远程场景中,由于网络的延迟,使得I/O速度成为影响对外服务的重要因素之一。针对以上研究提出一种基于Alluxio远程场景下的缓存策略CPR,利用存储系统中数据块之间的关联性指导数据预取与替换,采用分组思想提高关联规则的利用率,启用后台线程实时更新规则集,并通过仿真实验验证策略的有效性。仿真结果表明,CPR策略指导下的I/O性能要优于Alluxio现有的缓存策略和一些基于数据块间关联规则的缓存策略。     

基于变周期数据广播的缓存一致性维护

为了提高移动计算环境中缓存数据效率,在分析现有成果的基础上,提出了基于变周期数据广播的缓存一致性维护的策略。该策略根据数据的访问用户数目以及数据更新的频率等方法来动态调整服务器广播数据更新报告的频率及内容,在客户端接收服务器广播的数据更新报告后将缓存中已被更新过数据项的值用新值替换掉,而不直接将该数据项立即移出缓存。通过对该方法进行性能的分析,表明该方法能良好地适应数据更新频率不断变化的移动数据计算环境。     

面向链式数据结构的间隔预取策略

由于链式数据结构的存储缺乏空间局部性,导致程序执行过程中对链式数据的访问会发生严重的Cache缺失行为。通过对面向链式结构的线程预取性能分析,研究链式数据结构程序热点循环的计算任务量与访存任务量比例特征对线程预取性能的影响。结合多核处理器平台特点,实现了一种适用于链式数据结构的帮助线程间隔预取方法。实验结果进一步验证了计算任务量与访存任务量比例特征对间隔预取性能的影响,表明间隔预取相比于传统线程预取技术有明显的性能优势。     

一种自适应的数据预取与缓冲算法

在海量数据中进行的直接查找往往耗时巨大,在实际应用中很难满足实时性的需求,因此采用数据预取和缓冲技术实现对查找操作的优化成为实际系统中的重要环节。自适应的数据预取和缓冲算法是通过使用人工智能中的技术来分析用户的查询习惯,从而实现动态的预取策略并对预取的数据进行缓冲,以达到提高查询速度的目的。文章根据不同的数据查询需求提出了两类智能算法以适应不同的应用场合。在实验中分别针对单个用户的历史查询应用和多用户的并发查询应用分别进行了分析,证明了这两类智能算法分别对不同的应用场合拥有较好的性能。     

反馈指导的链式数据结构预取优化

传统的基于静态编译的数据预取大多针对数组访问,现在的应用程序中大量出现由指针构成的链式数据结构,依赖传统的编译方法难以进行预取优化.反馈式数据预取优化技术是当前高性能计算技术中前沿的一种编译优化手段,可以很好地解决链式结构的预取问题.在研究ORC编译器反馈式编译优化技术的基础上,针对Alpha结构的特点,对针对链式结构的反馈式数据预取进行了优化.SPEC2000测试表明,平均性能提高了4.1%.     

A Data Cube Model for Prediction-Based Web Prefetching

Reducing the web latency is one of the primary concerns of Internet research. Web caching and web prefetching are two effective techniques to latency reduction. A primary method for intelligent prefetching is to rank potential web documents based on prediction models that are trained on the past web server and proxy server log data, and to prefetch the highly ranked objects. For this method to work well, the prediction model must be updated constantly, and different queries must be answered efficiently. In this paper we present a data-cube model to represent Web access sessions for data mining for supporting the prediction model construction. The cube model organizes session data into three dimensions. With the data cube in place, we apply efficient data mining algorithms for clustering and correlation analysis. As a result of the analysis, the web page clusters can then be used to guide the prefetching system. In this paper, we propose an integrated web-caching and web-prefetching model, where the issues of prefetching aggressiveness, replacement policy and increased network traffic are addressed together in an integrated framework. The core of our integrated solution is a prediction model based on statistical correlation between web objects. This model can be frequently updated by querying the data cube of web server logs. This integrated data cube and prediction based prefetching framework represents a first such effort in our knowledge.