反向最远设施查询及其代价模型的研究
DOI: 10.3969/j.issn.1006-7043.2009.11.011
Keywords: 离散边界点 邻域区 反向最远设施查询 代价模型 discrete boundary points neighborhood region reverse furthest facility search cost model
Abstract:
针对现有反向最近邻查询不能有效支持满足弱影响集的设施查询这一类问题,利用离散边界点及邻域区等概念和相关定理实现对反向最远邻的判定.在此基础上提出反向最远设施查询,并给出其选择查询算法及索引结构.该算法可以准确地得到反向最远设施查询的结果,其动态更新算法可实现对查询点的反向最远设施查询结果的更新.在R~*-树的基础上构建RFF-树,并给出其选择查询算法的代价模型.实验结果表明,在3种不同数据分布空间中,采用基于RFF-树的反向最远设施选择查询的实际页面访问次数与代价分析预测的结果相近,代价模型的平均误差率约为12%.
References
[1] 1. STANOI I.RIEDEWALD M.AGRAWAL D Discovery of influence sets in frequently updated databases discovery of influence sets in frequently updated databases 2001 [2] ？2. TAO Yufei.MAN Lungyiu.NIKOS MAMOULIS Reverse nearest neighbor search in metric spaces 2006(9) [3] 3. 李松.郝忠孝 基于Voronoi图的反向最近邻查询方法研究 [期刊论文] -哈尔滨工程大学学报2008(3) [4] 4. ZHANG Donghui.DU Yang.XIA Tian.TAO Yufei Progressive Computation of the Min-Dist Optimal-Location Query 2006 [5] 5. SERGIO CABELLO.MIGUEL D J.LANGERMAN S.SEARA C,VENTURA I Reverse facility location problems 2005 [6] 6. 潘锐.朱大铭.马绍汉 一般设施定位问题计算复杂度和近似算法研究 [期刊论文] -计算机研究与发展2007(5) [7] 7. BECKMANN N.KRIEGEL H P.SCHNEIDER R.SEEGER B The R~*-tree:an efficient and robust access method for points and rectangles 1990 [8] 8. BOHM C.BERCHTOLD S.KEIM D Searching in high-dimensional spaces-index structures for Improving the performance of multimedia databases 2001(3) [9] ？9. BESPAMYATNIKH S.KEDEM K.SEGAL M.TAMIR A Optimal facility location under various distance functions 2000 [10] 10. CORRAL A.YANNIS M.THEODORIDIS Y Cost models for distance joins queries using R-trees 2006(1)
Full-Text
