一种存储最佳的分支界限轮廓查询算法

摘要

给定一组多维的点,轮廓(skyline)查询能返回在所有维度上均不被其他点所支配(dominate)的点集.目前,对于集中式环境下的静态数据,BBS(分支界限轮廓)是一种最为有效的轮廓查询算法.然而,它却存在内存空间耗费大的不足.鉴于此,提出了一种基于最佳优先最近邻居查找的轮廓查询算法,称为IBBS(改进的分支界限轮廓).它既有最佳的I/O代价和较低的CPU开销,又有最少的内存空间消耗.其核心是利用一系列有效的剪枝策略丢弃所有不必要的记录.大量的实验证实IBBS优于BBS,尤其是在低维空间.