一种◢k◣-ary搜索树的快速求交算法

k-ary搜索树因其对高速缓存和SIMD并行指令集天然的适配性,正在受到越来越多的关注和研究.近年来,它被成功地应用于搜索引擎倒排索引结构中,用于实现高效的查询处理和索引压缩.但基于k-ary搜索树的查询处理算法目前仍处在一种相对简单基础的应用程度,效率提升有限;而且查询算法仅限于元素搜索,大大限制了其适用范围.基于上述观察,研究了基于k-ary搜索树的求交算法,并提出了两种优化技术用于压缩搜索范围以提升查询效率.实验证明,结合不同的遍历方式,优化后的求交算法可以极大地提高查询速度,尤其是针对存储海量数据的长倒排链,配合更大的SIMD寄存器,k-ary搜索树相比于传统求交算法的优势更为明显.     

实时子步积分算法的设计与实现

积分算法是实时仿真的关键所在,传统的单步法结构简单,但精度较差。而多步高阶积分算法虽然精度高,却由于结构复杂实时性不强。文章在对实时仿真积分算法研究的基础上,提出了实时子步积分算法,使不同的积分算法拥有相同的子步控制结构。由于每个子步的运算量一样,所以在步长和帧数一致的情况下,不同的积分算法运算时间是一致的。经仿真实验表明,该算法的子步结构显著提高了多步积分法的实时性,且误差精度在可控范围内。     

基于阈值的快速启动Top-k查询处理算法

Top-k查询是搜索引擎领域广泛应用的技术之一,该算法从海量数据中返回最符合用户需求的前k 个结果,在执行时能避免对大部分无关文档的打分处理。Top-k 查询虽然极大提升了查询性能,但其存在的慢启动问题并未得到有效解决。为此,该文首先提取倒排索引的静态Top-k信息,再动态计算针对具体查询词项的初始阈值,在此基础上,结合MaxScore和WAND算法,提出了快速启动的Top-k查询处理算法。实验结果表明,该方法能够有效解决上述问题,具有良好的性能。     

基于四叉树的缓存复用机制地形算法

为了减少地形数据的冗余,实现缓存复用,在研究了Geo-CLipmap算法的基础上,针对其采用嵌套网格一次只能渲染单张高程图的方案,提出了一种块状四叉树的数据结构,同时分开存储节点的位置信息和高程信息,有效地减少了数据大小和数据交换,实现了顶点和索引缓存的复用;利用掩膜填充不同分辨率网格之间的缝隙,避免了加入光照后的几何失真,并使用几何过渡消除几何体的跳变。经过实验测试,该算法能有效地压缩数据量,在稳定帧速的情况下,实现地形的无缝渲染。