持久性(基于磁盘)R-树(或R*树)。
如何将r*树作为持久性(基于磁盘)的一个?用于保存r*树索引或保存叶值的文件的架构是什么? 注意:此外,在这样的持续r*树中可以执行插入,更新和删除操作? 注释II:我已经实现了具有散装载荷功能的内存R-Tree.但是我认为,当我们谈论基于磁盘的磁盘时,这是完全无关紧要的. 解决方案 如果您需要有一个磁盘R-Tree索引,我建议使用空间或 postgis .空间岩是轻巧且易于嵌入独立应用中的.另外,您是否查看了 c#空间索引项目?.几年前,我在Java撰写了R-Tree实施,如果已经存在某些东西,不建议这样做. 其他解决方案 文件的体系结构 好吧,它是页面(=块).这些页面应具有基础存储的页面大小的倍数,因此大概是1KB或8KB块.每个块都有一个数字,可以通过这种方式参考. 目录页面存储了儿童的边界框及其页码. 儿童页面存储实际数据对象. 管理树 很好,从理论上讲:每当您在内存中修改页面时,都会为磁盘写更改.就是这样. 实际
12 2024-04-20
编程技术问答社区
有没有在F#(或C#)中实现的R | Tree?
可能的重复: 是否有.net有任何文档的免费R-Tree实现? f#? 中是否有任何R-Tree实现 假设是:无需插入或删除,固定的地理围栏(区域). 需求是:非常快的搜索时间. 谢谢 解决方案 这是 ocaml 的快速翻译P> namespace RTree open System module Envelope = type t = float * float * float * float let ranges_intersect a b a' b' = a'
18 2024-04-19
编程技术问答社区
我可以用线程使用Boost.Geometry.index.rtree吗?
我正在尝试使用BOOST.SOMETRY的RTREE创建多线程空间索引,但是我无法确定这是否是线程安全.我在rtree.hpp中没有看到任何锁定机制,但是我的C ++/提升知识处于初学者级别. BOOST.DEOMETRY.INDEX.RTREE线程以任何方式安全吗?如果没有,以安全的方式将其与多个线程一起使用的最佳方法是什么(例如,插入()调用之间的静音锁定?具体来说,我试图获得更好的查询(阅读)性能. 解决方案 是boost.deometry.index.rtree螺纹以任何方式安全吗? 否 如果没有,以安全的方式将其与多个线程一起使用的最佳方法是什么(例如,插入()调用之间的mutex锁定? 最佳?取决于. 您需要相互排斥.您可以使用Spinlock,简单的静音,共享/可升级的静音等来完成此操作. 我可以和insert()同时询问(). 当然不是.这就是所谓的数据竞赛,这是您首先需要的相互排除(又称监视器). 特别是我试图
18 2024-04-02
编程技术问答社区
盒子的提升树给出了与段的错误交集
Boost rtree给出了与段查询的一些交点的错误交点结果. 在这种情况下,边界框是y = 0时的y平面10x10平方.我正在使用(2、1、0)到(2、1、10)的Z对准线查询.有趣的是,如果我使用一个盒子来查询而不是细分市场,那么它可以按预期工作.当盒子不是平面时,此行为也存在,只需将最小角移至(0,-5、0),然后仍然发生. 我是在使用这个错误还是在Boost中是一个错误? 编辑:在Boost 1.56和1.59上尝试了此操作. #include #include "gtest/gtest.h" #include "gmock/gmock.h" #include #include #include #include
4 2024-04-02
编程技术问答社区
对Boost.Geometry rtree进行序列化/去序列化
简短版本:是否有任何稳定/可靠的方法来序列化/除外序列化.几何rtree? 更长的版本:BOOST.几何中的RTREE实现对序列化/除外序列化具有实验支持,但是支持是不稳定的,有时在去序列化过程中会引发异常.我什至不知道它是否会静静地破坏树数据. 我已经实现了一个简单但非常缓慢的hack:序列化所有树节点(而不是整个树),并在除外序列化过程中重建树.我想要更快的东西. 解决方案 您可以使用可提供大量加载的包装构建器. ://www.boost.org/doc/libs/1_62_0/libs/geometry/doc/html/geometry/spatial_indexes/introduction.html 此外,还有一些算法创建R-Tree,其中包含一些对象.该技术称为散装加载,并通过使用填料算法[5] [6]来完成.该方法更快,导致具有更好内部结构的R-Trees.这意味着查询性能提高. 如您所见,您可以期望从包装算法中获得最佳查询性能: i
0 2024-04-02
编程技术问答社区
存储或访问提升R树中的对象
我正在使用boost::geometry::model::point对象. 我的问题:无论如何是否有存储对象( 城市本身),而不仅仅是在树上的坐标?我想到的一种解决方案是使用自己的索引.如果这确实是我应该做的 - 无论如何,是否在那里可以通过插入树的顺序找到对象的索引? 所以,例如,当我寻找某些城市的KNN时 - 我不仅要提取它们的坐标(或距离),就像他们在示例中一样: for ( rtree_t::const_query_iterator it = rtree.qbegin(bgi::nearest(pt, N)); it != rtree.qend() ; ++it ) { std::cout
2 2024-04-02
编程技术问答社区
Android SQLite R-Tree如何安装模块?
http://www.sqlite.org/rtree.html 树是"作为合并的一部分,但默认情况下是禁用的",并启用它"只需使用sqlite_enable_rtree c-preprocessor宏定义的sqlite_enable_rtree comp. 好吧,我想在我的Android应用中使用R-Trees,但是显然SQLite都是已预安装的.是否可以在用户的​​电话/设备上启用它? 另外,是否可以使用ndk和可自由使用的源代码? 解决方案 您绝对可以编译自己的SQLite版本.我们这样做是为了从WXSQLITE启用加密/编解码模块.查看Android Git存储库中的SQLite源.基本上,它很容易,并与您希望启用的选项(例如sqlite_enable_rtree)创建Android.mk.当然,这将为您提供一个本地图书馆.为了使用它,您需要从NDK访问它或创建包装器(再次,您可以查看Android存储库,Java/JNi包装器到SQLITE) 其他解决方案
12 2024-02-17
编程技术问答社区
R-Tree 实现 Java
我在过去的几天中搜索了R-Tree的稳定实现,并支持无限维度(20个左右的时间就足够).我只找到了此 . 另一个选项将是间隔树的多维实现. 也许我对使用R-Tree或Intervall-Tree解决问题的想法是完全错误的,因此我简而言之,您可以将您的想法发送给我. 我需要解决的问题是某种最近的邻居搜索.我有一组天线和房间,每个天线都有整数的间隔.例如.天线1,最小-92,最大-85.实际上,它可以表示为天线的室 - >天线 - >天线间隔. 这个想法是,每个房间都跨越天线的尺寸和每个维度的R-树横跨一个盒子. 如果我获得了n-antennas的查询和每个天线的值,那么我就可以将信息表示为房间中的查询点,然后检索"最近"的房间. 希望您对问题和我的想法有一个想法. 解决方案 请注意,当您拥有离散数据时,R-Trees会严重降解.您真正需要找出的第一件事是适当的数据表示,然后测试您的查询是否在数据子集上工作. r-树只能使您的查询更快.如果他们首先
6 2024-01-22
编程技术问答社区
是否有任何记录在案的适用于.NET的免费R-Tree实现?
我在C#中找到了一些开源R-TREE实现,但是没有文档,也没有其他人使用的迹象. 解决方案 nettopologysuite 是其他解决方案 我不知道,但是我会指出这样的库倾向于: 写(通常使用一些错误). 虫子虽然使用了. 所有活动错误均已修复 可选 "潜在"错误,由于平台以某种方式更改图书馆的平台上的先前语义,该错误永远不会发生. . 因此,在图书馆的提交方面缺乏活动,不应表明库死了,它可能表明它非常稳定且坚固.如果图书馆易于理解或针对相对复杂的受众(如当前的R-Tree使用情况),那么您可能会发现几乎没有在线对话. 缺乏下载活动有些令人担忧.尽管您在以前以重型GIS/空间查询工作不知名的平台上使用了相当利基库(尽管SQL Server 2008的更改可能会改变). 如果找不到适当活动的Java库,则不太可能会找到一个C#.如果您发现这样的Java一个直接(与惯用性的)端口不太可能出现问题. 其他解决方案 根据此线程/a>有一个R-
14 2024-01-04
编程技术问答社区
libspatialindex和Rtree on python
好吧,所以我试图将libspatialspatialindex安装到我的Ubuntu Machine Python.我确实按照所有说明进行了操作,然后从 并下载了它的AMD64版本,因为我的计算机是64BITS机器.我安装了它,然后跳到rtree python >在Python中下载并安装RTREE.我遵循文件夹内的install.txt文件中给出的安装说明.它说运行本地设置. `root@ubuntu:/# cd /home/neelabh/Desktop/Rtree root@ubuntu:/home/neelabh/Desktop/Rtree# python setup.py install Traceback (most recent call last): File "setup.py", line 4, in import rtree File "/home/neelabh/Desktop/Rtree/rtree/__init__.py", line 1,
18 2023-11-01
编程技术问答社区
哪些应用程序使用R-Tree?
除了GIS应用程序外,哪些其他应用程序或库使用R-Trees及其变体? 解决方案 电脑游戏经常这样做. 这是一个很酷的链接. . 计算机图形 - 软件和硬件 - 经常使用空间分区,例如 bsp ;想象中有整洁的逻辑,而英特尔芯片则称为 tile or = tile or = tile or tile or tile or tile or tile or tile or tile或boredering 例如.. 我所看到的代码倾向于倾向于固定分辨率划分 - 通常是八个尺寸 - 而不是可变大小的存储桶,但我仍然认为它们是R -Trees的"变体". 其他解决方案 一些关系数据库使用R-Trees进行索引. PostgreSQL是一个示例. 其他解决方案 这是一个应用程序 - 使用PERST LITE开源嵌入数据库的R-Trees使用的个人碳计算器.
16 2023-10-26
编程技术问答社区
R-Trees:我应该重新发明车轮吗?
我正在尝试了解如何实现R-Tree,该R-Tree将用于"选择"边界矩形中包含的一组几何对象.我检查了文章在Wikipedia上,该文章显示了数据布局为a b-tree . i 可以写一个b-tree并用它来编写R-Tree,但是这是两个复杂的数据结构,我必须调试,测试等.我宁愿重复使用现有的树实现(STD :: SET/MULTISET)并提供排序操作. 假设我的形状有以下接口: class Shape { public: Shape(); virtual ~Shape(); const AABB & bounding_box() const = 0; }; 并为订购形状提供此函数: struct OrderShapes { bool operator()(Shape * const & left, Shape * const & right) const { retur
26 2023-09-30
编程技术问答社区
使用rtree和普通索引的SQLite查询速度缓慢
我在sqlite表中有地理空间数据,带有坐标的名称,并为位置创建一个rtree,并在名称列上创建一个普通索引. 根据此文档使用 rtree: 当我在特定区域查询记录时,使用了rtree,并且可以快速起作用: SELECT demo_data.* FROM demo_data, demo_index WHERE demo_data.id=demo_index.id AND minX>=-81.0 AND maxX=35.0 AND maxY>=36.2; 当我仅查询名称时,它也会很快,因为使用了名称索引: SELECT demo_data.* FROM demo_data WHERE objname="Test" 但是,当我组合两者时,它非常慢,似乎整个桌子都被扫描了: SELECT demo_data.* FROM demo_data, demo_index WHERE demo_data.id=demo_ind
44 2023-09-22
编程技术问答社区
如何使用SQLite R-Trees将简单的空间索引移向Postgres?
我通过按照sqlite r*tree 教程,它给了我以下模式: CREATE VIRTUAL TABLE events_region USING rtree( id, -- primary key xmin, xmax, -- minimum and maximum X coordinate ymin, ymax, -- minimum and maximum Y coordinate ); 我现在想将此架构移植到Postgres(但不使用Postgis来减少依赖项).我知道,使用GIST索引应该可以使用(因为R-Trees已经逐步淘汰,GIST现在扮演了他们的角色),但是我正在努力解决如何解决这个问题. 解决方案 这是一个带有点而不是框的示例: time psql -c 'create table t(p point)' time psql -c "insert into t select (
8 2023-09-22
编程技术问答社区
在大数据集上寻找离每个点最近的线,可能使用shapely和rtree
我有一张简化的城市地图,其中有街道是线条和地址作为点.我需要找到从每个点到任何街道线的最接近路径.我有一个可以执行此操作的工作脚本,但是它在多项式时间内运行,因为它已嵌套以进行循环.对于150 000行(巧妙的线条)和10 000点(巧妙的点),在8 GB RAM计算机上完成10小时. 该功能看起来像这样(很抱歉,不完全可重复): import pandas as pd import shapely from shapely import Point, LineString def connect_nodes_to_closest_edges(edges_df , nodes_df, edges_geom, nodes_geom): """Finds closest line to points and returns 2 da
110 2023-08-31
编程技术问答社区
我怎样才能在ELKI中使用索引结构?
这些是引号表格 >: "本质上,我们将抽象距离查询绑定到数据库,然后将最近的邻居搜索此距离.此时,Elki将自动选择最合适的KNN查询类.如果是否存在适当的索引距离功能(并非每个索引都可以加速每个距离!),它将在此处自动使用." " getknnfordbid方法可能归结为慢的线性扫描,但是当数据库具有适当的索引时,将使用索引查询.然后,算法可以在O(N K Log N)甚至O(N K)中运行算法.时间." 问题是:Elki选择是否运行索引查询? 是什么意思:"何时数据库具有适当的索引",我该如何保证? 关于"运行"方法签名的另一个无关的问题, 为什么只有3个签名而不是1个签名?它们之间有什么区别, 确定要使用的签名的标准是什么? 解决方案 elki wiki中有一个howto页面:本质上,您必须使用-db.index添加索引.然后,如果索引支持距离度量,则将自动使用. r*-tre似乎是最强大的.还有一个有关添加R-Tree索引支持的教程: htt
42 2023-05-15
编程技术问答社区
记录添加到空间层后,Neo4J的性能大幅下降
因此,我想添加到空间层中约有7000万个空间记录(我已经用一个小集进行了测试,并且一切都很顺畅,查询返回与PostGIS相同的结果,并且该图层操作看起来不错) 但是,当我尝试将所有空间记录添加到数据库中时,性能迅速降低,以至于它在500万次(约2h运行时间)的记录左右速度确实很慢,并且挂在约770万(8小时)./p> 由于空间索引是使用图形结构来构建本身的rtree,所以我想知道为什么当数字OS记录增加时会降级. 如果我没记错的话,rtree插入是o(n),这就是为什么我担心的是边界框的重新排列之间的某些东西,不是树叶的节点,而不是造成addtolayer过程会随着时间而变慢的树叶. . 当前我会在这样的图层中添加节点(许多硬编码的东西,因为我试图在模式和代码样式之前找出问题): Transaction tx = database.beginTx(); try { ResourceIterable layerNodes = Globa
48 2023-04-20
编程技术问答社区
在matlab中实现R-tree
请,任何人告诉我我们如何在MATLAB中实现R-Tree结构以加快图像检索系统的速度,我想通知您,我的数据库空间是颜色直方图(多维)的特征向量(多维),我也有相似性度量的距离向量... 谢谢 解决方案 我不使用MATLAB.因此,我不知道与索引结构的MATLAB中有多少成本.它似乎不是为这些事情而设计的. r-树似乎有很大的不同.从 A>某些算法可以从具有良好的索引结构中受益匪浅.该网页上的数字在110250图像颜色直方图数据集上快5到7倍. 根据我的经验,R-Trees确实很难正确.但是,只有您想全力以赴.如果您有 static 数据库,则可以轻松地使用 bumb laded r-tree.散装加载和查询都不难.一旦您想通过复杂的拆分策略,重新插入,平衡并与智能缓存进行所有这些有效和盘子的操作,R-Trees会变得凌乱.但是,只要您在内存中操作并且不动态添加对象,则加载的R-Tree将有很多帮助,并且更容易实现. 您可能仍然更好地建立已经有效的R-Tre
150 2023-04-04
编程技术问答社区
C++空间索引库:从/到磁盘加载/存储主内存RTree
我在以下方式的帮助下创建了一个主内存r*索引(dbStream实现了散装界面的接口) // creating a main memory RTree memStorage = StorageManager::createNewMemoryStorageManager(); size_t capacity = 1024; bool bWriteThrough = false; fileInMem = StorageManager ::createNewRandomEvictionsBuffer(*memStorage, capacity, bWriteThrough); DBStream dstream(streets); tree = RTree::createAndBulkLoadNewRTree(SpatialIndex::RTree::BLM_STR, dstream, *fileInMem, fillFactor, indexCapacity,
140 2023-03-02
编程技术问答社区
Boost R-tree是否支持分层遍历?
It seems that the r-tree 在Boost中不支持层次结构. 要具体,我想获得r-tree的root节点,然后获取节点的孩子. Boost R-Tree支持层次结构遍历? 解决方案 以防这是XY问题.您想做什么? 关于您的问题.用户定义的树遍历不受正式支持.但是,如果您不喜欢在内部挖掘,那么您可以写自己的节点访问者,例如: 并这样使用: https://github.com/boostorg/geometry/blob/develop/include/boost/goost/geometry/index/detail/rtree/rtree/rtree/print.hpp.l200
32 2023-03-01
编程技术问答社区