摘要
针对现有反向最近邻查询不能有效支持满足弱影响集的设施查询这一类问题,利用离散边界点及邻域区等概念和相关定理实现对反向最远邻的判定.在此基础上提出反向最远设施查询,并给出其选择查询算法及索引结构.该算法可以准确地得到反向最远设施查询的结果,其动态更新算法可实现对查询点的反向最远设施查询结果的更新.在R*-树的基础上构建RFF-树,并给出其选择查询算法的代价模型.实验结果表明,在3种不同数据分布空间中,采用基于RFF-树的反向最远设施选择查询的实际页面访问次数与代价分析预测的结果相近,代价模型的平均误差率约为12%.
Reverse furthest facility location is a new issue in spatial database theory and applications. The reverse nearest neighbor query cannot solve the facility search efficiently based on the weak influence set. This paper formalizes the definition and proves primary properties of reverse furthest neighbors. Theorems for judging the reverse furthest neighbor are proposed based on using the discrete boundary points and neighbor regions. The metric distance was extended to support the reverse furthest facility search efficiently. The updating algorithm that deals with dynamic datasets can update search results in real time. The reverse furthest facility tree based on the R^ ＊ -tree and a cost model for the selection search algorithm were presented. Experimental results indicate that the cost model can evaluate the number of page accesses required with a low relative error ratio. The estimated average error ratio was about 12%.
出处
《哈尔滨工程大学学报》
EI
CAS
CSCD
北大核心
2009年第11期1261-1267,共7页
Journal of Harbin Engineering University
基金
国家自然科学基金资助项目(60673136)
黑龙江省自然科学基金资助项目(F200601)
关键词
离散边界点
邻域区
反向最远设施查询
代价模型
discrete boundary points
neighborhood region
reverse furthest facility search
cost model
