问题标签 [spatial-index]

我正在做一个植绒模拟，只是为了好玩，我想对其进行一些优化。需要工作的区域是在给定的 boid 附近寻找 boid。我认为要做到这一点，某种适合该任务的空间数据结构将是我最好的选择（请参阅此处并向下滚动一下。）。

无论我做什么，我都会用 Java 从头开始​​实现自己。这样一来，我将比仅调用一堆库函数了解更多有关我选择的数据结构的信息。

我知道R-Trees、kd trees和Quadtrees。在我看来，它们都是可行的选择。但我对这些数据结构没有任何经验，我不完全确定什么最适合我的目的。我不需要这种规模的任何东西——我说的可能是几百个，最多可能是一千，而不是一百万，尽管请记住，我最终可能最终会在 Android 手机上运行它。

请为此推荐一个数据结构（当然不限于上述），并给我一个选择它而不是替代方案的充分理由。

是的，我见过这个问题。不，我对答案不满意——根本没有给出任何理由。

哦，还有一件事——正如标题所说，这仅适用于二维。

背景

我有一个表，其中包含代表客户区域的 POLYGONS/MULTIPOLYGONS：

• 该表包含大约 8,000 行
• 大约 90% 的多边形是圆形
• 其余的多边形代表一个或多个州、省或其他地理区域。这些形状的原始多边形数据是从美国人口普查数据中导入的。
• 该表在主键上有一个空间索引和一个聚集索引。未对默认 SQL Server 2008 R2 设置进行任何更改。每个对象 16 个单元格，所有级别中等。

这是一个简化的查询，它将重现我遇到的问题：

看似简单、直接的查询需要 12 或 13 秒才能执行，并且对于这样一个简单的查询，执行计划似乎非常复杂。

在我的研究中，一些消息来源建议在查询中添加索引提示，以确保查询优化器正确使用空间索引。添加WITH(INDEX(idx_terr_territory))没有任何效果，从执行计划中可以清楚地看出，无论提示如何，它都在引用我的索引。

减少多边形

从美国人口普查数据导入的领土多边形似乎过于复杂，因此我创建了第二列，并测试了具有不同程度公差的缩减多边形（使用Reduce() 方法）。对新列运行与上述相同的查询会产生以下结果：

• 不减少：12649ms
• 减少10：7194ms
• 减少20：6077ms
• 减少 30：4793ms
• 减少 40：4397ms
• 减少50：4290ms

显然朝着正确的方向前进，但降低精度似乎是一个不雅的解决方案。这不是索引应该用于的吗？对于这样一个基本查询，执行计划似乎仍然异常复杂。

空间索引

出于好奇，我去掉了空间索引，结果惊呆了：

1. 在没有索引的情况下查询更快（低于 3 秒，不减少，低于 1 秒，减少容差 >= 30）
2. 执行计划看起来要简单得多：

我的问题

1. 为什么我的空间索引会减慢速度？
2. 为了加快查询速度，真的有必要降低我的多边形复杂性吗？降低精度可能会导致问题出现，并且似乎不会很好地扩展。

其他注意事项

• 已应用 SQL Server 2008 R2 Service Pack 1
• 进一步的研究建议在存储过程中运行查询。试过这个，似乎没有任何改变。

CREATE TABLE building (buildid VARCHAR(15) PRIMARY KEY, buildname VARCHAR(50),numpoint NUMBER,points SDO_GEOMETRY);

CREATE INDEX building_spatial_idx ON building(points) INDEXTYPE IS MDSYS.SPATIAL_INDEX;

INSERT INTO USER_SDO_GEOM_METADATA(TABLE_NAME,COLUMN_NAME,DIMINFO,SRID) VALUES ('building', 'points', SDO_DIM_ARRAY(--820*580 grid SDO_DIM_ELEMENT('X', 0, 820, 1), SDO_DIM_ELEMENT('Y', 0 , 580, 1) ), 空 --SRID );

当我第一次执行它时，它没有给出任何错误，但后来它给出了错误

或者还有什么其他原因。如何一次删除所有索引、元数据、表并删除此错误。

我们正在尝试更新我们的 WiX 安装程序以安装 SQL Server 2008 R2。常规 2008 似乎在大多数机器上都可以正常安装，但R2 安装似乎无法安装 SQLSysClrTypes - 所以我们遇到了一个错误，即缺少名为 SQLServerSpatial.dll 的 dll。

有没有办法让 SQL 安装程序正确安装它？我在网上找到了一些关于这个问题的讨论，但没有解决方案，除了在 SQL Server 之后手动安装 SQLSysClrTypes.msi。

我们希望安装是静默的，并且需要最少的用户交互。

我们正在使用 WiX 3.5 和 VS2010。

编辑

进一步的阅读和思考让我了解到 SQL 2008 SP1 也没有安装 SQLServerSpatial.dll，现在是对我们的代码所做的更改才要求这样做。所以我的问题变得更简单了：

我可以将 SqlServer 安装配置为包含/安装 SqlServerSpatial 吗？

或者

我可以使用 WiX 安装 SQLSysClrTypes.msi（我需要 package.xml 和 product.xml）吗？有人做过吗？

我有一个表，其中包含一组约 40k 行的样本，每行包含一个点（经度和纬度）。我正在使用 MySQL 的空间扩展来查找边界内存在哪些点。

如果我在我知道结果很少的边界内搜索，则按应有的方式使用索引。但是，我的测试数据集主要由英国各地的位置组成（更大的实时数据集在百分比上可能相似）。当我在这个边界框内搜索时，没有使用索引，而是执行了全表扫描：

因此，当它期望找到的行数接近总行数时，似乎 MySQL 决定忽略索引。

是这样吗，如果是这样，我可以强制使用索引还是确保避免全表扫描？

使用以下

在 134 行（56 秒）上运行非常慢，但是，在未注释索引提示的情况下，它返回

消息 8635，级别 16，状态 4，第 3 行
查询处理器无法为带有空间索引提示的查询生成查询计划。原因：空间索引不支持谓词中提供的比较器。尝试删除索引提示或删除 SET FORCEPLAN。

执行计划显示过滤器成本为 98%，它查询另一个表中的 1400 行，因此总成本为 134 * 1400 次单独查找，这就是延迟所在。就其本身而言，每个表中的空间索引都表现出色，没有碎片，99% 的页面填充度，并且对所有 4 个网格级别使用中等，每个对象有 16 个单元格。更改任一表上的空间索引属性对性能没有影响。

文档表明空间索引提示只能在 SQL Server 2012 中的查询中使用，但肯定有解决方法吗？

我正在使用 MongoDB 来存储空间记录。有些记录是多边形，有些是点。不断插入数据。

我需要能够访问其多边形包含一个点的所有记录。Mongo 的空间查询允许查找多边形内的所有点，但不是所有包含点的多边形。在 MongoDB 另一个数据库系统中是否有一个好方法可以做到这一点？

我有大量与重要因素配对的 3d 点。

每个用户有六分。例如：人 Charlie 有 6 个点：(22,44,55) 是他的第一个点，重要性因子为 3，(10,0,0) 是他的第二个向量，重要性因子为 2.8，一直到他的第六点即 (100,300,200)，重要性因子为 0.4。

我想做的是找到与查理最相似的人，而无需遍历每个其他人。基本上为每个用户最小化这个函数（即，匹配从那个用户到查理的正确的六个点）：

然后通过选择成本最低的用户来找到与查理最相似的用户。我现在以愚蠢的方式编写了代码（通过执行大量循环），但我正在寻找一种方法来正确处理存在多个点和重要因素的事实。

我开始研究空间索引，但我认为它们不会起作用，因为我有多个点，但也许我可以将这些点展开为更高维度的点？所以不是 3 个维度的 6 个点，我可以有 18 个维度的 1 个点？仍然无法处理重要性因素，但总比没有好。

不幸的是，我不能在这里使用向量和余弦，因为 (1,1,1) 和 (400,400,400) 是完全相反的东西。

有任何想法吗？

我在二维空间中有一组不同大小的矩形。矩形的数量可以从 10 到 100 000 动态变化，它们的位置以及它们的大小经常更新。

你会推荐哪种空间结构在给定点 (x,y) 找到矩形？假设搜索操作也经常执行（例如鼠标移动）。如果您可以参考各种空间索引算法比较或在这里比较它们的搜索/构建/更新性能 - 那会很可爱。

我有一个大型查询，试图将质心与它们适合的多边形相匹配。虽然我确实通过块和多边形的 Z 值进行约束，但它仍然会进行大量的多点计算并且需要很长时间才能运行。

对于一些背景：

• 包含质心的表有 250 万行
• 表中的所有空间数据都在世界很小的一个区域内，整个事物的边界框只有 7643 x 2351 米
• 在这些行中，660K 适合符合 Z 标准
• 包含多边形的表有 10K 行
• 表中的所有空间数据都位于世界上更小的区域
• 在这些行中，有 2366 行符合名称标准
• 在没有任何索引的情况下运行查询需要 11 个小时并返回 91K 匹配项

查询是这样的：

因此，为了加快查询速度，我在blocks.WGS84Centroid和 上添加了一个空间索引polygons.Shape。
查询分析器还建议在 blocks.ZCentre 上使用非聚集索引，包括 blocks.Id 和 blocks.WGS84Centroid。

毕竟，这是查询计划：

和过滤器成本：

但是，在添加这 3 个索引之后，查询仍然需要同样长的时间才能运行。
我现在能做什么？