2. 浙江中海达空间信息技术有限公司, 浙江 湖州 313299;
3. 四川视慧智图空间信息技术有限公司, 四川 成都 610036;
4. 武汉大学测绘遥感信息工程国家重点实验室, 湖北 武汉 430079;
5. 四川省自然资源厅信息中心, 四川 成都 610072
2. Zhejiang Hi-Target Spatial Information Technology Co. Ltd., Huzhou 313299, China;
3. Sichuan Smart Map Spatial Information Technology Co. Ltd., Chengdu 610036, China;
4. State Key Laboratory of Information Engineering in Surveying, Mapping and Remote Sensing, Wuhan University, Wuhan 430079, China;
5. Information Center of Department of Nature Resources of Sichuan Province, Chengdu 610072, China
任务驱动的地理场景数据组织管理与传统GIS数据库端偏向于高效磁盘存储的组织管理不同，它更靠近应用端，以任务所需的形式在内存中存储和索引，是计算分析就绪的[1]。随着移动互联网、物联网和社交网络的快速发展，智慧城市中每时每刻将会产生海量异质且动态关联的多模态场景数据。这些动态的(人流、车流、物流)和关联的(社交网络、道路网络、语义网络)且随时间不断增长的多模态场景数据中蕴含着丰富知识和规律，亟需实时高效的处理、分析与展示，给现有的时空数据组织管理系统，尤其是时空索引算法设计带来了严峻挑战[2-3]。基于树结构的时空索引算法已经得到了广泛的研究，但这些算法大多基于外存，智能感知数据和关联关系数据实时接入，动态变化且规模巨大，致使时空索引结构发生剧烈变化，导致密集的磁盘I/O[4-5]。多模态场景数据索引算法还需要支持复杂的时空关联分析查询应用，例如行为模式挖掘，异常探测等[6-7]，因此，亟需一种高性能低延迟，且支持复杂的时空关系查询应用的多模态场景数据索引算法。
随着场景任务的综合性要求日益突出，混合时空索引成为一种发展趋势[8]。现有的支持智能感知数据的时空索引方法通常采用混合索引结构来提高数据组织和查询效率，满足多样化场景任务所带来的差异性数据访问与调度需求[9-13]。这些多层次混合的时空索引算法主要区别是其全局索引的设计，主要分为4类。①先空间后时间划分，即首先采用空间索引(如格网、四叉树)将数据划分到多个子区域，接着对子区域内的数据建立局部时间索引[14]。此类方法空间区域划分固定，索引构建和查询效率高，有利于提高数据并发访问效率，缺点是空间数据分布不均，容易导致数据访问倾斜。②先时间后空间划分，即采用一维索引(如B树及其变种)将数据划分为多个时间区间，接着对每个时间区间内的数据建立局部空间索引[9]。此类方法需要对每个时间版本都单独维护一个空间索引，维护成本高。此外，与第1类方法一样，都存在时空查询模式固定的问题，查询须按照划分策略才能得到效率保证[15-16]。③随机划分，即采用随机函数(如Hash函数)将数据打乱为多个子数据集，然后对每个数据集单独建立时空索引。这种做法有利于分布式存储与负载均衡，但是却破坏了数据的时空相关性，增加了时空查询磁盘I/O次数[17]。④降维，即采用填充曲线(如Z-order曲线)将时间信息、空间信息转换为一维字符串，实现时空降维查询，然后可以通过B树及其变种或者Hash实现快速检索[18]。这类做法的优点是降低了多维空间信息处理的复杂性，点对点查询效率高，缺点是填充曲线只能一定程度上在一维空间中保留多维空间中目标的聚集性，导致其范围查询效率不高[5]。
智能感知数据中蕴含的关联关系价值往往大于数据本身，在异常发现、知识探索中扮演着重要的角色。常见的关联关系组织管理方式主要分为两类。第1类是将时空维度关系和其他泛在关联关系分别管理，利用上述混合时空索引独立维护数据的时空关系信息，同时基于关系模型存储管理数据对象之间的其他泛在关联关系，数据的多维属性特征及其关系基于关系模型进行表达，通过主键和外键映射方式实现关系构建[19-20]。但是，在进行场景分析探索时，常需要基于SQL语句构建复杂的时空关联关系查询模式，并且频繁涉及多表的JOIN操作，效率低[21]。第2类是基于图网络构建智能感知数据及其载体之间的多层复杂网络或知识图谱，实现数据对象及其关联关系的一体化管理，但是由于其不支持频繁密集的动态更新且时空查询效率低，无法满足动态变化的智能感知数据实时接入与高性能低延迟计算分析的处理需求[22-24]。
场景任务复杂多样，任务所需的场景数据需要实时、高性能的分析处理，基于内存以一种面向任务所需，计算分析就绪的方式索引组织场景数据成为一种发展趋势[10, 25-26]。树结构常用于表达空间对象之间的拓扑关系，而图模型相较于树结构将拓扑关系扩展为了场景中更为普适存在的关联关系，更适合多层次复杂计算分析任务[1]。基于稀疏矩阵可以在低延迟的内存环境中高效地表达图模型中关联关系，并且借助于矩阵运算可以实现高性能的数据检索[27]。因此，本文提出一种基于稀疏矩阵的动态关联数据图索引算法，通过稀疏矩阵在内存中高效地组织场景数据之间的时间、空间、关联等关系信息，以解决现有的索引磁盘I/O密集、延迟高、时空查询模式固定且对关联关系支持弱的问题。
1 时空关系图索引 1.1 时空关系图索引的定义场景数据模型决定着来自于人机物三元空间中的多模态场景数据在计算机系统中的存储和表达方式，对后续场景数据的索引组织、分析、可视化起到关键性作用。本文采用多模态场景数据实体描述模型，如图 1所示，从语义描述、空间位置、几何形态、演化过程、复杂关系、属性特征6个方面描述多模态场景数据[7, 28-29]。时空关系图索引是在多模态场景数据实体描述模型的基础上，从多模态场景数据实体及其6个维度中抽取时间、空间、语义和关联关系等需要进行检索的摘要信息以图模型的方式进行排列组织的一种数据结构。与传统树型结构的时空索引只关注时态、位置和拓扑关系不同，时空关系图索引将多模态场景数据实体及其属性特征和广泛存在的关联关系抽象为图模型的节点和边，实现对多模态场景数据多维特征和复杂关联关系的高效索引组织，满足多层次可视化任务，尤其是分析性可视化任务对场景数据的高效检索和调度需求。
|
| 图 1 多模态场景数据实体描述模型 Fig. 1 Entity description model of multimodal scene data |
常见的图模型有资源描述框架(resource description framework，RDF)三元组图模型和标签属性图模型(labeled property graphs，LPG)两种[27]。由于RDF图模型简单的节点和边结构设计，导致RDF模型在表达同样的多模态场景数据时会比LPG模型的节点和关系数量多出一个数量级，因此本文选用LPG模型对场景数据进行表达。LPG模型通过节点、关系、属性和标签直观表达多模态场景数据及其关联关系，它们的详细定义如下：
(1) 节点(nodes)：通常用于表达多模态场景数据实体，例如人、车、智能传感器等，或者复杂的值类型，例如属性值、特征、轨迹点等，并且节点可以拥有键-值形式的属性以及零条或者多条与其他节点相连的关系边。
(2) 关系(relationships)：通常用于表达节点之间的关系，为节点提供上下文语义支持，关系必须拥有一个开始节点和结束节点以及关系类型，以便于关系的快速查找和遍历。此外，关系可以拥有方向，用于表达强烈主动的关联关系，还可以拥有键-值形式的属性。
(3) 属性(properties)：以键-值形式存在于节点和关系中，基于此可以更加丰富地表达多模态场景数据实体及其语义和关系。
(4) 标签(labels)：节点有且只有一个标签，标签可以表示节点的角色或类型，便于节点的快速查找。
时空关系图索引共有3层，如图 2所示，包含时间子图、空间子图和场景数据子图。其中，时间子图由用于表示不同粒度的时间点和时间区间组成；空间子图由用于表示不同粒度的空间范围组成；场景数据子图由实体节点、特征节点和数据节点3种节点混合组成。实体节点用于表达人机物三元空间中的多模态场景数据实体；特征节点是根据数据实体的属性、事件或者行为生成的，并且可以根据不同的场景任务主题进行自适应的批量加载和切换；数据节点表示由场景数据实体或者与之关联的一系列场景数据集合生成。
|
| 图 2 时空关系图索引结构 Fig. 2 Index structure of spatiotemporal relation graph |
时空关系图索引中的关联关系来源可以分为3类。第1类关联关系来源于原始输入的多模态场景数据，包括场景数据实体之间已知的特征关联和通过时空计算提取出的与时间节点和空间节点之间的关联。第2类关联关系是由分析性可视化得到的分析结果和知识，这一类关系常用来更新维护时空关系图索引。第3类关联关系是一类在人机交互的探索性可视化过程中临时假设的关联关系，常用于推理和假设。为了更好地区分和描述关系的类型，可将关联关系按照人机物三元空间细分为6大类，包括：物理空间(spatial和temporal)、社会空间(social)、信息空间(cyber)及其他关系(attributive和causal)，其中，其他关系类型主要是为了表示跨三元空间的通用性关系类型。通过这6大类关联关系可以更细致和全面地描述人机物三元空间中多模态数据实体之间的复杂关联关系，便于对时态、位置、语义和关系的快速关联查询。时空关系图索引中具体关系边的类型可以在这6大类基础之上进行扩展。表 1展示了一些典型的关联关系类型。时空关系图索引中关系边类型的命名是按照“父类:关系名”这样的规则来进行命名的，例如，“Spatial:Inclusion”、“Temporal:Start”和“Temporal:End”等。
| 父类 | 子类示例 | 关系名示例 |
| 空间(spatial) | 拓扑，方向 | Spatial:Inclusion Spatial:South |
| 时间(temporal) | 时间片断，时间点 | Temporal:Start Temporal:End |
| 社会(social) | 强组织，弱关系 | Social:Fan of Social:Jurisdiction |
| 信息(cyber) | 面向对象 | Cyber:Dependece Cyber:Aggregation |
| 属性(attributive) | 拥有，映射 | Attributive:Has Attributive:Mapping |
| 因果(causal) | 随时间变化，推理 | Causal:Timing Causal:Reasoning |
1.2 时空关系图索引的生成
时空关系图索引的构建可以分为3步：
(1) 根据输入的多模态场景数据生成场景数据子图中的实体节点、特征节点和数据节点，并设立相应节点标签。若该数据的实体节点已经存在，则更新其特征节点和数据节点，若不存在，则先创建实体节点，再创建特征节点和数据节点。
(2) 根据上一步生成的数据节点计算相应的时间信息和空间信息，并生成相应的时间节点和空间节点(若不存在)，并设立相应标签。例如：实时接入的人的轨迹数据则是一种空间和时间均变的数据，对于此类数据则计算其某一段时间内的空间范围，并生成相应的时间节点和空间节点。而对于空间不变，值随着时间变化的智能传感器数据，则只需要生成相应的时间节点。
(3) 建立时空关系图索引的子图内部和跨子图之间的关系边连接。首先，将数据子图内部的特征节点、数据节点与实体节点进行关联；接着，将数据子图中的数据节点与计算所得对应的时间节点和空间节点连接；最后，根据实体对象之间已知的关联关系(例如：用户之间的社交关系)对特征节点建立连接。
为了使生成的时空关系图索引具有统一的结构和高效的检索性能，时空关系图索引的构建需要遵循以下规则：
(1) 实体节点只与对应的特征节点和数据节点相连，关系方向为实体节点指向特征节点和数据节点。
(2) 数据节点与对应的时间节点和空间节点相连，关系方向为数据节点指向时间节点和空间节点。
(3) 多模态场景数据实体之间的复杂关联关系通过表达关系的特征节点进行连接表示。
为了使时空关系图索引的构建过程更加直观，举例如下：假设有一个场景数据实体M，其拥有一个表示社交的特征节点Sm和数据节点P，该数据节点表示其最近一段时间[T1, T2)内的轨迹数据，落在空间范围R内。与此同时，随着场景数据的不断接入，时空关系图索引也随之更新，场景实体N进入系统，其拥有特征节点Sn，根据输入的关联关系数据得知M与N是朋友，时空关系图索引的最终构建结果如图 3所示。
|
| 图 3 时空关系图索引的构建结果 Fig. 3 The construction result of spatiotemporal relation graph index |
时间子图和空间子图构成了整个时空关系图索引的时空索引框架，为了加快对场景数据子图中的时空数据的查询，时间节点的存储格式设为(ID, TimeStamp, Type)，其中ID表示时间节点的全局唯一的识别码，TimeStamp表示该时间节点的时间戳，Type表示该时间节点的不同的时间精度，例如：年、日、秒等，时间节点的标签为TimeNode。空间节点的存储格式为(ID, GeoString)，其中ID表示空间节点的全局唯一的识别码，GeoString表示空间区域内对象的一维字符串编码，本文采用一种52位的Geohash算法将经度和纬度坐标转换为唯一的地理字符编码，用于支持空间范围查询和近邻查询。该Geohash在经纬度上分别二分迭代计算，大于则为1，否则为0，其空间粒度的大小通过不同长短的Geohash表示，当Geohash长度为52时，将地球表面划分成了226×226个网格，每个网格的边长是0.6 m。图 4是点P(114.27, 32.08)长度为10的Geohash具体迭代计算过程示意图。点P在经度上计算得11010，纬度上计算得10101，最后Geohash由经纬交叉生成1110011001。在此基础上，空间区域内对象的GeoString计算过程如下：首先计算空间对象的最小外接矩形(MBR)，然后分别计算该MBR的两个对角点的地理字符编码。地理字符编码L的初始值设置为52，如果两个对角点计算得到的Geohash是相同的，这表明该空间对象完全落在同一个地理字符串所表示的网格内，此时相应的Geohash值作为该对象的GeoString。如果不同，则L=L-2，重新计算两个对角点的Geohash值是否相同，如此通过不断的迭代计算，直到相同为止，将当前Geohash的值设为该空间区域内对象的GeoString。
|
| 图 4 基于平面四叉树的地理字符编码生成过程，以点(114.27, 32.08)为例 Fig. 4 The GeoString generation process based on a planar Quad-tree, taking point (114.27, 32.08) as an example |
2 索引的内存存储与操作 2.1 基于稀疏矩阵的内存存储与表达
将索引存储在内存环境中，可以避免索引节点访问时内外存交换产生的I/O延迟，提高场景数据索引构建和查询性能。本文在内存中采用对象的方式存储各类节点和关系的属性数据，如图 5所示，每一个节点和关系都与内存中唯一的键值类型的内存对象通过ID唯一绑定，其中，节点的ID以节点标签作为前缀，即ID1=Lable_uid，便于按照不同的标签对节点进行分类，缩小查询范围，而关系的ID则由始节点ID、末节点ID和关系类型组合形成，即ID3=ID1_ID2_Type，便于快速查询关系的详细语义描述。
|
| 图 5 以内存对象的形式存储节点和关系的属性数据 Fig. 5 Storing attribute data of nodes and relationships in the form of memory objects |
时空关系图索引中的复杂关联关系采用稀疏矩阵进行存储。例如：如果一个有向关系从起始点M指向目标点N，那么使用稀疏矩阵可以表示为：Matrix[M, N]=1，否则为0。一般说来，将矩阵的行用来表示起始点，矩阵的列表示目标点。时空关系图索引拥有一个全局邻接稀疏矩阵，表示所有节点之间的可达性。此外，针对每一种关系类型还会额外存储一个关系稀疏矩阵，用来对关系类型进行维护。如图 3中所生成的时空关系图索引片段，图 6(a)表示其全局邻接矩阵，图 6(b)表示其关系类型为“Attributive:Has_Social”的关系矩阵，其中矩阵行和列的顺序均为[M, N, Sm, Sn, P, T1, T2, R]。面对海量的时空数据组织管理时，基于稀疏矩阵表达的关联关系存在许多0值，为了提高内存的空间利用率，本文采用了CSC(compressed sparse column format)的方法对稀疏矩阵进行压缩存储，并同时采用GraphBLAS线性代数库支持高效的稀疏矩阵运算。
|
| 图 6 时空关系的稀疏矩阵表达 Fig. 6 Representation of spatiotemporal relation based on sparse matrix |
2.2 索引的操作
与以节点的分裂与合并为核心的树型结构空间索引不同，时空关系图索引的操作主要涉及对内存对象的更新和稀疏矩阵的运算。下面将从索引的增加、删除和查询3个方面来详细阐述时空关系图索引的运行机制。
向时空关系图索引中增加不存在的节点及其关联关系时，只需要在内存中插入该节点对象和关系对象，然后根据关系类型对全局邻接矩阵和关系矩阵扩增一个新的行和列，并按照输入关系的始节点和末节点对新增的行列进行赋值，使得M→N处，Matrix[M, N]=1，否则为0。如果只是在已有节点之间新增关系，则在内存中新增该关系对象，并修改全局邻接矩阵和对应类型的关系矩阵中相应位置的数值为1。
从时空关系图索引中删除一个节点，如果删除的是场景数据实体节点，则还需要删除与之对应的特征节点和数据节点，还有与数据节点对应的时空节点(若不存在其他连接，则删除)，最后删除场景数据实体节点本身。针对具体某一个节点的删除，首先需要删除与该节点连接的所有关系边，将全局邻接矩阵和所有类型的关系矩阵中该节点所在的行列全部删除，并删除相应的内存关系对象防止出现只有单个连接节点的关系边，然后再从内存中删除该节点对象。如果只是删除一个关系，则只需要删除相应的内存关系对象，并将对应关系矩阵处相应位置值修改为0，并判断该关系的两个节点之间是否存在其他关系，如果不存在则修改全局邻接矩阵相应位置处为0。
基于稀疏矩阵表示时空关系图索引中的复杂关系连接，给关系的增加和删除操作带来高效率的同时，也提高了时空关系图索引的查询和遍历性能。时空关系图索引中的每一个节点都充当着与其连接的其他节点的索引，借助于关系边可以从一个节点快速到达另外一个相连的节点，实现全图的遍历，并且随着索引规模的增长，遍历整个索引的时间复杂度是O(n)，其中n表示所有节点的总数。时空关系图索引支持时空查询，如图 7所示(简要显示了时空节点和数据节点)，已知时空查询条件：时间范围[t1, t2)和空间范围R1。查询具体步骤是：首先查询到与时空条件对应的时间节点T1和T2，空间节点R1。然后查询与T1时间节点相连且关系类型为“Temporal:Start”的数据节点，同时查询与T2时间节点相连且关系类型为“Temporal:End”的数据节点，两者求交即得到满足时间区间要求的所有数据节点{P2, P3}。接着以类似的方法查询与空间节点相连且关系类型为“Spatial:Inclution”的数据节点{P2, P3, P5, P6}。对两者求交即得到时空查询的结果{P2, P3}。时空关系图索引支持的时空查询是多模式的，支持时-空和空-时查询等多样化的时空查询条件，适应性更广。此外，由上述查询过程可知，索引的时空节点粒度选择需要考虑场景数据的特点，不合理的时空划分粒度会产生大量存储效率不高的数据节点，增加查询时节点与边的遍历量，影响索引性能。
|
| 图 7 多模式时空查询示意 Fig. 7 Spatiotemporal query diagram with schema-free |
此外，时空关系图索引还支持复杂关联关系查询，如图 8(a)(简要绘出了特征节点及其之间的复杂关联关系)，已知需要执行的关联关系查询为“M与I之间存在关联关系A，I与J之间存在关联关系B，J与N之间存在关联关系A，查询所有满足此条件的M与N”，该查询条件可以表示为图 8(b)中的模式子图。使用稀疏矩阵使得这一类复杂关系查询变得简单，获取关系类型为A的关系矩阵P(A)和关系类型为B的关系矩阵P(B)，然后将关系矩阵相乘Result(M, J)=P(B)P(A)，得到中间结果Result(M, J)，继续计算Result(M, N)=P(A)Result(M, J)，Result(M, N)的行表示可能的M节点，列表示可能的N节点，如果Result(M, N)[i, j]=1，则(M, N)就是符合条件的结果，图 9展示了计算过程，其中，矩阵的行和列依次为[S1, S2, S3, S4, S5, S6]，得到所有可能的结果共10组，若去除重复节点和关系回路，最终符合条件的节点共4组，为{(S1, S4), (S1, S5), (S3, S2), (S4, S2)}。
|
| 图 8 复杂关联关系查询与模式子 Fig. 8 Complex associations query and pattern subgraph |
|
| 图 9 基于矩阵运算的复杂关联关系查询 Fig. 9 Example of complex relation query based on matrix operations |
时空关系查询是对时空查询和关系查询的结合应用，通过时空查询可以缩小关系查询的范围，避免全图遍历。这一类复杂时空关系的查询常用于城市犯罪分析和智能设施诊断等场景中，对于探索场景对象之间的相互作用、隐含信息和规律具有重要意义。尤其是随着增强现实等显示设备的应用，出现了新型人机交互界面，用户可以更方便地与计算机进行交互，叠加用户的知识和经验，构建目标的时空关系子图，迭代查询与分析，形成一套可假设、可推理、可解释的完整交互分析体系。
3 试验分析本文从索引生成、时空查询、复杂关系查询3个方面开展试验，综合测试时空关系图索引在处理智能感知数据和复杂关联关系方面的有效性和高效性。本文选取一种基于MongoDB数据库实现的多维树索引作为对比试验对象，下文简称“多维树索引”。为了保证试验的可靠性，试验结果均是取得多次测量结果的平均值。
3.1 试验场景与环境本文旨在构造一个以人类活动为中心、人机物三元空间相互交融、动静耦合、多要素相互作用的试验场景。人类活动在物理空间中产生了大量时空维度不断动态变化的轨迹数据，同时在社会空间中通过相互作用和影响产生了大量的社交关联关系数据，最终这些数据均被接入到了信息空间中进行处理和分析。上述提及的多模态场景数据均由模拟程序生成，包括用户属性数据、轨迹点数据和社交关系数据3种，根据用户规模不同分为4组，其主要信息描述如表 2所示。试验程序和依赖项均以Docker容器的形式运行在虚拟机(4核心，16 GB内存，CentOS 7最小化安装)环境中，运行此虚拟机的物理机配置为Intel i7-8750H 2.2 GHz，内存32 GB，磁盘为1 TB，7200转，系统为64位Win10专业版。本文索引方法基于内存数据库Redis(V5.0.3版)和图模型开发工具RedisGraph(V1.2.2版)实现，而多维树索引基于MongoDB(V4.0.4版)实现，对数据在时间、空间和属性多个维度分别建立典型树索引，即分别在轨迹数据空间维建立2Dsphere空间索引，在时间维建立B树索引，并对包含关联关系数据的用户ID属性维建立B树索引。为了保证试验测试的公平性，两种索引方法均采用相同的时间粒度，即时间间隔为15 min。
| 数据集名称 | 用户数 | 关联关系数 | 时间跨度 | 轨迹数 |
| OBJ1W | 10 000 | 60 729 | (2016-01-01 00:00— 2016-01-01 12:30) |
50 0000 |
| OBJ3W | 30 000 | 259 005 | 1 500 000 | |
| OBJ5W | 50 000 | 443 391 | 2 500 000 | |
| OBJ10W | 100 000 | 886 933 | 5 000 000 |
3.2 效率分析 3.2.1 索引创建效率
实时接入的智能感知数据和关联关系需要及时高效的处理，因此索引的构建效率极为关键。时空关系图索引将场景数据和索引全部存储在内存中，具体处理细节如下：首先将试验数据中的用户数据抽象为带有用户属性和object标签的用户实体节点；接着为每一个用户实体节点生成相应的带有social标签的社交特征节点并建立连接，用于表达用户之间的社交关联关系数据；然后将轨迹数据按照15 min的时间粒度进行划分，生成相应的带有data标签的数据节点，每个用户实体节点共拥有50个数据节点，每个数据节点根据所表示的轨迹起始时间与时间节点连接，同时计算该数据节点所属的空间节点并与空间节点连接，其中空间节点GeoString初始化长度设为38位。基于试验数据构建的时空关系图索引抽象示意如图 10所示。
|
| 图 10 基于试验数据的时空关系图索引构建 Fig. 10 Spatiotemporal relation graph index construction based on experimental data |
索引创建试验分别针对不同规模的数据集展开，索引处理效率曲线如图 11所示，索引处理效率由总记录数除以总耗时所得。由效率曲线可以看出不同数据规模下的时空关系图索引的处理效率均优于对比方法。
|
| 图 11 不同规模数据集下索引创建效率对比 Fig. 11 Comparison of index creation efficiency under different scale data sets |
3.2.2 索引查询效率
为了验证本文方法的时空查询性能，在数据集OBJ5W上根据索引时空粒度分别选取了小(75×75 m2, 30 min)，中(150×150 m2, 60 min)，大(300×300 m2, 90 min)3组时空范围与多维树索引开展了时空查询试验(参数设置与前文相同)，试验结果如图 12所示。由试验结果可以看出，在小、中时空范围查询试验中，时空关系图索引方法耗时少于对比方法。随着时空查询粒度的进一步增大，由于时空关系图索引的初始时空粒度设置较小，导致访问的节点和关系边增多，耗时增加，但与多维树索引相差不大。
|
| 图 12 不同时空范围下的查询耗时 Fig. 12 Time-consuming of spatiotemporal queries in different spatiotemporal ranges |
为了验证本文方法在复杂时空关系查询方面的优势，本次试验针对试验数据分别设计了“行为模式挖掘”和“异常探测”两个查询场景。其中，“行为模式挖掘”的查询条件为“查询用户A的N阶以内的朋友B，满足A与B都曾去过地点C”，该查询可以分析关联用户之间的行为偏好。“异常探测”的查询条件为“查询A的N阶以内的朋友B，满足A与B同时在地点C出现过”，该查询可以分析关联用户之间时空集聚现象。分别就N={1, 2, 3}进行了查询试验，查询结果如图 13所示。
|
| 图 13 不同关系阶数下时空关联查询耗时 Fig. 13 Time-consuming of spatiotemporal association queries with different orders |
本文方法可快速检索所有三阶内的关系用户，然后根据关系边继续访问时空节点相关联的数据节点，判断是否曾经去过某地或同时出现在某地，避免了大量遍历匹配操作，针对时空关系不确定性查询具有明显优势。而多维树索引在关系阶数较低时，查询效率较好，但随着查询阶数的增大，得到满足关系条件的候选用户数增多，进一步导致需要计算匹配的用户轨迹数目增多，使得查询效率明显下降，耗时远高于本文方法。
4 结论本文提出的时空关系图索引算法充分利用了基于稀疏矩阵的内存图模型优势，支持智能感知数据和关联关系的高效索引组织，支持多模式的时空查询和复杂时空关系查询。在索引生成和查询效率上明显优于对比方法，满足分析性场景任务对数据的高性能、低延迟访问需求。在索引内存空间存储效率方面，虽然采用了CSC稀疏矩阵压缩方法，在一定程度上降低了内存空间占用，但仍具有优化空间。未来随着智慧城市建设的推进，智能感知数据和关联关系数据的高效组织管理是场景对象之间异常发现和探究其相互作用规律的核心技术，后续工作会针对更复杂的现实应用场景，例如：智慧社区智能设施管理，进一步提高索引方法在处理时间和存储空间方面的效率，以提高索引的多目标并发访问和复杂时空关系分析能力。
| [1] |
FENG Bin, ZHU Qing, LIU Mingwei, et al. An efficient graph-based spatio-temporal indexing method for task-oriented multi-modal scene data organization[J]. ISPRS International Journal of Geo-Information, 2018, 7(9): 371. |
| [2] |
朱庆, 付萧. 多模态时空大数据可视分析方法综述[J]. 测绘学报, 2017, 46(10): 1672-1677. ZHU Qing, FU Xiao. The review of visual analysis methods of multi-modal spatio-temporal big data[J]. Acta Geodaetica et Cartographica Sinica, 2017, 46(10): 1672-1677. DOI:10.11947/j.AGCS.2017.20170286 |
| [3] |
刘铭崴, 朱庆, 朱军, 等. 多模态时空数据多层次可视化任务模型[J]. 测绘学报, 2018, 47(8): 1098-1104. LIU Mingwei, ZHU Qing, ZHU Jun, et al. The multi-level visualization task model for multi-modal spatio-temporal data[J]. Acta Geodaetica et Cartographica Sinica, 2018, 47(8): 1098-1104. DOI:10.11947/j.AGCS.2018.20180104 |
| [4] |
CHEN C L P, ZHANG Chunyang. Data-intensive applications, challenges, techniques and technologies:a survey on big data[J]. Information Sciences, 2014, 275: 314-347. |
| [5] |
陆锋, 周成虎. 一种基于Hilbert排列码的GIS空间索引方法[J]. 计算机辅助设计与图形学学报, 2001, 13(5): 424-429. LU Feng, ZHOU Chenghu. A GIS spatial indexing approach based on Hilbert ordering code[J]. Journal of Computer-Aided Design & Computer Graphics, 2001, 13(5): 424-429. |
| [6] |
REZGUI A, MALIK Z, XIA Jizhe, et al. Data-intensive spatial indexing on the clouds[J]. Procedia Computer Science, 2013, 18: 2615-2618. |
| [7] |
华一新. 全空间信息系统的核心问题和关键技术[J]. 测绘科学技术学报, 2016, 33(4): 331-335. HUA Yixin. The core problems and key technologies of pan-spatial information system[J]. Journal of Geomatics Science and Technology, 2016, 33(4): 331-335. |
| [8] |
龚俊, 柯胜男, 朱庆, 等. 一种集成R树、哈希表和B*树的高效轨迹数据索引方法[J]. 测绘学报, 2015, 44(5): 570-577. GONG Jun, KE Shengnan, ZHU Qing, et al. An efficient trajectory data index integrating R-tree, hash and B*-tree[J]. Acta Geodaetica et Cartographica Sinica, 2015, 44(5): 570-577. DOI:10.11947/j.AGCS.2015.20130520 |
| [9] |
MA Youzhong, RAO Jia, HU Weisong, et al. An efficient index for massive IOT data in cloud environment[C]//CIKM'12 Proceedings of the 21st ACM International Conference on Information and Knowledge Management. Bellevue, WA: ACM, 2012. https://dl.acm.org/doi/10.1145/2396761.2398587
|
| [10] |
YU Jia, WU Jinxuan, SARWAT M. GeoSpark: a cluster computing framework for processing large-scale spatial data[C]//Proceedings of the 23rd SIGSPATIAL International Conference on Advances in Geographic Information Systems. Bellevue, WA: ACM, 2015. https://www.researchgate.net/publication/307822559_GeoSpark_a_cluster_computing_framework_for_processing_large-scale_spatial_data
|
| [11] |
AJI A, WANG Fusheng, VO H, et al. Hadoop-GIS:a high performance spatial data warehousing system over mapreduce[J]. Proceedings of the VLDB Endowment, 2013, 6(11): 1009-1120. |
| [12] |
AZQUETA-ALZÚAZ A, PATIÑO-MARTINEZ M, BRONDINO I, et al. Massive data load on distributed database systems over HBase[C]//Proceedings of the 17th IEEE/ACM International Symposium on Cluster, Cloud and Grid Computing (CCGRID). Madrid, Spain: IEEE, 2017.
|
| [13] |
NISHIMURA S, DAS S, AGRAWAL D, et al. MD-HBase: a scalable multi-dimensional data infrastructure for location aware services[C]//Proceedings of 2011 IEEE International Conference on Mobile Data Management. Lulea, Sweden: IEEE, 2011. https://www.researchgate.net/publication/224265794_MD-HBase_A_Scalable_Multi-dimensional_Data_Infrastructure_for_Location_Aware_Services
|
| [14] |
ELDAWY A, ALARABI L, MOKBEL M F. Spatial partitioning techniques in SpatialHadoop[J]. Proceedings of the VLDB Endowment, 2015, 8(12): 1602-1605. |
| [15] |
MOKBEL M F, GHANEM T M, AREF W G. Spatio-temporal access methods[J]. IEEE Data Engineering Bulletin, 2003, 26(2): 40-49. |
| [16] |
NGUYEN-DINH L V, AREF W G, MOKBEL M. Spatio-temporal access methods:part 2(2003-2010)[J]. IEEE Data Engineering Bulletin, 2010, 33(1): 46-55. |
| [17] |
LI Shen, HU Shaohan, GANTI R, et al. Pyro: a spatial-temporal big-data storage system[C]//Proceedings of the USENIX Annual Technical Conference. Bellevue, WA: ACM, 2015. https://www.researchgate.net/publication/277558808_Pyro_A_Spatial-Temporal_Big-Data_Storage_System
|
| [18] |
KILIMCI P, KALIPSIZ O. Indexing of spatiotemporal data: a comparison between sweep and Z-order space filling curves[C]//International Conference on Information Society (i-Society 2011). London, UK: IEEE, 2011. https://www.researchgate.net/publication/252027973_Indexing_of_spatiotemporal_Data_A_comparison_between_sweep_and_z-order_space_filling_curves
|
| [19] |
LIZARDO L E O, DAVIS JR C A. A PostGIS extension to support advanced spatial data types and integrity constraints[C]//Proceedings of the 25th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems. Bellevue, WA: ACM, 2017. https://www.researchgate.net/publication/322952591_A_PostGIS_extension_to_support_advanced_spatial_data_types_and_integrity_constraints
|
| [20] |
丁治明, 高需. 面向物联网海量传感器采样数据管理的数据库集群系统框架[J]. 计算机学报, 2012, 35(6): 1175-1191. DING Zhiming, GAO Xu. A database cluster system framework for managing massive sensor sampling data in the internet of things[J]. Chinese Journal of Computers, 2012, 35(6): 1175-1191. |
| [21] |
FERNANDES D, BERNARDINO J. Graph databases comparison: AllegroGraph, ArangoDB, InfiniteGraph, Neo4J, and OrientDB[C]//Proceedings of the 7th International Conference on Data Science, Technology and Applications. Bellevue, WA: ACM, 2018. https://dl.acm.org/doi/10.5220/0006910203730380
|
| [22] |
VUKOTIC A, WATT N. Neo4J in action[M]. Shelter Island, NY: Manning Publications Co, 2015.
|
| [23] |
ELBATTAH M, ROUSHDY M, AREF M, et al. Large-scale ontology storage and query using graph database-oriented approach: the case of Freebase[C]//Proceedings of 2015 IEEE Seventh International Conference on Intelligent Computing and Information Systems (ICICIS). Cairo, Egypt: IEEE, 2016. https://www.researchgate.net/publication/304414637_Large-Scale_Ontology_Storage_and_Query_Using_Graph_Database-Oriented_Approach
|
| [24] |
XIAO Zhuoling, WEN Hongkai, MARKHAM A, et al. Indoor tracking using undirected graphical models[J]. IEEE Transactions on Mobile Computing, 2015, 14(11): 2286-2301. |
| [25] |
ZHANG Xiaomin, SONG Wei, LIU Liming. An implementation approach to store GIS spatial data on NoSQL database[C]//Proceedings of the 22nd International Conference on Geoinformatics. Kaohsiung, Taiwan: IEEE, 2014. https://www.researchgate.net/publication/286108516_An_implementation_approach_to_store_GIS_spatial_data_on_NoSQL_database
|
| [26] |
XU Xiaofeng, XIONG Li, SUNDERAM V. D-grid: an in-memory dual space grid index for moving object databases[C]//Proceedings of the 17th IEEE International Conference on Mobile Data Management (MDM). Porto, Portugal: IEEE, 2016. https://www.researchgate.net/publication/305525786_D-Grid_An_In-Memory_Dual_Space_Grid_Index_for_Moving_Object_Databases
|
| [27] |
ANGLES R. A comparison of current graph database models[C]//Proceedings of the 28th IEEE International Conference on Data Engineering Workshops. Arlington, VA: IEEE, 2012. https://www.researchgate.net/publication/261076480_A_Comparison_of_Current_Graph_Database_Models
|
| [28] |
华一新, 周成虎. 面向全空间信息系统的多粒度时空对象数据模型描述框架[J]. 地球信息科学学报, 2017, 19(9): 1142-1149. HUA Yixin, ZHOU Chenghu. Description frame of data model of multi-granularity spatio-temporal object for pan-spatial information system[J]. Journal of Geo-information Science, 2017, 19(9): 1142-1149. |
| [29] |
周成虎. 全空间地理信息系统展望[J]. 地理科学进展, 2015, 34(2): 129-131. ZHOU Chenghu. Prospects on pan-spatial information system[J]. Progress in Geography, 2015, 34(2): 129-131. |