Accepted by NDBC 2018
高效的空间大数据分布式拓扑分析算法 Efficient Distributed Big Spatial Data Topology Analysis Algorithm
Abstract: Rapidly growing spatial data and the increasing demand for application have put forward higher requirements for spatial topology analysis algorithms, such as high concurrent real-time request processing and massive data topology analysis. The existing stand-alone or multi-cores space topology analysis algorithm to deal with spatial data is inefficient. We propose an efficient big spatial data distributed topology analysis algorithm. The space-filling curve is used to divide the complex spatial objects into subspace objects. Each sub-space-object has a unique number, CellId. A pre-judgment algorithm is proposed that uses the CellId’ spatial information to filter the redundant data and reduce the data in topological analysis. Experiments show that this algorithm can efficiently process the topological analysis of massive spatial data. It is superior to existing stand-alone and multi-core algorithms in most cases, and has a linear acceleration ratio.
Key words: spatial database; topology analysis; distributed computing; data division; space fill curve
摘 要: 迅猛增长的空间数据和日趋旺盛的应用需求，对空间拓扑分析算法提出了更高的要求， 如高并发 请求实时处理、 海量数据拓扑分析。 现有空间拓扑分析算法针对单机或多核设计，处理空间大数据效率不 高。本文提出了一种高效的空间大数据分布式拓扑分析算法。 利用空间填充曲线将复杂的空间对象划分为 子空间对象，每个子空间对象拥有唯一网格编号； 提出一种预先判断机制，利用网格编号包含的局部空间 信息过滤冗余数据，减少拓扑分析的数据量。 实验表明，该算法可以高效的处理海量空间数据拓扑分析， 在绝大多数情况下优于现有单机和多核算法，且具有线性加速比。
关键词: 空间数据库； 拓扑分析; 分布式计算; 数据划分; 空间填充曲线
BBox（边缘矩形，粗略表示曲线和区域），Segment（线段，详细表示曲线与区域），这两个数据结构类似
Curve（曲线），Region（区域，可以看作封闭曲线）先不管Region
LineDetail，RegionDetail L1.Points L2.points -> Map -> p台机器，线段L1，L2相同cellId的点(也就是可能交点)就在同一个机器上 -> Reduce -> 交点/null
如何分布式： 1 以求两条线段L1,L2交点为例： 读取curveDetail.pointNums，根据cellId，将两条线段的点映射到p台机器上， 每台机器上就有Map<cellId_n, list> L1Map 和 L2Map,判断后返回交点或者null。long 8B，double 8B，一个点32B；1000KM长的线段，按照1m一个点，1000 000个点，1000 000 * 32 B = 32MB，这种情况可以不需要分布式
2 以一条线段与多条已知线段求交点集合为例: 长途货车穿越哪些乡镇 乡镇的位置信息是提前确定的，货车路线每时每刻不同。乡镇的信息数据量大，需要分割后存储在p台机器中，货车的路线分割后放入不同台机器，就真分布式了。
只有2这种情况，多条线/区域求交点，数据量大，才需要分布式
rawData -> curve/region -> pointSets
rawData1 { List<(double x, double y)}> type // 曲线还是区域还是其他 }
curve/region { public long curveNum; public CellId cellId; public List divisionPointSetNums; // 第一次划分 }
pointSet { private long pointSetNum; private long inheritNum; private CellId cellId; public List divisionPointSetNums; // 可以继续划分，多次划分（pointSet划分为多个子pointSet，这里存储pointSetNum） private List points; // 可以为空，即具体点的信息存储在divisionPointSetNums的points里面 }
原始数据利用 cellId 划分到一个个 pointSet，存储在机器中
1 建立数据库
2 对于输入的线段，分割存储在内存/数据库中
3 输入curveNum，得到这条线段的所有信息
1 全库分析，输出报表（交点个数）
long getReportIntersection()
{
//计算交点，将所有点写入文件intersection.txt
//返回交点个数
}
2 输入线段，分析该线段与数据库信息的拓扑关系（相交，包含等）
//单个处理
List<Point> calculateIntersection(Curve curve)
{
List<Point> res = new ArrayList<>();
//划分curve为多个PointSet
//对每个pointSet，求交点
return res;
}
//批处理
List<List<Point>> calculateIntersection(List<Curve> curves)
{
List<List<Point>> res = new ArrayList<>();
//划分curve为多个PointSet
//对每个pointSet，求交点
return res;
}
Boolean calculateIntersectionToFile(List<Curve> curves)
{
//划分curve为多个PointSet
//对每个pointSet，求交点
//写入文件
}
3 进入某个区域的点（已知点的轨迹和区域的范围，找出所有轨迹进入到区域内的点 -> 现实场景：某城市净流入人口，净流出人口）
public static void getPointInRegion(Region region)
{
//划分region
//查找与之相交的线段（轨迹）
//判断交点状态（流入，流出，相切）
//统计保存结果
}
1 全库展示
2 输入curveNum，展示该线段
3 展示拓扑分析结果（显示交点，包含关系等）