• 中国精品科技期刊
  • CCF推荐A类中文期刊
  • 计算领域高质量科技期刊T1类
Advanced Search
Liu Runtao, Liang Jianchuang. Reverse Nearest Neighbor Query Based on New Index Structure[J]. Journal of Computer Research and Development, 2020, 57(6): 1335-1346. DOI: 10.7544/issn1000-1239.2020.20190470
Citation: Liu Runtao, Liang Jianchuang. Reverse Nearest Neighbor Query Based on New Index Structure[J]. Journal of Computer Research and Development, 2020, 57(6): 1335-1346. DOI: 10.7544/issn1000-1239.2020.20190470

Reverse Nearest Neighbor Query Based on New Index Structure

Funds: This work was supported by the National Natural Science Foundation of China (11871181).
More Information
  • Published Date: May 31, 2020
  • To improve the efficiency of reverse nearest neighbor query, firstly the definition of the minimum bounding square based on nearest neighbor distance (MBSD) for spatial data and the definitions of four orders for spatial data are given. Then a new spatial data index structure—the index tree based on the minimum bounding square and the distance of nearest neighbor(MBDNN-tree) is proposed according to these definitions. The new index structure uses the idea of dividing spatial data in the R-tree, to construct the nodes on each level of an MBDNN-tree according to nodes’ geometric distribution and the corresponding order relation of nodes, by dividing the original data set in defined orders from top to bottom, and from left to right by using its MBSD to represent data. And then the detailed description and proof analysis are made for the algorithms in the preprocessing and constructing procedures used for creating an MBDNN-tree. The properties of an MSDNN-tree are obtained. Then the pruning rules for reverse neighbor query on an MBDNN-tree are set up, and further the reverse neighbor query algorithm on an MBDNN-tree is presented. The geometric orders among the nodes on the same level of an MBDNN-tree are used to reduce the visited node number of an MBDNN-tree for the reverse neighbor query so that the algorithm’s query efficiency is greatly improved. Finally, the reverse nearest neighbor query algorithm based on this structure is analyzed experimentally. Experiments show that the reverse nearest neighbor query algorithm based on MBDNN- tree has better query performance.
  • Cited by

    Periodical cited type(8)

    1. 李仲年,皇甫志宇,杨凯杰,营鹏,孙统风,许新征. 基于图提示的半监督开放词汇多标记学习. 计算机研究与发展. 2025(02): 432-442 . 本站查看
    2. 罗宇航,吴润秀,崔志华,张翼英,何业慎,赵嘉. 基于密度峰值聚类的Tri-training算法. 系统仿真学报. 2024(05): 1189-1198 .
    3. 刘旺成,方欢,张顺. 基于图像数据的缺失活动日志修复CNN方法. 计算机集成制造系统. 2024(08): 2787-2796 .
    4. 李道全,祝圣凯,翟豫阳,胡一帆. 基于特征选择与改进的Tri-training的半监督网络流量分类. 计算机工程与应用. 2024(23): 275-285 .
    5. 康昭,刘亮,韩蒙. 基于转换学习的半监督分类. 计算机研究与发展. 2023(01): 103-111 . 本站查看
    6. 李松,吴润秀,康平,赵嘉. 基于自适应剪辑与概率参数的Tri-Training算法. 江西师范大学学报(自然科学版). 2023(05): 490-496 .
    7. 王宇飞,陈文. 基于DECORATE集成学习与置信度评估的Tri-training算法. 计算机科学. 2022(06): 127-133 .
    8. 彭曦晨,葛斌,邰悦. 基于特征融合和注意力的图像分类研究. 合肥学院学报(综合版). 2022(02): 91-97 .

    Other cited types(13)

Catalog

    Article views (746) PDF downloads (261) Cited by(21)
    Turn off MathJax
    Article Contents

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return