标签: spatial-index

在研究粒子相互作用的模拟时,我偶然发现Morton-order(Z-order)(维基百科链接)中的网格索引,这被认为是提供有效的最近邻细胞搜索.我读过的主要原因是内存中空间紧密单元的几乎顺序排序.

处于第一个实现的中间,我无法围绕如何有效地实现最近邻居的算法,特别是与基本的统一网格相比.

1. 给定单元(x,y),获得8个相邻单元索引并计算相应的z索引是微不足道的.虽然这为元素提供了恒定的访问时间,但是要在预定义的表中计算或查找z-index(对于每个轴和OR'ing分开).这怎么可能更有效率？是否正确,按顺序访问数组A中的元素说A [0] - > A 1 - > A [3] - > A [4] - > ...比A顺序更有效[1023] ] - > A [12] - > A [456] - > A [56] - > ......？

2. 我预计存在一种更简单的算法来查找z次序中的最近邻居.顺便说一句:找到邻居的第一个单元格,迭代.但这不可能是真的,因为这只能在2 ^ 4大小的块内很好地工作.然而,存在两个问题:当小区不在边界上时,可以容易地确定该块的第一个小区并且遍历该块中的小区,但是必须检查该小区是否是最近邻居.当细胞位于边界上时,情况更糟,而不是必须考虑2 ^ 5个细胞.我在这里错过了什么？是否有一个相对简单而有效的算法可以满足我的需求？

第1点中的问题很容易测试,但我不太熟悉所描述的访问模式生成的基本指令,并且非常希望了解幕后发生的事情.

在此先感谢任何帮助,参考等...

关于第2点:我应该补充一点,我理解如何为R ^ d中的点云构建Morton有序数组,其中索引i = f(x1,x2,...,xd)是从逐位交织等获得的.我试图理解的是,是否有比下面的天真ansatz更好的方法来获得最近的邻居(这里是d = 2,"伪代码"):

// Get the z-indices of cells adjacent to the cell containing (x, y) 
// Accessing the contents of the cells is irrelevant here
(x, y) \elem R^2 …

我正在进行植绒boids仿真,只是为了好玩,我想稍微优化一下.需要工作的区域是在给定的boid附近找到boids.我认为要做到这一点,某种适合任务的空间数据结构将是我最好的选择(见这里并向下滚动一下.).

无论我采用什么,我都会用Java从头开始实现自己.这样我就可以学到更多关于我选择的数据结构的知识,而不是我刚才调用的一堆库函数.

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

请为此推荐一个数据结构(当然不限于上述内容),并给我一个很好的理由选择它.

是的,我已经看到了这个问题.不,我对答案不满意 - 根本没有任何理由.

哦,另外一件事 - 就像标题所说的那样,这仅仅是针对两个维度的.

好的,所以我正在尝试安装libspatialspatialindex到我的Ubuntu机器python.我确实按照所有说明libspatialindex1_1.4.0-1.1_amd64.deb从http://packages.ubuntu.com/lucid/libspatialindex1下载并下载了amd64版本,因为我的机器是64位机器.我安装它然后跳转到Rtree python https://pypi.python.org/pypi/Rtree下载并在python中安装Rtree.我按照文件夹中install.txt文件中给出的安装说明进行操作.它说运行本地setup.py $ python setup.py install我也做了,但我得到的是

`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 <module>
import rtree
File "/home/neelabh/Desktop/Rtree/rtree/__init__.py", line 1, in <module>
from .index import Rtree
File "/home/neelabh/Desktop/Rtree/rtree/index.py", line 6, in <module>
from . import core
File "/home/neelabh/Desktop/Rtree/rtree/core.py", line 110, in <module>
rt.Error_GetLastErrorNum.restype = ctypes.c_int
File "/usr/lib/python2.7/ctypes/__init__.py", line 378, in __getattr__
func = self.__getitem__(name)
File "/usr/lib/python2.7/ctypes/__init__.py", line 383, in __getitem__
func …

为什么这不会返回每个社区(边界框)中的点数计数？

import geopandas as gpd

def radius(points_neighbour, points_center, new_field_name, r):
    """
    :param points_neighbour:
    :param points_center:
    :param new_field_name: new field_name attached to points_center
    :param r: radius around points_center
    :return:
    """
    sindex = points_neighbour.sindex
    pts_in_neighbour = []
    for i, pt_center in points_center.iterrows():
        nearest_index = list(sindex.intersection((pt_center.LATITUDE-r, pt_center.LONGITUDE-r, pt_center.LATITUDE+r, pt_center.LONGITUDE+r)))
        pts_in_this_neighbour = points_neighbour[nearest_index]
        pts_in_neighbour.append(len(pts_in_this_neighbour))
    points_center[new_field_name] = gpd.GeoSeries(pts_in_neighbour)

每个循环都给出相同的结果.

第二个问题,我怎样才能找到第k个最近的邻居？

有关问题本身的更多信息:

• 我们正在以非常小的规模进行这项工作,例如华盛顿州,美国或加拿大不列颠哥伦比亚省

• 我们希望尽可能多地使用geopandas,因为它类似于pandas并支持空间索引:RTree

• 例如,sindex这里有方法最近,交叉点等.

如果您需要更多信息,请发表评论.这是GeoPandasBase类中的代码

@property
def sindex(self):
    if not self._sindex_generated:
        self._generate_sindex()
    return self._sindex

我试过理查德的例子,但它没有用

def radius(points_neighbour, points_center, new_field_name, r):
    """
    :param points_neighbour:
    :param points_center: …

我们有一个x,y对的列表.每对代表2D空间上的一个点.我想找到这个列表中最接近的点,到特定点xq,yq.针对此问题的最佳性能关键算法是什么？点的Lisp不会改变; 这意味着我不需要执行插入和删除.我想在这个集合中找到目标xq,yq点的最近邻居.

编辑1:谢谢大家!正如Stephan202猜对了,我想反复这样做; 像一个功能.列表不一定排序(实际上我不明白它是如何排序的？就像一个主键为2列a和y的表？如果有帮助那么我会对它进行排序).

我将基于列表构建一次数据结构,然后我将在函数中使用此生成的数据结构(如果此过程本身是相关的).

谢谢Jacob; 似乎KD-Tree数据结构是一个很好的候选者(我觉得它是.我会在得到一些相关结果时更新).

编辑2:我发现,这个问题被命名为"最近邻居"!

编辑3:第一个标题是"寻找算法(用于空间查询和空间索引)(最近邻)"; 我选择了一个新标题:"解决最近邻居的最佳性能关键算法".因为我不想对我的初始数据执行插入和删除操作,并且我只想从它们中最近的一个到新点(不会被插入),所以我选择(当前)处理KD-Trees.谢谢大家!

我有一个大表(> 50米行),其中包含一些带有ID和时间戳的数据:

id, timestamp, data1, ..., dataN

...打开多列索引(id, timestamp).

我需要查询表以选择具有特定ID的所有行,其中时间戳在两个日期之间,我目前正在使用:

SELECT * FROM mytable WHERE id = x AND timestamp BETWEEN y AND z

目前在高端机器上需要2分钟(2x 3Ghz双核Xeons w/HT,16GB RAM,RAID 0中2x 1TB驱动器),我真的很想加速它.

我发现这个提示建议使用空间索引,但它提供的示例是IP地址.然而,速度增加(436s到3s)令人印象深刻.

我如何使用时间戳？

我(我认为)是一个简单的Sql Server空间查询:

抓住存在于某些4边多边形内的所有美国州(即网页的google/bing地图的视口/边界框)

SELECT CAST(2 AS TINYINT) AS LocationType, a.Name AS FullName, 
    StateId, a.Name, Boundary.STAsText() AS Boundary, 
    CentrePoint.STAsText() AS CentrePoint
FROM [dbo].[States] a
WHERE @BoundingBox.STIntersects(a.Boundary) = 1

运行需要6秒钟:(

这是执行计划....

删除

过滤操作的统计数据......

删除

现在,我只是不确定如何调试这个..弄清楚我需要微调等等.我有任何空间索引吗？我相信是这样 ...

/****** Object:  Index [SPATIAL_States_Boundary]    
        Script Date: 07/28/2010 18:03:17 ******/
CREATE SPATIAL INDEX [SPATIAL_States_Boundary] ON [dbo].[States] 
(
    [Boundary]
)USING  GEOGRAPHY_GRID 
WITH (
    GRIDS =(LEVEL_1 = HIGH,LEVEL_2 = HIGH,LEVEL_3 = HIGH,LEVEL_4 = HIGH), 
    CELLS_PER_OBJECT = 1024, PAD_INDEX  = OFF, SORT_IN_TEMPDB = OFF, 
    DROP_EXISTING = OFF, ALLOW_ROW_LOCKS  = ON, …

背景

我有一个表格包含代表客户区域的POLYGONS/MULTIPOLYGONS:

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

这是一个简化的查询,将重现我遇到的问题:

DECLARE @point GEOGRAPHY = GEOGRAPHY::STGeomFromText('POINT (-76.992188 39.639538)', 4326)

SELECT terr_offc_id
FROM tbl_office_territories
WHERE terr_territory.STIntersects(@point) = 1

看起来像一个简单,直接的查询需要12或13秒才能执行,对于这样一个简单的查询来说,这似乎是一个非常复杂的执行计划.

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

减少多边形

从美国人口普查数据导入的领土多边形似乎有可能是不必要的复杂,因此我创建了第二列,并测试了具有不同程度公差的缩小多边形(带有Reduce()方法).对新列运行与上面相同的查询会产生以下结果:

• 没有减少:12649ms
• 减少10:7194ms
• 减少20:6077ms
• 减少30:4793ms
• 减少40:4397ms
• 减少50:4290ms

显然朝着正确的方向前进,但精确度下降似乎是一个不优雅的解决方案.这不是索引应该是什么？对于这样的基本查询,执行计划似乎仍然很复杂.

空间索引

出于好奇,我删除了空间索引,并被结果震惊:

1. 没有索引时查询速度更快(sub 3 sec w/no reduction,sub 1 sec with reduction tolerance> = 30)
2. 执行计划看起来很远,更简单:

我的问题

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

其他说明

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

我有~400k兴趣点存储在GEOGRAPHY spatial sql中.

我将使用PointOfInterest.STDistance(@CentralPoint)<@Radius查询这些点,以在发送给查询的@CentralPoint 的某个半径内找到PointOfInterest.

我已经阅读了一些关于网格分层的内容,并希望有人知道他们的东西,推荐最明智的网格模式.默认是

LEVEL_1 = MEDIUM,LEVEL_2 = MEDIUM,LEVEL_3 = MEDIUM,LEVEL_4 = MEDIUM

但我的情况是,我只会 在英国境内有兴趣点.虽然很棒,但我们只采用了相关的terra firma规范,所以我想知道在这种情况下是否有更好的网格模式用于空间索引.

基于地理我不能使用可爱的几何边界框.此外,我使用的SQL Azure似乎没有空间帮助存储过程:(

首先,这是我的堆栈描述: 

• GrapheneDB + Neo4j Spatial插件上的Neo4j 2.3.0 0.15
• Ninja Framework 5.2.1我的电脑上的java服务器
• Neo4j-OGM 1.1.3用于实体映射
• Geotools 14.0用于geostuffs
• 用于REST查询的ApacheHttp

我有单位节点,它们使用属性"position"进行地理定位.位置是几何(POINT,CIRCLE或POLYGON).

我在这个属性上创建了一个图层和一个索引.我可以添加一个地理位置单位.这很好用.这是我之前的问题,我解决了它,因为它隐藏了真实的问题.

现在,我需要定义一些其他地理对象,如"path","detectionZone"或"actionZone".操作通常是"哪个其他单位在行动区？" 或"单位路径穿过检测区域？"

我如何索引这些数据？每个房产的一个指数？或者"wkt"属性的索引和用于检测区域,动作区域和路径的新节点,具有wkt属性？

我是否需要为每个地理概念创建一个图层？或者是一个独特的"geom"图层,它将所有与空间相关的节点分组？