我想编写一个地理处理任务，以查找所有价值在x y英尺以内的x $ /英亩的宗地。另一个价值小于z $ / acre的地块。
我想制定和运行此查询，而又不知道或不关心数据分布在50台计算机上。请记住边界条件：我还希望查询返回一种状态下的昂贵包裹接近另一种状态下的廉价包裹的情况。
是否有一种支持这种分布式地理处理的体系结构？
可以抽象地描述该体系结构，也可以将其描述为Azure或Amazon Web Services的特定实现。或者，最好将其作为典型的办公室，使计算机在夜间拥有大量ArcGIS桌面许可证而闲置。
#1 楼
将所有包裹存储在一个中央数据库中
在美国上形成一个网格，该网格由一侧为N英尺的正方形组成，其中N表示适合N的包裹数不会耗尽内存在您的一个节点上
在数据库中创建一个表，每个网格正方形一行，一个id列，一个几何列和一个状态列
每个节点运行一个小的程序，该程序
找到下一个未处理的正方形
将其标记为正在处理中的
将所有地块ST_DWithin（square，parcel，maxfeet）
进行实际查询中央数据库中的解决方案表
将正方形标记为完整
返回到1
显而易见的失败案例是您的半径对宗地查询的兴趣变得足够大，以至于数据集中的大部分都可以匹配每个宗地。
评论
感谢Paul，我需要一个节点充当其他节点的协调者吗？
– Kirk Kuykendall
2010-10-26 14:33
数据库充当隐式“协调器”，因为它保留队列的状态，但是除了启动并指向数据库外，不需要协调节点。不知道这是否是答案。
– Paul Ramsey
2010-11-5 14:02
#2 楼
9月，在巴塞罗那的FOSS4G上有一个有趣的插槽，它是这样的：而不是演示。保罗·拉姆西（Paul Ramsey）在这篇博文的中间对此做了一些总结。
评论
看起来很有希望，他们是否将演示文稿张贴在任何地方？
– Kirk Kuykendall
2010-10-25 13:03
好吧，由于Schuyler Erle成为了小组讨论的主持人，而不是主持计划的演讲，所以我认为不会有更多的信息。但是，由于Erle计划了这次演讲，他可能已经掌握了一些信息。如果您进行Google搜索，他无处不在。直接问他可能是个主意。我不知道。大多数讨论超出了我的理解范围，因此我无法提供比Paul在其博客中更好的简历。
–尼克拉斯·阿文（NicklasAvén）
2010-10-25 16:23
#3 楼
也许可以看看esri白皮书中的白皮书“ ArcGIS Server in Practice Series：大批量地理编码”。它是关于地理编码的，但是使用异步地理处理服务的一般过程可能适用于您的情况。
评论
看起来不错，我想知道这是否可以推广到其他形式的地理处理。似乎我需要在数据集之间重叠。
– Kirk Kuykendall
2010-10-25 13:11
#4 楼
与该问题有关的第一件事是何时何地需要什么数据。为此，我通常从问题的愚蠢的串行版本开始。查找所有价值x x /英亩的地块，该地块在另一个价值小于z $的地块的y英尺内。 / acre。
foreach p in parcels {
if value(p) > x {
foreach q in parcels {
if (dist(p,q) <= y) and (value(q) < z) {
emit(p)
}
}
}
}
虽然该算法未优化，但可以解决问题。
我为硕士论文解决了类似的问题在数据集中找到每个点最近的地块。我在PostGIS，Hadoop
和MPI中实现了该解决方案。我的论文的完整版本在这里，但是我将总结适用于此问题的要点。
MapReduce并不是解决此问题的好平台，因为它需要访问整个数据集（或精心挑选的子集）来处理单个包裹。 MapReduce不能很好地处理辅助数据集。
MPI可以很方便地解决此问题。最困难的部分是确定如何拆分数据。拆分的依据是：有多少数据，必须运行多少p
处理器以及每个处理器有多少内存。为了达到最佳缩放比例（并因此获得最佳性能），您将需要一次在内存中（跨所有计算机）拥有宗地数据集的多个
副本。
为了解释其工作原理，我将假设您的50台计算机中的每台都具有8个处理器。然后，我将指派每台计算机负责检查包裹的1/50
。该检查将由计算机上的8个进程执行，每个进程都具有相同地块的1/50部分和
地块数据集的1/8的副本。请注意，这些组不仅限于一台机器，还可以跨越机器边界。从第1/8集开始的q的包裹。后内部
循环，同一台计算机上的所有进程将一起讨论以确定是否应发出包裹。
针对我的问题，我实现了与此类似的算法。您可以在此处找到源。
即使使用这种非优化算法，我也可以获得令人印象深刻的结果，这些结果针对程序员的时间进行了高度优化（这意味着我可以编写一个愚蠢的简单算法，并且计算速度仍然足够快） 。要优化的下一个位置（如果确实需要）是为每个过程设置第二个数据集（从中获取q）的四叉树索引。
回答原始问题。有一个体系结构：MPI + GEOS。从我的ClusterGIS实施中获得一点帮助，可以做很多事情。所有这些软件都可以作为开源软件找到，因此无需任何许可费用。当我在linux上工作时，我不确定它对Windows的可移植性（也许与Cygwin兼容）。该解决方案可以部署在EC2，Rackspace或任何可用的云上。当我开发它时，我正在大学中使用专用的计算集群。
#5 楼
传统的并行编程方法是只存储一个状态+在每个处理器上触摸过的包裹，然后很容易进行并行化。但是，鉴于美国各州大小的差异，您可以通过将国家划分为网格单元（同样具有包裹性的光环），并使用主从配置将每个网格单元发送给处理器来获得更好的性能。评论
除了需要接触的宗地之外，我还需要y距离内来自相邻州的宗地。
– Kirk Kuykendall
2010-10-25 13:13
我认为Y足够小，因此不会比少数包裹大得多。如果是状态的很大一部分，那么最好使用任意网格进行计算。
–伊恩·特顿♦
2010-10-25 14:18
#6 楼
您可能想给Appistry看看。它旨在实现将现有应用程序迁移到私有云基础架构。可能还有其他一些目标相似的项目：不是为每个应用程序一遍又一遍地找出将任务分解并分配给并行处理的非常复杂的螺母，而是创建一个自动执行此任务的库或平台。评论
谢谢马特，这看起来确实很有希望。谷歌搜索，我从FedUC 2008议事录中找到了此演示文稿。esri.com/ library / userconf / feduc08 / papers /…我很想知道他们从那以后所做的工作的最新进展。
– Kirk Kuykendall
2010-10-26 14:13
#7 楼
对于此类问题，我将使用map / reduce框架。 “原始” Appistry框架非常适合解决这个“尴尬的并行”问题。边缘条件不允许这样做。 Map / Reduce（Google的分布式计算方法）非常适合此类问题。自08年论文发表以来，Appistry的最大进步就是CloudIQ Storage产品的发布。这样就可以利用本地服务器上的磁盘来实现类似“ s3”的存储功能。然后，CloudIQ Engine产品可以启用任何类型的高容量服务或分散/收集样式的应用程序（我们已经使用ESRI运行时和其他开放源代码库证明了可扩展性）。如果您正在处理基于文件的数据，则可以使用CloudIQ Storage将其分发出去，然后将处理作业路由到本地文件副本，这样就不必在网络上四处移动它们。 （因此每个节点都不需要所有数据）
对于Map / Reduce，您可以在CloudIQ Storage上分层放置诸如Hadoop（开源M / R框架）之类的东西。我将针对描述的问题查看Hadoop，但您确实需要深入研究，入门并不容易，M / R令人费解。 Cloudera还提供了商业支持的发行版。还有另外一个Appistry产品CloudIQ Manger，它是Hadoop（Cloudera或其他）的很好的补充，用于分发和管理。需要更受商业支持的可扩展解决方案，请与Apperatry CloudIQ Manager和Storage以及Cloudera Hadoop发行版一起使用。
如果您想要用于“繁琐的并行”任务的更简单架构，请同时查看CloudIQ Engine 。 （引用的Kirk论文中概述的方法仍然有效）
#8 楼
看看OGSA-DQP。 “ DQP允许使用SQL来查询来自多个分布式关系数据库的表，就像在单个数据库中有多个表一样。”http://ogsa-dai.sourceforge.net/documentation/ogsadai4.0/ ogsadai4.0-axis / DQPOverview.html
评论
好问题。在此特定示例中，您需要一种自动并行化空间数据结构（例如四叉树）的构建和使用的方法。如果您不这样做，而是仅对50台计算机进行暴力搜索，则实际上可能会降低查询速度而不是加快查询速度。我敢肯定，像这样的通用架构尚不存在，因此您可以通过首先考虑哪些类型的查询可能会从分布式处理中受益，然后研究所需的架构来获得更好的运气。也许将此问题发布到TCS网站上？@whuber谢谢，什么是TCS网站？
@柯克（Kirk）对不起，我很神秘-我很懒。 cstheory.stackexchange.com
CS的基本理论可能无济于事，因为CS的人很少获得空间:-)
@iant那里并没有太多的GIS人会对分布式计算的细节有所了解（我对这个站点的成员显然没有例外）不加思索。我相信TCS员工将有知识来回答有关体系结构存在的原始问题。我唯一关心的是他们是否会发现这个问题有趣！我认为，如果采取正确的方法，他们可能会这样做。 （例如，可能会根据数据结构对其进行重组。）