反向最远设施查询及代价模型研究.pdfVIP

第30卷第ll期 哈尔滨工程大学学报 V01．30№．1l 2009年11月 JoumalofHarhin Nov．2009 EngineeringUniversity doi：10．3969／j．issn．1006—7043．2009．11．Oll 反向最远设施查询及其代价模型的研究 李博涵1，郝忠孝1’2 (1．哈尔滨理工大学计算机科学与技术学院，黑龙江哈尔滨150080；2．哈尔滨工业大学计算机科学与技术学院，黑龙江 哈尔滨150001) 摘要：针对现有反向最近邻查询不能有效支持满足弱影响集的设施杳询这一类问题，利用离散边界点及邻域区等概念 和相关定理实现对反向最远邻的判定．在此基础上提出反向最远设施查询，并给出其选择查询算法及索引结构．该算法 可以准确地得到反向最远设施杳询的结果，其动态更新算法可实现对查询点的反向最远设施查询结果的更新．在R‘．树 的基础上构建RFF-树，并给出其选择查询算法的代价模型．实验结果表明，在3种不同数据分布空间中，采用基于RFF． 树的反向最远设施选择查询的实际页面访问次数与代价分析预测的结果相近，代价模型的平均误差率约为12％． 关键词：离散边界点；邻域区；反向最远设施杳询；代价模型 中图分类号：TP311．13文献标识码：A文章编号：1006-7043(2009)11．126l聊 on of Research thereVersefurthest withacostmodel queries facility UBo-hanl，HA0Zhong—xia012 of scienceand l 0f (1．collegeComputer Technolo盱，Harbinunivers时ofscience卸d‰hnology，Harbin Scienceand Institute of Computer Tbchnology，Harbin7rechnology，Harbin15000l，China) furthest 10cationisa newissuein Abstract：ReVerse databaseand reverse f如ility spatial theoryapplications．The nearest cannotsolVethe search basedontheweakinnuencese￡．This for- neighborquery facility e佑ciently paper malizesthedefinitionand ofreve玛efurthest for thereverse pmVesprimarypropenies neighbors．Theoremsjudging funhest are basedon thediscrete and Themetricdis— neighborpmposed using boundarypointsneighborregions． wasextendedto thereVersefurthest tance search thatdealswit