是否可以在P2P网络中进行空间搜索？

我想建立一个基于Javascript/HTML5地理定位的社交网络，我想知道可能的架构的最佳选择。客户端 - 服务器可以很容易开发，但缺点是系统资源可能非常高，尤其是因为应用程序必须管理移动（最坏的情况：汽车中的用户必须看到汽车周围的其他用户）。是否可以在P2P网络中进行空间搜索？

Basicaly，在客户端 - 服务器架构，服务器任务将是：

收集并存储纬度和用户的经度（可能有几千条）
使地理距离搜索该用户（获取用户在他周围的用户列表）
建立并向客户端发送用户在列表中的位置的XML文件

这3个操作必须定期进行，每3或5秒进行一次，因为我需要一张“活”地图，显示列表中的用户在他们的环境（城市，城镇）中移动。

所有这3点可以优化：

客户移动10米时，以减少的数据的量来处理
“球形矩形”中MyISAM表与空间索引搜索发送他的位置（使用MBRContains）来卸载MySQL数据库。
公共输出文件：如果2个用户位于x米半径内（2个用户彼此靠近），则发送的XML可以相同。

很难使负荷估计在这个阶段，但我认为，客户端 - 服务器架构是不适合这种类型的应用程序和peer2peer的可能是一个很好的答案，如果当它们相互靠近2个客户端可以通信。

我的观点是：

是否有任何梅索德使可能的客户到位于某一半径没有中央服务器的帮助下盲目搜索其他客户端？（它可能与UDP广播:-)

编辑：更正。 UDP Brodcast允许客户机在任何地方，某个范围或IP地址中轮询机器。

感谢你的帮助，弗洛朗

来源

2012-02-19 Flo

我GOOGLE“搜索空间P2P”，发现这两个研究（它看起来是非常复杂的空间算法和我将尝试使用基本的客户端/服务器架构进行操作）。 http://www.springerlink.com/content/9r6wl93g52bg6c75/ http://www.ijcaonline.org/archives/number15/315-483 – Flo 2012-02-19 20:14:54

-1

你必须有中央的同行/服务器，因为你需要集中一些信息，以便能够执行你的功能。

我会去如下：

指定平方英里（或任何你想要的大小）到特定的服务器。
是否有设备发送一个'我在这里'的消息及其坐标给一些调度员，他们会将这些消息转发到正确的平方英里服务器进行处理。
服务器在设备进入他们管理的平方英里时注册。这可能是确保设备注册到一个且仅一个方格的中心地图。
将此消息转发给广场上的所有其他设备。
并且/或者确保您包含此消息的用途，并确保设备在将其显示给用户之前对其进行检查。

调整广场的大小和'我在这里'的消息率。而已。

来源

2012-03-11 00:28:58 JVerstry

很抱歉的批评，但是这是一个PRACTIC开发商的典型速战速决答案它说“为什么我应该花时间思考我什么时候可以花时间进行开发”，不幸的是这是行业所付出的代价。通过这种方式，您最终将得到一个与Oracle紧密结合的解决方案或其他一些通用技术，这将有助于以远远不能满足的方式降低任务的复杂性。有更优雅的解决这个问题，允许找到节点的邻居在O（日志（N））啤酒花 – Lu4 2012-04-07 23:23:43

@ LU4这是一个笑话？您如何将地理位置与Kamdelia距离连接起来？这些完全不同。 Kamdelia距离是一个抽象的数学概念，与真实的地理位置距离无关。你根本不理解这个问题。你没有将抽象与现实联系起来。 – JVerstry 2012-04-08 14:09:19

@JVestry你的现实并不真实。你打算使用的一个中央服务器解决方案是一个严密的瓶颈，它是失败的根源和万恶之源。想象一下，它会下降，整个P2P网络将停止工作。如何在您的架构中解决可扩展性问题，需要多少成本来扩展？安全性如何，防止黑客入侵有多安全？ JVestry我不想冒犯你，但你的解决方案是一个痛苦的屁股，就像行业解决方案一样，你的钱不是为了帮助你解决问题。 – Lu4 2012-04-09 10:40:50

-1

答案实际上取决于很多事情，所以我会帮助基本策略。要理解事情，您需要了解Kademlia如何工作（Kademlia是一个存储信息的DHT P2P网络）。

在Kademlia第一次启动时，每个节点选取一个随机ID，这是一个160位数字，代表所有可能的160位ID空间中的一个点。

的需要被存储的与SHA-1函数（它接收任意字符串，并且输出等的需要被存储的信息ID处理160位的数目）

获得的信息的ID之后，您将获得信息的ID，然后将其发布，信息将物理存储在ID接近信息ID的节点上。

（插图从here截取）

enter image description here

的信息被通过查询它的ID。信息查找或节点查找都需要O（log（N））跳来获取所需的信息。在Kademlia中使用“XOR”度量（在您的情况下，它可以是普通的欧几里德度量）。

每个节点都维护一个存储桶阵列，每个存储桶包含适合当前存储桶的节点地址。 “恰当”是衡量身份证多近的标准。考虑例如：

  0        160 
Node 1 ID: 1101000101011111101110101001010... 
Node 2 ID: 1101011101011111101110101001010... 
Node 3 ID: 1101000101011001101110101001010...

施加XOR度量的节点＃1,2之后即（计算表示这些节点之间的虚拟距离的数量），我们得到：

index -
xor - 000001100000000... (the difference is in 5-th msb bit) 
order - msb   lsb

施加异或度量节点之后＃1,3我们得到：

index -
xor - 000000000000011... (the difference is in 13-th msb bit) 
order - msb   lsb

显然节点1更接近节点3，因为它具有比来自节点1的距离更小显著比特差到节点2并且因此从一个PO int节点1的视图中，它的邻居节点3转到第13个存储桶（较高的索引表示更近的ID），并且节点2转到第5个存储桶，其中包含一组距离一个5 MSB基数的节点当前节点ID。

这样的数据结构允许每个节点知道它在各种距离的160个级别中的环境。

回到您的示例，为了允许高效的地理空间查询，您需要用普通欧几里德度量替换Kademlias XOR度量。在这种情况下，你有你自己的ID为3D或2D向量，不幸的是由于事实与浮动它们不能直接适用于这种类型的算法的点数，所以你需要将它们转换成离散的二进制数欧几里德的度量结果以某种方式类似于XOR功能的方式。之后，找到节点的相邻节点是一件小事。

希望这会有所帮助。哦，通过外观HyperDex的方式，新的搜索分布式档案系统紧密联系在一起的欧几里德度量，可以帮助...

来源

2012-04-08 00:45:43 Lu4

你如何连接地理定位与Kamdelia距离？这些完全不同。 Kamdelia距离是一个抽象的数学概念，与真实的地理距离无关。 – JVerstry 2012-04-08 14:10:01

键之间的距离是一个数字，地理位置之间的距离也是一个数字。你应该采取Kademlia的概念，把键换成地理位置，Xor度量到Euclidian度量，你将会像一头大象一样快乐。 – Lu4 2012-04-09 10:47:25

尤达，告诉我在Kamdelia键和地理位置之间做映射的算法。做实际的实施，并在原始问题中将解决方案插入到问题中。在途中，你会学到一些东西。到目前为止，你只是在天空中抽烟......它会让你的头旋转！得到真实！ – JVerstry 2012-04-09 12:06:43

是否可以在P2P网络中进行空间搜索？

回答

相关问题