徽标
联盟百科
通讯
下载应用,请到 Google Play
新! 在您的Android™设备上下载联盟百科!
自由
比浏览器更快的访问!
 

R树

指数 R树

R树是用来做空间数据存储的树状数据结构。例如给地理位置,矩形和多边形这类多维数据建立索引。R树是由Antonin Guttman于1984年提出的Guttman, A. (1984).

18 关系: 堆 (数据结构)多边形大圆距离子集交集地理位置B+树B树矩形線段樹 (儲存區間)Lp空间R*树R+树树 (数据结构)最小外接矩形最近鄰居法最邻近搜索数据库

堆 (数据结构)

堆(Heap)是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵树的数组对象。在队列中,调度程序反复提取队列中第一个作业并运行,因为实际情况中某些时间较短的任务将等待很长时间才能结束,或者某些不短小,但具有重要性的作业,同样应当具有优先权。堆即为解决此类问题设计的一种数据结构。《数据结构与算法分析》 Mark Allen Weiss(美)第六章,优先队列(堆)。.

新!!: R树和堆 (数据结构) · 查看更多 »

多边形

多邊形是平面的封閉图形、由有限線段(大于2)組成,且首尾連接起來劃出的形狀。.

新!!: R树和多边形 · 查看更多 »

大圆距离

大圆距离(Great-circle distance)指的是从球面的一点A出发到达球面上另一点B,所经过的最短路径的长度。一般说来,球面上任意两点A和B都可以与球心确定唯一的大圆,这个大圆被称为黎曼圆,而在大圆上连接这两点的较短的一条弧的长度就是大圆距离。若这两点和球心正好都在球的直径上,则过这三点可以有无数大圆,但两点之间的弧长都相等,且等于该大圆周长的一半\pi r, r 是球的半径。由于地球类似球体,地球上任何两点沿球面的最短距离都可以通过大圆距离的公式估算的出,这在航空和航海上都有很大作用。.

新!!: R树和大圆距离 · 查看更多 »

子集

子集,為某個集合中一部分的集合,故亦稱部分集合。 若A和B为集合,且A的所有元素都是B的元素,则有:.

新!!: R树和子集 · 查看更多 »

交集

数学上,两个集合A和B的交集是含有所有既属于A又属于B的元素,而没有其他元素的集合。.

新!!: R树和交集 · 查看更多 »

地理位置

地理位置是指地球表面某一事物与其它事物间的空间关系。地理位置是地理事物的特殊属性,是地理事物的标志之一。 任何地理事物的地理位置都是在一定的参照系中识别的,当参照系改变时,其含义会受到改变,因此地理学上有数理地理位置、经济地理位置、自然地理位置、政治地理位置等概念。.

新!!: R树和地理位置 · 查看更多 »

B+树

B+ 树是一种树数据结构,通常用于数据库和操作系统的文件系统中。B+ 树的特点是能够保持数据稳定有序,其插入与修改拥有较稳定的对数时间复杂度。B+ 树元素自底向上插入,这与二叉树恰好相反。 B+ 树在节点访问时间远远超过节点内部访问时间的时候,比可作为替代的实现有着实在的优势。这通常在多数节点在次级存储比如硬盘中的时候出现。通过最大化在每个内部节点内的子节点的数目减少树的高度,平衡操作不经常发生,而且效率增加了。这种价值得以确立通常需要每个节点在次级存储中占据完整的磁盘块或近似的大小。 B+ 背后的想法是内部节点可以有在预定范围内的可变数目的子节点。因此,B+ 树不需要象其他自平衡二叉查找树那样经常的重新平衡。对于特定的实现在子节点数目上的低和高边界是固定的。例如,在 2-3 B 树(常简称为2-3 树)中,每个内部节点只可能有 2 或 3 个子节点。如果节点有无效数目的子节点则被当作处于违规状态。 B+ 树的创造者 Rudolf Bayer 没有解释B代表什么。最常见的观点是B代表平衡(balanced),因为所有的叶子节点在树中都在相同的级别上。B也可能代表Bayer,或者是波音(Boeing),因为他曾经工作于波音科学研究实验室。.

新!!: R树和B+树 · 查看更多 »

B树

在计算机科学中,B树(B-tree)是一种自平衡的树,能够保持数据有序。這種資料結構能夠讓查找數據、顺序访问、插入數據及刪除的動作,都在對數時間內完成。B树,概括来说是一个一般化的二元搜尋樹(binary search tree),可以拥有多于2个子节点。与自平衡二叉查找树不同,B树为系统大块数据的读写操作做了优化。B树减少定位记录时所经历的中间过程,从而加快存取速度。B树这种数据结构可以用来描述外部存储。這種資料結構常被應用在数据库和文件系统的实现上。.

新!!: R树和B树 · 查看更多 »

矩形

在几何中,矩形定义为有一个角是直角的平行四边形,即是正方形和长方形。 在四邊形中,四邊相等且四個角是直角的,叫做正方形。 在四邊形中,角是直角,但對邊等長,叫做長方形。 ──歐幾里得《幾何原本》 从这个定义可以得出矩形两条相对的边等长,也就是说矩形是平行四边形。正方形是四個邊都等長的矩形,它的四个边都是等长的。 对于长方形两对相对的边,我们称横边为长,竖边为宽。长方形的面积是长和宽的乘积;用符号表示就是:A.

新!!: R树和矩形 · 查看更多 »

線段樹 (儲存區間)

線段樹(Segment tree)是一種二元樹形資料結構,1977年由Jon Louis Bentley發明,用以儲存區間或線段,並且允許快速查詢結構內包含某一點的所有區間。 一個包含n個區間的線段樹,空間複雜度為O(n\log n),查詢的時間複雜度則為O(\log n+k),其中k是符合條件的區間數量。 此資料結構亦可推廣到高維度。.

新!!: R树和線段樹 (儲存區間) · 查看更多 »

Lp空间

在数学中,Lp空间是由p次可积函数组成的空间;对应的ℓp空间是由p次可和序列组成的空间。它們有時叫做勒貝格空間,以昂利·勒貝格命名,儘管依據它們是首先介入。在泛函分析和拓扑向量空间中,他们构成了巴拿赫空间一类重要的例子。 Lp空间在工程学领域的有限元分析中有应用。.

新!!: R树和Lp空间 · 查看更多 »

R*树

R*树是R树的一种变体,可用来建立。R*树的构造花费比标准R树略高。例如数据可能需要被重新插入,但这通常能获得更好的查询性能。像标准R树一样,它能存储点和空间数据。它在1990年由Norbert Beckmann,Hans-Peter Kriegel,Ralf Schneider,和Bernhard Seeger提出。.

新!!: R树和R*树 · 查看更多 »

R+树

R+树可以用地址来查询数据。地址用坐标来表示,一般是(x, y)轴坐标,常用于地理坐标。单个地址查询问题早已被解决,而多地址查询,或者查询在坐标系上的附近地址则需要更巧妙的算法。 R+树本质上来说是树结构,是R树的一个变体,也被用来检索空间信息。.

新!!: R树和R+树 · 查看更多 »

树 (数据结构)

在計算機科學中,樹(tree)是一种抽象数据类型(ADT)或是實作這種抽象数据类型的数据结构,用來模擬具有樹狀結構性質的数据集合。它是由n(n>0)个有限节点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的。它具有以下的特点:.

新!!: R树和树 (数据结构) · 查看更多 »

最小外接矩形

最小外接矩形 (minimum bounding rectangle, MBR),也有译为最小边界矩形,最小包含矩形,或最小外包矩形。最小外接矩形是指以二维坐标表示的若干二维形状(例如点、直线、多边形)的最大范围,即以给定的二维形状各顶点中的最大横坐标、最小横坐标、最大纵坐标、最小纵坐标定下边界的矩形。这样的一个矩形包含给定的二维形状,且边与坐标轴平行。最小外接矩形是最小外接框(minimum bounding box)的二维形式。.

新!!: R树和最小外接矩形 · 查看更多 »

最近鄰居法

在模式识别领域中,最近鄰居法(KNN算法,又譯K-近邻算法)是一种用于分类和回归的無母數統計方法。在这两种情况下,输入包含特征空间中的k个最接近的训练样本。 最近鄰居法採用向量空間模型來分類,概念為相同類別的案例,彼此的相似度高,而可以藉由計算與已知類別案例之相似度,來評估未知類別案例可能的分類。 K-NN是一种,或者是局部近似和将所有计算推迟到分类之后的。k-近邻算法是所有的机器学习算法中最简单的之一。 无论是分类还是回归,衡量邻居的权重都非常有用,使较近邻居的权重比较远邻居的权重大。例如,一种常见的加权方案是给每个邻居权重赋值为1/ d,其中d是到邻居的距离。 邻居都取自一组已经正确分类(在回归的情况下,指属性值正确)的对象。虽然没要求明确的训练步骤,但这也可以当作是此算法的一个训练样本集。 k-近邻算法的缺点是对数据的局部结构非常敏感。本算法与K-平均算法(另一流行的机器学习技术)没有任何关系,请勿与之混淆。.

新!!: R树和最近鄰居法 · 查看更多 »

最邻近搜索

最邻近搜索(Nearest Neighbor Search, NNS)又称为“最近点搜索”(Closest point search),是一个在尺度空间中寻找最近点的优化问题。问题描述如下:在尺度空间M中给定一个点集S和一个目标点q ∈ M,在S中找到距离q最近的点。很多情况下,M为多维的欧几里得空间,距离由欧几里得距离或曼哈顿距离决定。 高德纳在《计算机程序设计艺术》(1973)一书的第三章中称之为邮局问题,即居民寻找离自己家最近的邮局。.

新!!: R树和最邻近搜索 · 查看更多 »

数据库

--,簡而言之可視為電子化的檔案櫃——儲存电子檔案的處所,使用者可以對檔案中的資料執行新增、擷取、更新、刪除等操作。 所謂「資料庫」係以一定方式储存在一起、能予多个用户共享、具有尽可能小的冗余度、与应用程序彼此独立的数据集合。.

新!!: R树和数据库 · 查看更多 »

传出传入
嘿!我们在Facebook上吧! »