一个多维数据搜索算法

J4 ›› 2012, Vol. 34 ›› Issue (9): 104-108.

一个多维数据搜索算法

钟声，钟小双，虞衍聪

（海南大学信息科学技术学院，海南海口 570228）

收稿日期:2012-04-15 修回日期:2012-06-25 出版日期:2012-09-25 发布日期:2012-09-25
基金资助:
海南省自然科学基金资助项目（611121）

A Search Algorithm for Multidimensional Data

ZHONG Sheng,ZHONG Xiaoshuang，YU Yancong

（College of Information Science and Technology,Hainan University,Haikou 570228,China）

Received:2012-04-15 Revised:2012-06-25 Online:2012-09-25 Published:2012-09-25

摘要/Abstract

摘要：

本文提出了一种使用二叉树组织多维数据的数据结构，在这种结构下提出了一个区域搜索算法，确定空间中给定点的区域内所有在给定数据集中的点，搜索效率与维数无关，算法的平均时间复杂性为O(logn)，为了保证算法的效率，提出了一种平衡树操作算法。

关键词: 搜索树, 空间数据, 区域搜索

Abstract:

This paper proposes a data structure that uses the binary tree to organize multidimensional data.Based on the proposed data structure,an area search algorithm is proposed in order to find out all points in the given data set in the domain of given points.The search efficiency of the algorithm is not related with the space dimension.The average time complexity of the algorithm is O(logn).To guarantee the algorithm efficiency,the paper also proposes a balanced tree adjustment algorithm.

Key words: search tree;spatial data;area search

钟声，钟小双，虞衍聪. 一个多维数据搜索算法[J]. J4, 2012, 34(9): 104-108.

ZHONG Sheng,ZHONG Xiaoshuang，YU Yancong. A Search Algorithm for Multidimensional Data[J]. J4, 2012, 34(9): 104-108.

[1]	杨秀娟1，宋俊山2，董军1，王丽芬1. 利用离散边界点判断的反向最远邻查询算法[J]. 计算机工程与科学, 2016, 38(08): 1682-1687.
[2]	来心可,吴筱天. 基于搜索树的平面图支配集算法[J]. J4, 2011, 33(6): 37-40.
[3]	刘世翔薛林福贺金鑫郄瑞卿邓春艳. 矿产地质信息挖掘与评价系统的设计与实现[J]. J4, 2008, 30(8): 89-91.
[4]	董元张时忠. Oracle Spatial＆ Map Viewer在汽车导航定位上的应用[J]. J4, 2008, 30(6): 119-120.
[5]	王新闻[1] 李胜余[1] 杨会军[2]. 基于SVG的空间数据组织和编码及其在WebGIS中的应用[J]. J4, 2008, 30(5): 78-80.
[6]	徐忆展[1] Rudolf Fleischer[2]. 限制树宽的图的最小标记生成数算法[J]. J4, 2008, 30(12): 72-74.
[7]	赵珏[1,2] 康志伟[3]. WebGIS在税务管理系统中的应用[J]. J4, 2006, 28(9): 109-111.
[8]	卢炎生向祥兵潘鹏. CQRtree空间数据库索引结构及实现算法[J]. J4, 2006, 28(6): 108-111.
[9]	卢炎生杨攀宇潘鹏. 时空数据库事务并发控制的动态封锁[J]. J4, 2005, 27(5): 45-47.
[10]	傅冰刘云翔陈荦唐宇. 基于空间信息栅格服务的空间数据集成[J]. J4, 2005, 27(1): 38-39.
[11]	于大东钟志农李军. 基于Oracle Spatial与GML的WebGIS研究[J]. J4, 2004, 26(4): 66-69.
[12]	万定生张俐等. 中间件技术在汛情监视地理信息系统中的应用[J]. J4, 2003, 25(1): 101-103.