移动轨迹数据的分布式存储和计算方法研究

本科毕业论文移动轨迹数据的分布式存储和计算方法研究 学院专业学生姓名学生学号指导教师提交日期计算机科学与工程学院计算机科学与技术王鑫同201230601184吕建明副教授2016年6月摘 要目前，移动设备已得到普遍应用，通过这些设备收集了大量的用户实时的时间、空间信息。针对时空数据进行存储与分析，对于基于位置的服务具有重要的作用。然而，时空数据具有数据容量巨大、流式到达、多源异构等特性，因此对大规模时空数据进行存储与检索是当前研究所面临的挑战。为解决时空数据存储与计算问题，首先，我们提出了移动轨迹数据的存储和精确匹配查询方法。并将针对移动轨迹的存储与精确匹配检索方法应用到安全监控领域，开发基于分布式架构的犯罪嫌疑人追踪系统TREST。TREST利用Hadoop集群分布式横向扩展机制有效存储海量移动轨迹数据，支持对流式移动轨迹数据频繁的更新操作。同时，TREST直接将移动轨迹映射到HBase中key-value模式中去，从而获得更高的检索效率。更进一步的，我们研究了该问题的扩展问题，针对时空数据的复杂查询问题。时空数据是比移动轨迹数据更加宽泛的一类数据，而移动轨迹数据是其中一种特殊模态的时空数据。我们提出了时空数据存储与复杂查询方法，并将针对时空数据的存储与复杂检索方法应用到房产大数据分析领域，开发基于分布式架构的房产大数据分析平台HPLAT。HPLAT针对更加普适的时空数据进行存储与计算，并且支持对时空数据进行更加复杂的聚合、连接、时空范围查询等查询操作。同时，我们提出了时空数据存储与分析系统的基本框架，并利用真实的基站数据与模拟的房产交易数据对系统进行了测试。实验结果显示，TREST与HPLAT具有高效的数据吞吐性能，并且能够快速的执行精确匹配查询与复杂查询等查询任务。关键词：时空数据；轨迹；分布式存储；分布式计算；AbstractNowadays, mobile phones have prevailed in a great variety of applications, through which massive personal trajectories can be collected and analyzed to support many interesting location-based services. However, it is still challenging to efciently store and retrieve this kind of spatio-temporal data, which has typical big-data feature with large size, streaming style and multiple data source. To address this issue, first, we propose a method to store mobile trajectories and conduct exact retrieval tasks in a distributed manner. Using this method, we develop a mobile trajectory retrieval system named TREST, which is based on the distributed Hadoop and HBase systems. TREST makes use of the horizontal expansion mechanism of Hadoop to store over-whelming spatio-temporal trajectories, and supports frequent incremental insertion of data stream. Furthermore, we study an expansion problem, which is how to store normal spatio-temporal data and conduct complex retrieval tasks. Using the method we proposed, we develop a house-transaction data analyzing system named HPLAT. HPLAT makes use of the memory-based mechanism of Spark to store normal spatio-temporal data, and supports complex retrieval of data stream. Meanwhile, we propose a spatio-temporal data distributed storage and computing framework, and conduct experiments on TREST and HPLAT. Experiments on these systems show that TREST and HPLAT can efciently support both exact retrieval and complex retrieval tasks.Keywords: Spatio-temporal data, trajectories, distributed storage, distributed computing目 录摘 要IIAbstractIII目 录IV第一章绪论11.1研究背景及意义11.1.1 移动轨迹数据的价值11.1.2 移动轨迹数据的分布式存储和计算方法11.1.3 时空数据的分布式存储和计算方法21.2本文的工作21.3本文的组织结构41.4本章小结5第二章基于Hadoop的分布式存储与计算技术62.1时空数据的分布式存储方法62.1.1基于HBase的分布式存储方法62.1.2基于Hive的分布式存储方法72.2时空数据的分布式计算技术82.2.1基于MapReduce的分布式计算技术82.2.2基于Spark的分布式计算技术92.3本章小结10第三章移动轨迹的存储与精确匹配检索113.1移动轨迹的精确匹配检索113.2目标人物手机识别与追踪的背景介绍123.3相关概念及介绍123.3.1手机轨迹的定义123.3.2 轨迹检索任务的定义143.4系统的存储架构设计143.5目标人物轨迹检索算法163.5.1 单目标轨迹检索算法163.5.2 多目标轨迹检索算法163.6实验分析183.6.1数据插入效率193.6.2轨迹检索效率193.6.3原型系统213.7本章小结22第四章时空数据的存储与复杂检索234.1时空数据的复杂检索234.2时空大数据分析的背景介绍244.3相关概念及介绍244.3.1时空数据的定义244.3.2 时空数据复杂检索任务的定义254.4平台的存储架构设计264.5时空数据的复杂检索算法284.5.1时空数据的聚合检索算法284.5.2 时空数据的连接检索算法294.5.3 时空数据的时空范围检索算法294.6实验分析304.6.1数据插入效率314.6.2数据检索效率314.7本章小结32第五章系统实现与实验分析335.1时空数据存储与分析系统的基本框架335.1.1存储与分析系统的基本框架335.1.2时空数据存储与分析的核心问题345.2系统性能对比分析345.2.1数据插入效率的对比分析345.2.2数据检索效率的对比分析355.3本章小结36结论371.论文工作总结372.工作展望37参考文献39致谢41第一章 绪论第一章 绪论1.1 研究背景及意义1.1.1 移动轨迹数据的价值过去几年中，诸如手机等移动设备显著增加，这些移动设备能记录并报告用户实时的轨迹信息。大量用户使用移动手持设备的同时就产生了大量的移动轨迹数据，数据容量迅猛增加。同时，移动轨迹是众多基于位置服务的基础资源，如智能导游、驾驶智能指引、旅游热点搜索等都需要支持对移动轨迹数据高效的存储与检索。如果能够实现对移动轨迹数据的分布式存储和高效计算，从数据中挖掘出其中包含的规律，是非常有益的。因此，本文对移动轨迹数据的存储与计算方法进行深入的研究。1.1.2 移动轨迹数据的分布式存储和计算方法移动轨迹数据是带有移动时空属性的数据，是移动对象随着时间和位置的变化产生的一系列时空点。针对此类数据如何进行高效的存储以及计算是当前的研究热点。近年来，基于树结构的索引技术在轨迹检索中得到广泛使用，如R*Tree1、TPR-Tree2、TPR*-Tree3、B+Tree4和基于网格的索引算法5。基于这些索引算法，产生了专门为时空数据存储而设计的系统，例如TrajStore6和PIST7，其中TrajStore通过在磁盘相邻段上动态存储和压缩时空数据，实现在特定时空区域进行有效检索。而PIST是对空间进行最优化网格切分，在子空间内建立时间索引B+Tree，实现性能最优化。无论是TrajStore还是PIST都采用非分布式存储架构，因此在处理大规模轨迹数据集方面存在不适应性的缺陷。不同于TrajStore和PIST，CloST8是利用Hadoop分布式存储与计算框架来实现更好的可扩展性。CloST根据时空属性进行数据划分，在分布式文件系统（HDFS：Hadoop Distributed File System）上以三级目录树的形式组织数据分区，并且其利用Hadoop MapReduce并行计算方法进行数据检索。OceanST9是近期提出的一种基于Hadoop的时空数据存储系统，其存储采用与CloST相似的数据分区策略。不同的是，OceanST通过在块文件一级引进三维时空索引从而提高了CloST系统的检索效率。同时，OceanST利用Spark良好的基于内存的迭代计算性能，替代了原有基于磁盘I/O的MapReduce方式。然而，无论是CloST还是OceanST，这种基于块文件的目录树索引方式，使得此类系统难以高效地执行多目标检索，即在给定时空范围内检索出所有的移动轨迹。这是因为全目标检索会导致系统扫描分布于HDFS中不同文件目录下的大量的块文件，从而带来巨大的时间开销。为了实现对移动轨迹数据的分布式存储和精确匹配查询，本文基于这些研究需求，提出基于Hadoop HBase/MapReduce的分布式存储与计算方法。1.1.3 时空数据的分布式存储和计算方法时空数据是比移动轨迹数据更加宽泛的一类数据，即数据中包含有时间维与空间维属性的数据。随着城市计算10、感知计算与基于位置的社交网络11等新兴领域的兴起，对多种异构的时空数据进行更为普适的存储与复杂计算，成为当前研究所面临的挑战。近年来，传感器遍布于人们生活之中，如手持设备、穿戴设备、交通设备和人等。传感器与设备在工作的过程中，不断地搜集多种模态与属性的时空数据。例如，空气质量数据、能耗数据、交通流数据、房产交易数据等时空数据，而移动轨迹数据是其中一种特殊模态的时空数据。在上文所介绍的专门为时空数据存储而设计的系统中，TrajStore和PIST虽然针对时空索引进行了设计与优化，但因其所采用的非分布式存储架构，难以应对海量数据所带来的挑战。CloST与OceanST等基于Hadoop的分布式存储与计算框架而实现的单数据、单任务系统，在应对多数据、多任务等更为普适的时空数据存储与更加复杂的计算时显示出不足。因此，为实现针对更普遍的时空数据的分布式存储与复杂计算，本文基于这些研究需求，提出了基于Hadoop Hive/Spark的分布式存储与计算方法。该方法能够针对更加普适的时空数据进行存储与计算。同时，支持更加复杂的聚合、连接、时空范围查询等查询操作。1.2 本文的工作本文首先对移动轨迹的存储与精确匹配查询进行深入的探讨与分析；设计了一种基于Hadoop HBase的分布式存储方法，并利用MapReduce并行计算技术对移动轨迹数据进行高效检索；接下来，我们在监控领域利用Hadoop HBase存储架构开发基于分布式架构的犯罪嫌疑人追踪系统。更进一步的，我们研究了该问题的扩展问题，即针对时空数据进行更复杂的查询。我们设计一种基于Hadoop Hive时空数据的分布式存储方法，从而实现针对更加普适的时空数据的存储与计算，轨迹数据本质上是时空数据的一种特例。同时，我们利用Spark分布式计算框架对时空数据进行并行计算，从而支持更加复杂的聚合、连接、时空范围查询等查询操作。最后，本文在房地产领域利用Hadoop Hive存储架构开发了房产交易大数据处理平台。在基于Hadoop HBase的分布式存储方法与MapReduce并行计算技术方面，本文在安全监控领域，设计了在手机移动轨迹数据上对目标人物进行识别与追踪的系统TREST。其工作的创新点如下：1. 我们提出一种基于Hadoop HBase的轻量索引机制，从而对移动轨迹数据进行分布式存储与高效地检索。与CloST、OceanST相似，TREST利用Hadoop实现横向扩展机制。不同的是，TREST直接将移动轨迹映射到HBase中key-value模式中去，因此TREST的索引结构比起CloST与OceanST更为轻量，能够获得更高的检索效率。在拥有1亿条数据的真实轨迹数据集上，TREST可以在毫秒级完成各项检索任务。2. 为实现针对不同检索任务的高效检索，我们以数据冗余方式对移动轨迹进行存储。轨迹数据被冗余存储到多张HBase表中，每一张表选择一个最优的row key从而优化检索性能。3. 利用Hadoop HBase存储与检索方法，我们开发基于分布式架构的犯罪嫌疑人追踪系统。该系统通过检索匹配于给定移动模式的犯罪嫌疑人的手机轨迹，从而确定犯罪嫌疑人的手机设备号。在基于Hadoop Hive的分布式存储方法与Spark并行计算技术方面，我们在房地产领域，设计了房产交易大数据处理平台HPLAT。其工作的创新点如下：1. 我们提出一种基于Hadoop Hive的分布式存储方法，从而针对更加普适的时空数据进行分布式存储与高效地计算。与TREST相似，HPLAT利用Hadoop的分布式文件系统HDFS进行底层的数据存储，以分布式的方式管理表的元数据，并实现高可扩展性。不同的是，HPLAT直接将时空数据映射到Hive的key-value表模式中去。因此，HPLAT的存储架构更为简单、轻量、通用。从而解决针对Hadoop HBase存储架构中只能支持基于row key进行高效查询，而针对非row key查询会导致全表扫描的不足。2. 为实现针对时空数据的复杂查询，我们利用Spark并行计算框架对时空数据计算，从而支持更加复杂的聚合、连接、时空范围查询等查询操作。利用Spark并行计算技术替代原有的MapReduce并行计算框架，解决了MapReduce并行计算时大量磁盘I/O与同步障的性能不足。在拥有4千万条记录的模拟房产交易数据集上，HPLAT可以在秒级完成各项检索任务。3. 利用Hadoop Hive的存储方法，我们开发房产交易大数据处理平台。该平台实现对海量关系数据的分布式存储与快速在线交互计算。1.3 本文的组织结构本文分为五章。第一章简述了移动轨迹数据的价值，对比了国内外现有的针对移动轨迹数据的存储与计算方法。特别地，我们还简述了比移动轨迹数据更为普适的时空数据，分析其在存储与复杂计算方面所面临的挑战。第二章，我们详细介绍了基于Hadoop的分布式存储与计算技术。对Hadoop、HBase、Hive、MapReduce、Spark等分布式存储与计算技术进行原理性介绍。第三章，我们针对移动轨迹数据的存储与精确匹配检索问题进行深入探讨。接下来，我们介绍了利用该方法支持的一个移动轨迹应用场景，即在安防领域对犯罪嫌疑人进行识别与追踪。之后我们对方法进行相关的实验测试，并进行性能评估。第四章，更进一步地，我们研究了移动轨迹数据的存储与精确匹配检索的扩展问题，即针对时空数据的存储与复杂检索。接下来，我们介绍了应用该方法的实际项目，房产交易大数据处理平台。在本章最后，我们对方法进行相关的实验测试，并进行性能评估。第五章是两个系统的对比分析，以及本文中综合性的实验结论。结论中，我们对本文移动轨迹数据的分布式存储与计算的研究工作进行总结。分析其不足，展望未来工作中深入优化的方向。1.4 本章小结本章首先介绍了移动轨迹数据的价值，并对国内外现有的移动轨迹存储与计算方法进行概述。特别地，本章简述了比移动轨迹数据更为普适的时空数据，分析其在存储与复杂计算方面所面临的挑战。接着本章概述了针对移动轨迹数据的存储与精确匹配检索方法。更进一步的，对该问题的拓展问题进行介绍，即针对时空数据的存储与复杂查询。在本章的最后，我们对全文的组织结构进行了简要介绍。5第二章 基于Hadoop的分布式存储与计算技术第二章 基于Hadoop的分布式存储与计算技术在前面的章节中，我们介绍了移动轨迹数据的分布式存储和计算方法的研究背景。事实上，基于非分布式存储架构而设计的时空数据存储系统难以应对海量移动轨迹数据以及难以实现高可扩展。而基于分布式存储架构而设计的时空数据存储系统能够实现对移动轨迹数据的分布式存储与并行计算，但同时又各有不足，不能实现对各种移动轨迹检索任务都有高效的检索性能。因此实现针对移动轨迹数据的存储与精确匹配检索，更进一步地实现针对时空数据的存储与复杂检索，比现有系统具有更高的应用价值。目前本文在时空数据的存储与计算方法的研究工作已经获得阶段成果，并将其应用到实际的领域中去。其中，将基于Hadoop HBase存储方法应用到安全监控领域；将基于Hadoop Hive存储方法应用到房地产交易大数据处理领域。本章将对相关存储与计算方法进行介绍，并在后续章节中对两类问题进行描述，并对应用的设计以及性能的评估进行介绍。2.1 时空数据的分布式存储方法2.1.1 基于HBase的分布式存储方法目前，业界存在许多分布式存储架构，其中Hadoop12是一个流行的分布式存储和并行计算架构。HBase13是一个分布式NoSQL数据库，可以实时读写大规模移动轨迹数据，如图2-1。同时，HBase以简单的键值对的形式组织数据以支持高效的基于键的检索。HBase数据存储是以分布式多维表的形式存储的。HBase表中的数据在逻辑上根据记录的不同键被划分到不同的区域中去，并以一种分布式的线性索引树组织数据。因此，在HBase中选择合适的键对于获得高效的检索性能是至关重要的。图2-1 基于Hadoop HBase的存储架构2.1.2 基于Hive的分布式存储方法Hive14是Hadoop底层分布式文件系统HDFS之上的一个数据仓库，其架构如图2-2。Hive逻辑上是以表的形式维护海量数据，并利用Hive查询语言HiveQL进行交互分析。表的模式及其他元数据信息是由Hive内部的元数据管理器metastore进行存储。在集群环境下，需要利用如MySQL等关系型数据库进行元数据存储，并对集群中的其他节点提供元数据服务。Hive逻辑上以表的形式组织数据，其本质是由元数据管理器以分布式方式管理和维护表的目录或者命名空间，而真正的数据是存储在Hadoop的分布式文件系统上。具体来说，Hive的表模式分为管理表与外部表两种。管理表即内部表，Hive会管理数据的整个生命周期，当删除表的模式时真实数据也会被删除。外部表只是告知Hive的元数据管理器真实数据的存储目录，当在Hive中删除表的模式时，真实的数据不会被删除。图2-2 基于Hadoop Hive的存储架构2.2 时空数据的分布式计算技术2.2.1 基于MapReduce的分布式计算技术MapReduce是一种并行计算模型，可以将大型的数据处理任务分解为单个，并且将任务在集群环境中并行执行，最后将各个子任务的计算结果进行合并产生最终的计算结果。MapReduce实际上对应于两个基本的数据转化操作，即Map操作与Reduce操作，具体如图2-3。Map操作是将以键值对形式的输入转化为多个键值对输出。而Reduce操作是将经Map操作产生的转化后的键值对进一步转化为集合。基于MapReduce的分布式计算方法主要分为两步：利用HBase进行时空数据的分布式存储；接下来就是利用MapReduce并行计算框架对时空数据进行计算。对时空数据的计算是利用MapReduce的API，将HBase作为数据源，利用Hadoop对HBase开放的接口InputFormat读入数据，并将读入的数据进行Map操作转换为键值对，进一步利用Reduce操作转换为新的集合或者值，最后利用接口OutputFormat将结果持久化到文本文件或者HBase中。图2-3 基于MapReduce的并行计算方法2.2.2 基于Spark的分布式计算技术Spark15是用于实现快速通用的分布式计算平台，其扩展了MapReduce并行计算框架，从而更高效的支持交互式查询分析与流式数据处理。Spark基于内存计算，从而解决MapReduce在进行迭代计算时巨大的磁盘I/O开销所带来的性能低下。其次，Spark利用有向无环图DAG优化任务调度，从而解决MapReduce进行子任务同步时的不足。Spark分布式计算框架操作的对象是分布式弹性数据集RDD，对RDD的计算主要包括转化操作与行动操作。RDD的转化操作是利用转换算子将原RDD转化为新的RDD。而行动操作是利用行动算子触发实际计算并向驱动器程序返回结果，具体如图2-4所示。利用Hadoop Hive对时空数据进行分布式存储，接下来利用Spark组件Spark SQL对时空数据进行交互式计算分析。Spark SQL是Spark中用来操作结构化和半结构化数据的接口。对时空数据进行计算，是通过在Spark SQL中连接Hive作为数据源，对输入的数据转化为Spark能够操作的数据集合分布式弹性数据集RDD。通过转化算子转化RDD，并利用行动算子触发计算行为，并将计算结果返回驱动器程序，最终打印在终端或持久化存储到Hive中去。图2-4 基于Spark的并行计算方法2.3 本章小结本章主要介绍了基于Hadoop的分布式存储与计算技术。首先，对Hadoop HBase、Hadoop Hive等分布式存储技术结合存储结构图进行原理性介绍。最后，对MapReduce与Spark等分布式计算技术进行了原理性介绍。9第三章 移动轨迹的存储与精确匹配检索第三章 移动轨迹的存储与精确匹配检索前面的章节中，我们介绍了移动轨迹数据的存储与计算的研究背景。在实际应用中，对移动轨迹进行计算，精确匹配检索是一种常见的检索。精确匹配检索是指对具体的轨迹或者数据点进行检索。例如，根据某些时空点精确找出与其匹配的轨迹。而移动轨迹数据往往规模巨大，因此想要快速进行轨迹的精确匹配就要设计合适的存储架构与检索方法。正如本文第一章所分析，现有的移动轨迹存储系统，在针对大规模移动轨迹存储与精确匹配检索方面表现出性能不足，这也是现有研究所面临的挑战。本文对移动轨迹的存储与精确匹配检索进行深入的探讨与分析。由于不同的移动轨迹数据其数据格式并不一致，本章利用手机移动轨迹数据进行存储设计与计算分析。并将针对移动轨迹的存储与精确匹配检索方法应用到安全监控领域，开发基于分布式架构的犯罪嫌疑人追踪系统。该系统通过检索匹配于给定移动模式的犯罪嫌疑人的手机轨迹，从而确定犯罪嫌疑人的手机设备号。3.1 移动轨迹的精确匹配检索精确匹配检索是指对具体的轨迹或者数据点的进行检索。精确匹配检索，可以分为以下类型：1. 单目标轨迹检索：给定对象标识，查询该对象在轨迹库中的轨迹。例如，给定对象标识及时间范围，查询该对象在轨迹数据库中满足该时间范围的所有记录，并将检索结果按时间有序输出。2. 多目标轨迹检索：给定时空范围，查询满足该时空范围的所有轨迹。例如，给定多个时空点，查询经过这些空间点，并且符合指定时间顺序的全部轨迹。手机轨迹是移动轨迹的一种常见类型，手机移动轨迹本质上反映其持有者的移动轨迹。通过手机移动轨迹我们能够找到不同人物的移动路线，从中辨别出不同的手机。关于手机移动轨迹的精确匹配检索有很多实际的应用场景，目标人物手机的监控识别是其中一个重要的应用场景。针对目标人物手机的监控识别是一种典型的多目标轨迹检索任务。11第三章 移动轨迹的存储与精确匹配检索3.2 目标人物手机识别与追踪的背景介绍如今，视频监控技术已在全国各大城市得到广泛应用，对保障公民人身安全发挥着重要作用。在传统的基于监控视频的安全事件处理方法中，办案人员对摄像头所拍摄到的视频录像进行人工搜索比对，这种方法效率低下且容易产生遗漏。随着图像识别技术的发展，具有人物识别功能的智能视频监控系统获得广泛应用。该类系统基于图像识别技术，对所获取的视频图像进行自动分析，以实现目标人物识别、跟踪、行为轨迹分析等功能。然而，在实际应用中，受到光线、摄像分辨率、人体姿态、遮挡等因素的影响，往往难以仅通过图像分析的方法进行人物身份的自动辨识。更重要的是，当目标人物离开视频监控区域时，就难以再进行持续的追踪。一种可行的追踪方法是针对目标人物携带的手机的追踪技术。在现今的社会，人们出行几乎都会携带手机。当人们使用手机时，移动通信网络中心会在后台记录该手机位置信息。根据给定的手机号码，可以在移动通信网络内实时监控目标手机所处的位置。这种基于移动网络的手机追踪技术的前提是，要预先获取目标手机号码。因此该方法不适用于对未知身份的嫌疑人物的位置追踪。鉴于上述人物追踪方法存在的问题，我们提出来一种结合移动网络记录和视频监控数据的目标人物追踪方法。该方法通过结合移动通信网络数据和视频监控数据，识别监控摄像头拍摄到的目标人物的手机号码，并基于手机号码实现目标人物的定位和追踪。3.3 相关概念及介绍3.3.1手机轨迹的定义在本文中，我们处理的数据集是由移动手机基站中搜集的手机轨迹数据。众所周知，手机网络将覆盖的区域分成若干的蜂窝，每一个蜂窝又是由一个基站提供服务。其记录被记录为五元组(Ui,TFi,TEi,Ci,Ai)如表3-2所示。表中的每一行表明手机Ui在时间TFi至TEi处于蜂窝Ci。Ai是基站记录的其他附属信息，例如手机的设备类型。表 3-2 蜂窝数据格式UkTFkTFkCkU12:20052:4010C1U12:40113:0020C2U22:25082:3020C2U22:31062:3917C9U32:26093:0019C5U42:27102:3018C2为了便于描述以及构建移动轨迹模型，本文将对手机轨迹进行形式化定义，相关的定义如下：时空段：如果一个移动手机Ui在时间TFi,TEi处于蜂窝Ci，那么定义 i= 为一个时空段，Ai表示其他附属说明信息。手机轨迹：手机轨迹是由一系列按照时间排序的时空段构成i=i1,i2,in。在实际的手机轨迹检索系统中，对满足特定时空模式的的轨迹进行检索是非常高效的。因此，我们定义查询模式为如下定义的一系列时空点。时空点：如果一个移动对象在时刻Ti处于位置Loci 我们定义 i= 为一个时空点。时空模式：按照时间排序的时空点序列i=i1,i2,in。轨迹匹配：手机轨迹 i满足时空模式i（ i i），当且仅当满足下述条件: 对于每一个时空点j= j，存在时空段ik= i，且TFikTTEik。为了清晰起见，重要的记号在表3-2进行总结。表3-2 记号总结记号说明i= 时空段表示手机Ui在时间TFi,TEi处于蜂窝Cii=i1,i2,in手机轨迹表示一系列按照时间排序的时空段i= 时空点表示移动对象在时刻Ti处于蜂窝Cii=i1,i2,in时空模式表示按照时间排序的时空点序列3.3.2 轨迹检索任务的定义基于位置的手机轨迹检索任务可以分为两类：单目标轨迹检索与多目标轨迹检索。单目标轨迹检索：给定手机设备号Ux以及时间范围TFx,TEx，检索出手机Ux从时间TFx至TEx的轨迹。返回的轨迹表示为x=x1,x2,xn。特别地，对于轨迹中的每一个时空段xi= 满足TFxTFxiTEx。多目标轨迹检索：给定时空模式i=i1,i2,in，检索出满足模式i的所有手机轨迹。3.4 系统的存储架构设计基于分布式架构的犯罪嫌疑人追踪系统TREST由三层结构组成，如图3-1所示。图3-1 TREST存储结构模型位于最顶层是逻辑视图层，其体现移动轨迹数据的逻辑视图。在此层，轨迹数据被存储到逻辑上的HBase分布式多维表：Base表、Traj表和Map表中。表的模式如表格3-3所示。表格3-3：HBase表TableRow KeyColumnsBaseCiloni,lati,SiTrajUiTFiTEi,Ci,AiMapCiTFiTEi,UiHBase表中的每一条记录都被唯一的row key所标识，表中所有的记录都被存储到HDFS相应的块文件中，并根据row key排序。特别地，Base表包含基站的基本信息，并且用基站编号Ci作为row key以获得对基站检索时更好的检索性能。loni、lati分别表示基站所在位置的经纬度。Si表示其他基站的描述性信息。作为核心结构的Traj表保存了所有的手机记录。表中的每一行对应于一个时空段： i=Ui,TFi,TEi,Ci,Ai.表中的row key表示为UiTFi，是由Ui与TFi组合构成，该row key被设计用于支持单目标轨迹的高效检索，即检索满足在给定时间区间内目标人物的所有时空段。Map表是一张必要的存储着相关信息的冗余数据表以支持快速的多目标轨迹检索。该表的row key是CiTFi，是由Ci和TFi组合构成。当执行多目标轨迹检索时，在给定的时空范围内的全部手机记录能够被快速检索出来。当有新的时空段被记录时，则会被插入到Traj表中并且映射相关信息到Map表中。中间层是Region层，该层对HBase数据表中的数据根据其row key分区到相应的Region中去。在HBase中，Region是分布式存储和负载均衡的最小单元，并被HBase的Region server以分布式的方式进行管理。Region进一步由基于row key的多级线性索引树结构所组织。该索引结构能够支持基于row key的快速数据检索。最底层是物理存储层，是以HBase的持久化存储方式将数据以HFile的形式存储到分布式文件系统HDFS中。3.5 目标人物轨迹检索算法 3.5.1 单目标轨迹检索算法单目标轨迹检索算法如算法3-1所示，该检索是在表Traj执行。给定手机设备号Ux，以及时间区间TFx,TEx。该算法在Traj表中检索出满足row key在UxTFx and UxTEx内的所有记录。每一条检索出的记录都是一个时空段j，当检索出满足条件所有的时空段时，就可以获得目标轨迹x = j。算法3-1： 单目标轨迹检索输入： Ux,TFx,TEx输出： 手机设备Ux在时间范围TFx,TEx的轨迹 x算法步骤:1. x 2. Ks UxTFx3. Ke UxTEx4. 在Traj表中检索row key在Ks,Ke范围的所有记录5. For each UjTFj,TEj,Cj,Aj do6. j Uj,TFj,TEj,Cj,Aj7. x x j 8. Return x3.5.2 多目标轨迹检索算法多目标轨迹检索是匹配满足时空模式=1,2,n的所有手机轨迹。其中i= 。正如在3.3所定义的，轨迹i满足模式i，当且仅当: 对于每一个时空点i= ，必须存在时空段 k= i (3-1)其中，TFkTTEk， (3-2)并且：Ck=Ci (3-3)这就意味着轨迹i相交于时空范围i。其中i充当在执行多目标轨迹检索时的时空约束。因此，正如算法3-2所述，我们使用i= 作为约束条件在Map表中进行检索。参数是一个手机的两个邻近时空段的最大时间间隔。当手机运行在工作模式下，它会在移动网络中进行注册，并且周期性的向邻近基站报告其状态信息。每一条报告信息都会作为一个时空段存储在移动网络之中。两个邻近的时空段记录的时间间隔在几秒至半小时之间。为确保所有匹配的结果都能够被检索到，我们设置间隔为一小时。因为是最大时间间隔，根据公式（3-2），我们得到：Ti-TFkTi. (3-4)因此，只需要检索出满足公式（3-3）及公式（3-4）的时空段即可。在算法3-2中第6行，我们可以根据row key范围 CiTi 和 CiTi ，对Map表进行高效检索，其中Ti=Ti-。在算法3-2的第8行，检索的结果通过过滤条件TEkTi进筛选。在第10行，挑选出轨迹满足每一i时空范围的手机设备号。在第12行，执行单目标轨迹检索以获得匹配轨迹的全部信息。算法3-2： 多目标轨迹检索输入： 时空模式 = 1,2,n, 其中 i=Ci,Ti.输出： 轨迹集 jx算法步骤：1. For each i=Ci,Ti do2. Ti Ti- 3. Ks CiTi4. Ke CiTi5. i 6. 在Map表中检索row key在Ks,Ke范围的所有记录7. For each CkTFk,TEk,Uk do8. if TEkTi then9. i i Uk10. * = 12n 11. For each Uk* do12. k Single-TrackUk,Tl,Tn13. Return k 3.6 实验分析这一节，我们利用广州2013年2月2日0：00 - 8：00，8个小时移动基站数据进行实验。该基站数据集包含位于24,370个蜂窝的590万部手机的1.56亿条时空段记录。我们在由三台工作站搭建起来的集群部署基于分布式架构的犯罪嫌疑人追踪系统TREST。每台工作站的配置为4核、Intel core i5-3470 CPU、3.20GHz、12G内存。所有的工作站运行着Ubuntu 14.04 LTS（64位）操作系统。基于上述配置，我们测试TREST的数据插入效率、单目标轨迹检索效率以及多目标轨迹检索效率。除此之外，可视化的原型系统也将在这一节进行展示。3.6.1 数据插入效率由于手机轨迹是每秒间都在持续产生，因此对于TREST，支持对数据流的高效插入操作就至关重要。为了测试TREST的数据插入效率，我们将包含1.56亿条时空段记录的原始数据分成等数据容量的八个数据子集，用符号S1S8标识。对S1S8的记录依次进行插入。每个数据子集进行插入操作所消耗的时间如图3-2所示。该图表明，八个数据子集进行数据插入操作所消耗的时间基本相同。TREST所存储的数据容量大小会对新数据的插入产生微小的影响。由三个工作站构成的集群在执行数据插入操作时的平均数据插入效率为1.9M/s。由于HBase的横向扩展机制，增加机器数目或者采用性能更强的服务器会在实际部署中明显增强数据吞吐的性能。图3-2 不同数据集执行数据插入所消耗的时间3.6.2 轨迹检索效率为测试在不同规模的数据集上执行检索操作的检索效率，我们将原始数据按时间等分成八个子集T0T7，每个子集包含有一小时的数据，如表3-4所示。接着，我们通过累加子集T0T7构建数据集C0C7。特别地，Ci是子集T0, T1, , Ti的连接。单目标轨迹检索与多目标轨迹检索效率将在这些数据集上进行测试，数据集的其他细节列举在表3-4中。对于每一个单目标轨迹检索任务，手机标识ID与时间范围TF,TE是在数据集中随机选出。另一方面，多目标轨迹检索任务也是由相似的随机方式选出。每一个多目标轨迹检索任务中的时空模式是由一系列时空点构成，而这些时空点是在数据集包含的轨迹中随机采样选出。默认情况下，一个多目标轨迹检索任务的时空点个数是五个。单目标轨迹检索任务与多目标轨迹检索任务分别执行50次，记录检索时间并算出平均检索时间。表3-4 实验数据集图3-3对比了在不同规模的数据集上执行检索任务所消耗的时间。单目标轨迹检索要快于多目标轨迹检索，其平均检索时间约为7ms。这证明了HBase基于key检索的高效性。此外，在数据集C7上执行多目标检索的平均检索时间为352ms。多目标轨迹检索要比单目标轨迹检索慢，这是由于其在匹配多时空点时的计算复杂性。图3-4进一步展示在数据集C7上一个查询模式中时空点个数对多目标轨迹检索效率的影响。其检索时间正比于时空点个数。图3-3 不同数据集执行精确匹配检索的检索时间图3-4 不同时空点数据在执行多目标检索时所消耗的时间3.6.3 原型系统除了对TREST的基本性能检测外，我们基于TREST部署了分布式的犯罪嫌疑人追踪系统。该系统通过检索匹配于给定移动模式的犯罪嫌疑人的手机轨迹，从而确定犯罪嫌疑人的手机设备号。这是一个典型的多目标轨迹检索任务。该系统同时提供了用户友好的基于Web UI的界面，对检索结果进行可视化展示，如图3-4所示。该系统的其他背景在我们之前的研究工作进行了总结16-17。图3-4 a)图3-4 b)图3-4 基于Web UI的可视化原型系统。A)单目标轨迹检索、b)多目标轨迹检索3.7 本章小结在本章中，我们首先介绍移动轨迹的存储与精确匹配检索的主要目标及其挑战性。接下来我们概述了目标人物识别与追踪的背景。针对现有监控技术的不足，我们提出了一种结合移动网络记录和视频监控数据的目标人物追踪方法，这是一种典型的多目标轨迹检索任务。然后，本章对相关概念进行抽象的数学描述。介绍了基于分布式的犯罪嫌疑人追踪系统的存储架构与目标人物轨迹检索算法。在本章的最后，我们对系统的性能进行测试并对测试结果进行了总结与分析。23第四章 时空数据的存储与复杂检索第四章 时空数据的存储与复杂检索在第三章，我们介绍了移动轨迹的存储与精确匹配检索。移动轨迹的精确匹配检索分为单目标轨迹检索与多目标轨迹检索。我们利用多目标轨迹检索算法对目标人物手机进行监控识别，开发基于分布式架构的犯罪嫌疑人识别与追踪系统。更进一步地，在本章中我们深入研究了该问题的扩展问题，即针对时空数据的复杂查询。时空数据是比移动轨迹数据更加宽泛的一类数据，即数据中包含有时间维与空间维属性的数据。例如，空气质量数据、能耗数据、交通流数据、房产交易数据等数据都属于时空数据，而移动轨迹数据是其中一种特殊模态的时空数据。对多种异构的时空数据进行更为普适的存储与复杂计算，成为当前研究所面临的挑战。由于不同的时空数据其数据格式不一，本章利用房产交易数据进行存储设计与复杂检索分析。并将针对时空数据的存储与复杂检索方法应用到房产大数据分析领域，开发基于分布式架构的房产大数据分析平台。该平台针对更加普适的时空数据进行存储与计算，并且支持对时空数据进行更加复杂的聚合、连接、时空范围查询等查询操作。4.1 时空数据的复杂检索时空数据的复杂检索不仅要求对具体的时空点或者针对时空范围进行检索，还要求根据某些属性值进行表的连接或者聚合计算。时空数据的复杂检索，可以分为以下类型：1. 时空数据的聚合检索：按照一个或者多个属性对时空数据进行分组，然后对每个分组执行聚合操作。2. 时空数据的连接检索：指定连接条件，对连接的两张表都存在与连接条件相匹配的数据进行输出。3. 时空数据的时空范围检索：给定时空范围，查询满足该时空范围的相关记录。房产交易数据是时空数据的一种类型，房产交易数据在空间维度反映房屋所处的地理位置，在时间维度反映房屋的购买时间及一系列交易时间。通过对房产交易数据进行分析，不仅能