R^3(x,y,z)中快速随机访问和顺序访问的数据结构

Question

我想找到一种内存高效的数据结构，用于搜索 R^3 坐标的巨大网络（可能有 100,000-500,000 个坐标）。我查看了看起来不错的 k-d 树，是否有用于快速随机和顺序访问的良好数据结构？编程语言将是 C++ 或 C。我研究了 k-d - tree 和 R^*-tree 是否有一些更有效的数据结构？

id x y z

1 0.1 0.05 0.3

2 0.3 0.22 2.3

3 0.1 0.2 3.3

等等

Answer 1

这是如何最快速和记忆有效地通过所有这些点找到点的存在或用它来组织地图的方法。您需要为您的 3d 坐标 class 实现特殊的比较对象 http://ru.cppreference.com/w/cpp/utility/functional/less。根据您的访问要求，将其用作 std::map 或 std::vector 的模板参数。

template< class T >
struct My3DLess;
bool operator()(const T &lhs, const T &rhs) const
{
    return lhs.x < rhs.x && lhs.y < rhs.y && lhs.z < rhs.z;
}

typedef std::map<My3DPoint,MyMappedObject,My3DLess> My3DMap;

如果您的插入不像提取那样频繁，则需要使用矢量。您可以使用此排序插入功能：

typedef< typename T, typename Pred >
typename std::vector<T>::iterator
    insert_sorted( std::vector<T> & vec, T const& item, Pred pred )
{
    return vec.insert ( std::upper_bound( vec.begin(), vec.end(), item, pred ), item );
}

typedef std::vector<My3DPoint> My3DVector;
My3DVector my3DVector;

// inserting
insert_sorted( my3DVector, my3DPoint, My3DLess() );

// check existance
if ( std::binary_search( my3DVector.begin(), my3DVector.end(), my3DPoint, My3DLess() ) )
    { ... }

Answer 2

假设您需要在任意直角棱柱内搜索，您应该考虑八叉树。 Wiki 上有一篇文章，https://en.wikipedia.org/wiki/Octree

Answer 3

如果内存效率最重要，我会推荐 PH-Tree（我自己的实现）之类的东西。根据数据量和维度，与包含相同坐标（例如 10M 点和 >7 维）的普通 float[] 或 float[][] 相比，它需要 LESS space。对于 3 维，它需要更多 space，但仍然少于大多数其他数据结构。

它是 quadtree/octree 与 trie（前缀共享）和一些其他算法的混合，使其适合大数据和高维度。

额外的好处：支持非常快速的随机更新，它们几乎不需要比查找长的时间。查询速度与 R-Trees 等类似。

主要缺点：目前没有C/C++版本，只有Java版本。此外，代码非常复杂，需要一些工作来翻译。另一个缺点是 PH-Tree 有时对于小于 1,000,000 个点的小数据集有点慢；它可能会变得更快（！）并获得更多积分。

编辑顺序访问 return 是一种稳定的顺序。作为额外的好处，顺序访问和 window 查询 return 会导致 z 排序。但是，无法按 ID 排序。

R^3(x,y,z)中快速随机访问和顺序访问的数据结构

Data structure for fast random access and sequential access in R^3 (x,y,z)

c++

tree

data-structures