道路网上最短路径算法综述

在道路网上计算两点之间的最短路径是图论算法的众多实际应用之一。经典的Dijkstra算法在大规模图上过于缓慢。过去十年间,这个经典问题在道路网上取得了重大突破,目前已知最快算法的运行效率比Dijkstra算法快了百万倍。这些算法都对道路网数据进行预处理,产生一定的辅助信息以加速查询,其中目标向导方法和层次化方法是两类典型方法。一些算法的实验性能良好,但缺乏理论支撑。这是因为难以用数学语言严格地刻画道路网的特性。因此,如何弥合理论与实践的差距是此问题面临的主要挑战。     

MapReduce框架下的Skyline计算

由于Skyline查询广泛应用于多目标决策、数据可视化等领域,近年来成为数据库领域的一个研究热点。针对云计算环境,在MapReduce框架下设计并实现了Skyline算法。MapReduce是一个运行在大型集群上处理海量数据的并行计算框架,其主要思想是任务的分解与结果的汇总。基于不同的数据划分思想,实施了三种Skyline并行算法,分别是基于MapReduce的块嵌套循环算法(MapReduce based block-nested-loops,MR-BNL)、基于MapReduce的排序过滤算法(MapReduce based sort-filter-skyline,MR-SFS)以及基于MapReduce的位图算法(MapReduce based bitmap,MR-Bitmap),并针对这三种算法进行了系统的实验比较,得出了不同数据分布、维数、缓存等因素对算法性能的影响结果。