基于时空插值的海量车辆轨迹数据索引方法 #

朱延冰1，罗嘉贝1，许涛2，徐先瑞3，张迪1，徐栋1，李响1**

（1. 华东师范大学地理科学学院地理信息科学教育部重点实验室，上海 200241；
2. 河南大学计算机与信息工程学院，开封 475001；
3. 上海体育学院经济管理学院, 上海 200438）

2.02.0School of Geographic Sciences，Key Laboratory of Geographic Information Science, Ministry of education, East China Normal University, Shanghai 200241；School of Geographic Sciences，Key Laboratory of Geographic Information Science, Ministry of education, East China Normal University, Shanghai 200241；School of computer and information engineering, Henan University, Kaifeng 475001；School of Economics and Management, Shanghai Institute of Physical Education, Shanghai 200438；School of Geographic Sciences，Key Laboratory of Geographic Information Science, Ministry of education, East China Normal University, Shanghai 200241；School of Geographic Sciences，Key Laboratory of Geographic Information Science, Ministry of education, East China Normal University, Shanghai 200241；School of Geographic Sciences，Key Laboratory of Geographic Information Science, Ministry of education, East China Normal University, Shanghai 200241华东师范大学地理科学学院地理信息科学教育部重点实验室，上海 200241;华东师范大学地理科学学院地理信息科学教育部重点实验室，上海 200241;河南大学计算机与信息工程学院，开封 475001;上海体育学院经济管理学院, 上海 200438;华东师范大学地理科学学院地理信息科学教育部重点实验室，上海 200241;华东师范大学地理科学学院地理信息科学教育部重点实验室，上海 200241;华东师范大学地理科学学院地理信息科学教育部重点实验室，上海 200241200241;;;;;;20024113482788526;;;;;;1376143139813482788526;;;;;;13761431398上海市闵行区东川路500号;;;;;;上海市闵行区东川路500号728527853@qq.com;924434341@qq.com;txu@henu.edu.cn;xuxianrui105@163.com;zhangdee6@gmail.com;xudongvigor@gmail.com;xli@geo.ecnu.edu.cn朱延冰(1994-)，男(满族)，硕士，研究方向为交通GIS;;;;;;李响(1975-)，男，博士，教授，研究方向为集成时空大数据与人工智能的空间分析朱延冰;罗嘉贝;许涛;徐先瑞;张迪;徐栋;李响ZHU Yanbing;LUO Jiabei;XU Tao;XU Xianrui;ZHANG Di;XU Dong;LI Xiang李响国家自然科学基金委员会项目(41771410)；教育部哲学社会科学研究重大课题(19JZD023)2.02.02.02.02.02.02.02.02.02.02.02.02.02.02.01*|*期刊*|*高强, 张凤荔, 王瑞锦, 等. 轨迹大数据:数据处理关键技术研究综述[J]. 软件学报, 2017, 28(04): 959-992.GAO Q, ZHANG F L, WANG R J, et al. Trajectory big data: A review of key technologies in data processing[J]. Journal of Software, 2017,28(4):959−992.<CR>2*|*期刊*|*阎超德, 赵学胜. GIS空间索引方法述评[J]. 地理与地理信息科学, 2004, 20(04):23-26+39.YAN C D, ZHAO X S. The Review of Spatial Indexes in GIS[J]. Geography and Geo-Information Science, 2004, 20(04):23-26+39.<CR>3*|*期刊*|*Zhu Q, Gong J, Zhang Y. An efficient 3D R-tree spatial index method for virtual geographic environments[J]. ISPRS Journal of Photogrammetry and Remote Sensing, 2007, 62(3): 217-224.<CR>4*|*期刊*|*Chen Y, Zhou L, Tang Y, et al. Fast neighbor search by using revised k-d tree[J]. INFORMATION SCIENCES, 2019, 472: 145-162.<CR>5*|*期刊*|*杨光, 王琰. 改进的四叉树图像压缩算法[J]. 沈阳工业学院学报, 2003, 22(4): 33-35.YANG G, WANG Y. A Modified Algorithm for Image Compression[J]. JOURNAL OF SHENYANG INSTITUTE OF TECHNOLOGY, 2003, 22(4): 33-35.<CR>6*|*期刊*|*古力努尔·艾尔肯, 哈力旦·阿布都热依木, 胡申华, 等. 基于改进Otsu与四叉树法的Marangoni凝结液边缘检测方法[J]. 科学技术与工程, 2017, 17(8): 187-191.Gulnur·arken, Halida·abdureyim, HU S H, et al. An Edge Detection Algorithm of Marangoni Condensation Based on the Combination of Optimized Otsu and Quadtree[J]. Science Technology and Engineering, 2017, 17(8): 187-191.<CR>7*|*期刊*|*彭召军, 王青山, 熊伟, 等. 基于改进四叉树的地理实体快速查询算法[J]. 地理空间信息, 2017, 15(1): 32-35.PENG Z J, WANG Q S, XIONG W, et al. Fast query algorithm of geographical entity based on Improved Quadtree[J]. GEOSPATIAL INFORMATION, 2017, 15(1): 32-35.<CR>8*|*期刊*|*郑美红, 陈红卫. 基于四叉树改进的分形图像编码方法[J]. 华东船舶工业学院学报(自然科学版), 2004, 18(4): 71-75.ZHENG M H, CHENG H W. An Advanced Quadtree Method for Fractal Image Coding[J]. Journal of East China Shipbuilding Institute(Natural Science Edition), 2004, 18(4): 71-75.<CR>9*|*学位论文*|*许涛. 基于海量出租车轨迹数据的旅行时间预测[D]. 上海：华东师范大学, 2017.XU T. Travel Time Prediction Based On Massive Taxi Trajectory Data[D]. Shanghai：East China Normal University, 2017.<CR>10*|*期刊*|*张得群, 谢传节, 裴韬. 基于HBase的面向语义单元的室内移动对象索引[J]. 地球信息科学学报, 2017(03): 307-316.ZHANG D Q, XIE C J, PEI T. Semantic Cell Oriented Indoor Moving Objects Index based on HBase[J]. Journal of Geo-information Science, 2017(03): 307-316.<CR>11*|*期刊*|*王凯, 陈能成, 陈泽强. 基于MongoDB的轨迹大数据时空索引构建方法[J]. 计算机系统应用, 2017, 26(6): 227-231.WANG K, CHEN N C, CHEN Z Q. Spatio-Temporal Indexing Method of Big Trajectory Data Based on MongoDB[J]. COMPUTER SYSTEMS APPLICATIONS, 2017, 26(6): 227-231.<CR>12*|*期刊*|*Leonardi L, Orlando S, Raffaeta A, et al. A general framework for trajectory data warehousing and visual OLAP[J]. GEOINFORMATICA, 2014, 18(2): 273-312.<CR>13*|*期刊*|*杨明远, 刘海砚, 朱新铭, 等. MFSTR-tree:面向Argo海洋浮标的时空数据索引[J]. 地球信息科学学报, 2018, 20(05): 665-673.YANG M Y, LIU H S,ZHU X M, et al. MFSTR-tree:An Spatio-temporal Index for Argo Floats Data[J]. Journal of Geo-information Science, 2018, 20(05): 665-673.<CR>14*|*期刊*|*张桂杰, 岳丽华, 金培权. 基于R*-tree的时空数据库索引VC-tree[J]. 计算机工程, 2008, 34(24): 46-48.ZHANG G J, YUE L H, JIN P Q. VC-tree:Spatial-temporal Database Index Based on R*-tree[J]. COMPUTER ENGINEERING, 2008, 34(24): 46-48.<CR>15*|*期刊*|*尹章才, 李霖, 王争王. 基于HR-树扩展的时空索引机制研究[J]. 武汉大学学报(信息科学版), 2007, 32(12): 1131-1134.YAN Z C, LI L, WANG Z W. Spatio-Temporal Index Based on Extended HR-tree[J]. Geomatics and Information Science of Wuhan University, 2007, 32(12): 1131-1134.<CR>16*|*期刊*|*林基艳, 张雅琼, 张慧. 基于出租车GPS轨迹数据挖掘的居民出行特征研究[J]. 计算机时代, 2017(5): 37-39, 41.LIN J Y, ZHANG Y Q, ZHANG H. Research on the characteristics of resident travel based on the taxi GPS trajectory data mining. COMPUTER ERA, 2017(5): 37-39, 41.<CR>17*|*期刊*|*Wonhee C, Eunmi C. Spatial Big Data Analysis System for Vehicle-Driving GPS Trajectory[J]. Advanced Multimedia and Ubiquitous Engineering, MUE/FutureTech 2017. LNEE 448, 2017: 296-302.<CR>18*|*期刊*|*Mckenna A, Hanna M, Banks E, et al. The Genome Analysis Toolkit: A MapReduce framework for analyzing next-generation DNA sequencing data[J]. GENOME RESEARCH, 2010, 20(9): 1297-1303.基于时空插值的海量车辆轨迹数据索引方法|Mass Vehicle Trajectory Data Indexing Method Based On Spatiotemporal Interpolation|国家自然科学基金委员会项目(41771410)；教育部哲学社会科学研究重大课题(19JZD023)|1|朱延冰|ZHU Yanbing|华东师范大学地理科学学院地理信息科学教育部重点实验室，上海 200241|School of Geographic Sciences，Key Laboratory of Geographic Information Science, Ministry of education, East China Normal University, Shanghai 200241|朱延冰(1994-)，男(满族)，硕士，研究方向为交通GIS|上海市闵行区东川路500号|200241|728527853@qq.com|13482788526|13482788526<CR>|2|罗嘉贝|LUO Jiabei|华东师范大学地理科学学院地理信息科学教育部重点实验室，上海 200241|School of Geographic Sciences，Key Laboratory of Geographic Information Science, Ministry of education, East China Normal University, Shanghai 200241||||924434341@qq.com||<CR>|3|许涛|XU Tao|河南大学计算机与信息工程学院，开封 475001|School of computer and information engineering, Henan University, Kaifeng 475001||||txu@henu.edu.cn||<CR>|4|徐先瑞|XU Xianrui|上海体育学院经济管理学院, 上海 200438|School of Economics and Management, Shanghai Institute of Physical Education, Shanghai 200438||||xuxianrui105@163.com||<CR>|5|张迪|ZHANG Di|华东师范大学地理科学学院地理信息科学教育部重点实验室，上海 200241|School of Geographic Sciences，Key Laboratory of Geographic Information Science, Ministry of education, East China Normal University, Shanghai 200241||||zhangdee6@gmail.com||<CR>|6|徐栋|XU Dong|华东师范大学地理科学学院地理信息科学教育部重点实验室，上海 200241|School of Geographic Sciences，Key Laboratory of Geographic Information Science, Ministry of education, East China Normal University, Shanghai 200241||||xudongvigor@gmail.com||<CR>*|7|李响|LI Xiang|华东师范大学地理科学学院地理信息科学教育部重点实验室，上海 200241|School of Geographic Sciences，Key Laboratory of Geographic Information Science, Ministry of education, East China Normal University, Shanghai 200241|李响(1975-)，男，博士，教授，研究方向为集成时空大数据与人工智能的空间分析|上海市闵行区东川路500号|200241|xli@geo.ecnu.edu.cn|13761431398|13761431398

摘要：随着定位和通信技术的发展，道路系统中很多车辆都安装了位置信息的采集、存储及传输设备，所获得的车辆轨迹大数据成为交通研究的重要基础。由于轨迹大数据具有海量性及时空异变性等特点，如何实现对其有效存储和应用成为当前研究的挑战和热点。本文就此提出了一种多时空粒度索引结构，称为“MSTGI”，其可以在建立索引结构的同时对当前轨迹数据进行不同时间粒度的插值，并实现对轨迹信息的快速查询。该方法首先从原始轨迹数据中获取车辆标识符集合，然后将原始轨迹数据按车辆标识符组织成有序轨迹序列，并对该序列进行时间插值、空间插值及状态插值。本文以上海市约一万三千辆出租车连续一个月的轨迹数据为例，将该方法与已有索引方法进行了对比，结果表明，本文方法在保证索引构建效率的同时，有效改善了已有索引方法应用于轨迹大数据时存在的查询及存储效率问题。

关键词：轨迹大数据；时空索引；多时空粒度索引；时空插值

中图分类号：TP3-05

Mass Vehicle Trajectory Data Indexing Method Based On Spatiotemporal Interpolation

ZHU Yanbing1, LUO Jiabei1, XU Tao2, XU Xianrui3, ZHANG Di1, XU Dong1, LI Xiang1

(1. School of Geographic Sciences，Key Laboratory of Geographic Information Science, Ministry of education, East China Normal University, Shanghai 200241;
2. School of computer and information engineering, Henan University, Kaifeng 475001;
3. School of Economics and Management, Shanghai Institute of Physical Education, Shanghai 200438)

Abstract: With the development of positioning and communication technology, many vehicles in the road system have installed location information acquisition, storage and transmission equipment, and the obtained vehicle trajectory big data has become an important basis for traffic research. Due to the characteristics of trajectory big data with massive time and space variability, how to realize its effective storage and application has become a challenge and hotspot of current research. In this paper, a multi-time-space granular index structure called "MSTGI" is proposed, which can interpolate the current trajectory data at different time granularity while establishing the index structure, and realize fast query of the trajectory information. The method firstly obtains a set of vehicle identifiers from the original trajectory data. Then it organizes the original trajectory data into an ordered trajectory sequence by vehicle identifier, and performs time interpolation, spatial interpolation and state interpolation on the sequence. This paper takes the trajectory data of about 13,000 taxis in Shanghai for one month as an example. The method is compared with the existing index method. The results show that the proposed method can not only effectively improve the query and storage efficiency of existing indexing methods but also ensure the efficiency of index construction when applied to trajectory big data.

Key words: Trajectory big data; Spatiotemporal index structure; Multiple spatiotemporal granularity index; Spatiotemporal interpolation

引言

随着定位和通信技术的发展，道路系统中很多车辆都安装了位置信息的采集、存储及传输设备，所获得的车辆轨迹大数据成为交通研究的重要基础[1]。随着轨迹数量的增大，如何有效存储及使用轨迹大数据成为需要解决的问题。传统空间数据库的索引结构多是基于空间分割结构[2]，例如，R树及其扩展版本[3]、K-D树及其扩展版本[4]、四叉树[5-8]等。上述索引结构都属于空间数据分割树，适用于传统稀疏分布的空间数据，但并不适合于空间范围相对固定（比如一个城市内部）的轨迹大数据。针对采集自大量车辆长期行驶的轨迹数据来说，其随着数据量的逐渐增加，一方面会令树状索引机构快速扩张、难以维护，另一方面也会在索引结构中产生大量重叠的最小外接矩形，降低查询效率[9]。因此，需要针对轨迹大数据设计新型的时空数据索引结构和相应的方法。

“将方法带入数据中”是当前应对大数据特征而产生的一种新的索引模式，其表现为针对特定应用场景，提出改进的特定检索方法。例如，张得群等[10]针对室内移动对象数据的三维立体性、复杂性、随机性特点设计了面向室内语义单元的移动对象索引方法SCoII。该方法能够适应大规模的并发更新与查询，具有良好的规模扩展性，规避了大数据给传统数据库带来的性能瓶颈问题，然而该方法需要有每个室内对象的先验知识，不具有通用性。王凯等[11]基于非关系型数据库MongoDB提出了一套基于四叉树的道路网时空索引，可根据感兴趣时段、感兴趣的空间点或空间范围实现针对海量轨迹数据的高效查询，但该方法由于依赖商业数据库产品，构建索引结构受制于数据库自身的局限性，令其效率受到影响。Leonardi[12]针对在海上航行的船只，提出对轨迹点进行多层次分级，使用户可以从不同粒度获得度量的时间和空间的整体视图。杨明远等[13]结合海洋浮标数据的特点，建立了兼容多频率的索引结构MFSTR-tree。该方法将STR-tree索引结构灵活、数据冗余少的优势进一步扩大，有效改善了原有STR-tree应用于 Argo数据中的查询效率问题，然而该方法在单时间切片查询中的效率仍不及 HR-tree的查询效率。此外，也有研究表明HR-tree较好的支持时间点查询，但是对时间段查询的效率不高[14]。为了克服HR-tree在时间段查询上的缺陷，尹章才等[15] 在R-tree基础上分别融入了HR+树、SEST时空索引与快照-增量索引结构思想，然而这种索引的应用范围还有待进一步研究。

在已有研究的基础之上，针对海量出租车轨迹数据，本文借鉴“将方法带入数据中”的思想，提出了一种新颖的车辆轨迹大数据索引方法，称为多时空粒度索引结构，简称MSTGI（即Multiple-Spatio-Temporal-Granularity Index Structure），其可以在建立索引结构的同时对当前轨迹数据进行不同时间粒度的插值，并实现对轨迹信息的快速查询。本文以上海市约一万三千辆出租车连续一个月的轨迹数据为例，将该方法与已有索引方法进行了对比，结果表明，本文方法在保证索引构建效率的同时，有效改善了已有索引方法应用于轨迹大数据时存在的查询及存储效率问题。

本文以下章节安排如下：第2节介绍了涉及到的数据结构，第3节介绍了MSTGI的原理及构建和查询算法；第4节通过真实数据将该索引方法与已有方法进行了比较；第5节总结全文。

数据结构

为更好地描述索引结构相关算法，本文首先对涉及的相关变量和数据结构定义如下：原始轨迹数据，索引后轨迹数据，其变量含义见表1。

表1 轨迹数据集合变量定义

Tab. 1 Trajectory data set variable definition

变量	定义
车辆唯一标识符
经度
纬度
采样时间 线性插值后得到的时间
速度
方向
0-空车，1-载客，-1-停运 原始载客状态 插值后载客状态
插值后车辆位置

原始车辆轨迹数据集，即所有车辆的轨迹数据。另，定义表示第一天的原始车辆轨迹数据。索引前车辆标识符为的有序轨迹数据序列。定义表示车辆标识符为1的车辆按时间顺序产生的轨迹数据;索引后车辆轨迹数据集。定义表示车辆标识符为1的车辆按时间粒度插值产生的轨迹数据序列。

MSTGI索引方法

原理

MSTGI索引方法特别适用于出租车轨迹数据，其结构包含索引层和数据层，如图1所示。MSTGI索引的核心是通过插值使得每一辆车的轨迹数据在时间上呈等粒度分布(即 x1, y1, state1 ~ xn, yn, staten)，其中t0代表着插值的时间粒度。同时将每一辆车轨迹数据的起始时间(StartTime)和所在行号(StartIndex)记录在索引层，从而在查询时可以根据时间，快速的从索引层定位到数据层。根据具体查询时间与起始时间的差为条件构建在数据层中的索引号，最终获得该查询时间基于时空插值的轨迹数据。因此数据量被大量地压缩，查询速度也能得到提升。

在进行插值前要依据不同场景来设定时间粒度，再根据此时间粒度进行数据插值，完成索引结构的构建。

图1 MSTGI索引结构

Fig. 1 MSTGI index structure

索引构建算法

MSTGI索引的初始化大致可以分为三步:（1）从原始轨迹数据中获取不重复的车辆标识符集合,（2）将原始轨迹数据按车辆标识符组织成为有序轨迹序列,（3）对每辆车的有序轨迹序列进行时间插值、空间插值、状态插值。

对原始数据进行插值前，需要将数据量庞大、无序、异频采样的原始数据按车辆标识符组织成有序轨迹序列。首先为不同车辆开辟存储空间，即定义车辆标识符与其轨迹点的轨迹序列carIDwithInfo。然后遍历原始数据，获取该条轨迹数据的车辆标识符carID，并将该轨迹数据存储插入轨迹序列carIDwithInfo，也就是插入该carID对应的存储空间。

本文采用时空插值的原理是每次迭代判断同一车的原始轨迹点时间间隔是否大于时间采样粒度，若时间间隔大于采样粒度则对采样点处前后的原始数据进行插值，得到采样点的位置数据；若时间间隔小于采样粒度则对相邻采样点间的原始数据进行剔除。插值点个数通过公式(1)确定，插值方法如公式(2)~(5)所示。

(1)
(2)
(3)
(4)
(5)

式中: 表示插值时间后一个轨迹点的GPS时间，表示位于插值时间前一个轨迹点的GPS时间，表示采样点的经纬度，表示插值点的载客状态，表示位于采样时间前一个轨迹点的经纬度，表示位于采样时间后一个轨迹点的经纬度，表示采样点处GPS时间。可以看出经插值后得到的新数据是由该插值时间的前后两个点得到。插值后轨迹点时间间隔固定，依据时间查询轨迹数据时，可以通过行号直接定位到轨迹点，将查询轨迹点的时间复杂度降低为，甚至。

索引查询算法

对插值后特定车辆轨迹数据进行查询使，查询条件为查询时间与车辆标识符，输出为查询结果数据，详细算法见附录。

首先获取压缩后车辆轨迹数据集中标识符为的有序轨迹数据。其次，遍历该轨迹数据，获取序列第一项的时间作为该序列起始时间，然后计算查询时间与序列起始时间的差与时间粒度的比值，获得索引指针，最后根据此指针获取轨迹数据。该算法的时间复杂度为，因此查询速度快于商业数据库。

实验与分析

实验环境与数据

实验硬件环境为Intel Core i5-7300U 2.6GHz CPU；8GB内存；128G SSD 硬盘。软件环境为Windows 10 64 bit操作系统，C#开发语言，编译环境为Visual Studio 2017（社区版）。车辆轨迹数据是由车载GPS接收设备和车载状态监控设备共同生成，它包含车辆的位置和状态等信息，能准确的表达车辆在不同时间、空间中的状态。实验使用数据为2016年8月1日约1.3万辆上海市出租车的数据来进行本节的实验。为避免受到商业数据库数据结构的影响，以文本形式存储在硬盘中，总容量1GB，约1千万条轨迹点。

查询效率分析

为了将本文方法进行横向比较，本文选取了MySQL的B+树索引进行创建时间、查询时间和占用空间的对比。创建时间被分为两部分，一部分是导入数据的时间，另一部分为建立索引的时间。从表2中不难发现本文的方法在数据导入时间上与B+树(MySQL)差不多，但是在建立索引时间上明显优于它。

表2 索引查询效能比较分析结果

Tab. 2 Index query performance comparison analysis results

评价指标	本文	B+树(MySQL)
数据导入时间(s)	296	330
建立索引时间(s)	25	145
查询用时(s)	0.010	0.016
占用空间(MB)	82.3	3718

在比较查询时间时，考虑本索引结构通过预先设置时间粒度，达到所有车辆在数据时间上呈均匀分布，故在任意查询时间均能查询到车辆数据。而现有商业数据库只能对某一车辆某一时间的数据进行精确查询，并非任意时间都能查询到车辆轨迹点数据。因此，若查询条件只设为会造成两种方法返回值不匹配，故本节将查询条件设为：查询时间和车辆标识符。

如表2所示，MSTGI索引结构的占用物理空间远小于B+数索引，其原因是MSTGI索引对数据进行了压缩，占用空间仅为MySQL的B+树索引的2.2%。

结论

本文针对不同时空粒度下对车辆位置状态的查询场景，提出了一种多时空粒度索引结构MSTGI，即在建立索引的同时对当前轨迹数据进行插值，使得索引后的数据可快速查询且占用更小的空间。实验结果表明：索引创建时间方面，MSTGI索引将B+树索引效率提升了32%；数据查询效率方面，MSTGI索引将B+树索引效率提升了37%；存储效率方面，MSTGI索引结构占用磁盘物理空间仅为MySQL的B+树索引的2.2%。由于本文的插值方式为线性插值，插值结果可能不在道路上。对于插值结果略有偏差的问题，进行路网匹配将是MSTGI索引方法改进的一个方向。本文提出的方法对解决时空大数据的查询、存储效率问题有着重要的参考价值。

[参考文献] (References)

[1] 高强, 张凤荔, 王瑞锦, 等. 轨迹大数据:数据处理关键技术研究综述[J]. 软件学报, 2017, 28(04): 959-992.GAO Q, ZHANG F L, WANG R J, et al. Trajectory big data: A review of key technologies in data processing[J]. Journal of Software, 2017,28(4):959−992.
[2] 阎超德, 赵学胜. GIS空间索引方法述评[J]. 地理与地理信息科学, 2004, 20(04):23-26+39.YAN C D, ZHAO X S. The Review of Spatial Indexes in GIS[J]. Geography and Geo-Information Science, 2004, 20(04):23-26+39.
[3] Zhu Q, Gong J, Zhang Y. An efficient 3D R-tree spatial index method for virtual geographic environments[J]. ISPRS Journal of Photogrammetry and Remote Sensing, 2007, 62(3): 217-224.
[4] Chen Y, Zhou L, Tang Y, et al. Fast neighbor search by using revised k-d tree[J]. INFORMATION SCIENCES, 2019, 472: 145-162.
[5] 杨光, 王琰. 改进的四叉树图像压缩算法[J]. 沈阳工业学院学报, 2003, 22(4): 33-35.YANG G, WANG Y. A Modified Algorithm for Image Compression[J]. JOURNAL OF SHENYANG INSTITUTE OF TECHNOLOGY, 2003, 22(4): 33-35.
[6] 古力努尔 艾尔肯, 哈力旦 阿布都热依木, 胡申华, 等. 基于改进Otsu与四叉树法的Marangoni凝结液边缘检测方法[J]. 科学技术与工程, 2017, 17(8): 187-191.Gulnur arken, Halida abdureyim, HU S H, et al. An Edge Detection Algorithm of Marangoni Condensation Based on the Combination of Optimized Otsu and Quadtree[J]. Science Technology and Engineering, 2017, 17(8): 187-191.
[7] 彭召军, 王青山, 熊伟, 等. 基于改进四叉树的地理实体快速查询算法[J]. 地理空间信息, 2017, 15(1): 32-35.PENG Z J, WANG Q S, XIONG W, et al. Fast query algorithm of geographical entity based on Improved Quadtree[J]. GEOSPATIAL INFORMATION, 2017, 15(1): 32-35.
[8] 郑美红, 陈红卫. 基于四叉树改进的分形图像编码方法[J]. 华东船舶工业学院学报(自然科学版), 2004, 18(4): 71-75.ZHENG M H, CHENG H W. An Advanced Quadtree Method for Fractal Image Coding[J]. Journal of East China Shipbuilding Institute(Natural Science Edition), 2004, 18(4): 71-75.
[9] 许涛. 基于海量出租车轨迹数据的旅行时间预测[D]. 上海：华东师范大学, 2017.XU T. Travel Time Prediction Based On Massive Taxi Trajectory Data[D]. Shanghai：East China Normal University, 2017.
[10] 张得群, 谢传节, 裴韬. 基于HBase的面向语义单元的室内移动对象索引[J]. 地球信息科学学报, 2017(03): 307-316.ZHANG D Q, XIE C J, PEI T. Semantic Cell Oriented Indoor Moving Objects Index based on HBase[J]. Journal of Geo-information Science, 2017(03): 307-316.
[11] 王凯, 陈能成, 陈泽强. 基于MongoDB的轨迹大数据时空索引构建方法[J]. 计算机系统应用, 2017, 26(6): 227-231.WANG K, CHEN N C, CHEN Z Q. Spatio-Temporal Indexing Method of Big Trajectory Data Based on MongoDB[J]. COMPUTER SYSTEMS APPLICATIONS, 2017, 26(6): 227-231.
[12] Leonardi L, Orlando S, Raffaeta A, et al. A general framework for trajectory data warehousing and visual OLAP[J]. GEOINFORMATICA, 2014, 18(2): 273-312.
[13] 杨明远, 刘海砚, 朱新铭, 等. MFSTR-tree:面向Argo海洋浮标的时空数据索引[J]. 地球信息科学学报, 2018, 20(05): 665-673.YANG M Y, LIU H S,ZHU X M, et al. MFSTR-tree:An Spatio-temporal Index for Argo Floats Data[J]. Journal of Geo-information Science, 2018, 20(05): 665-673.
[14] 张桂杰, 岳丽华, 金培权. 基于R-tree的时空数据库索引VC-tree[J]. 计算机工程, 2008, 34(24): 46-48.ZHANG G J, YUE L H, JIN P Q. VC-tree:Spatial-temporal Database Index Based on R-tree[J]. COMPUTER ENGINEERING, 2008, 34(24): 46-48.
[15] 尹章才, 李霖, 王争王. 基于HR-树扩展的时空索引机制研究[J]. 武汉大学学报(信息科学版), 2007, 32(12): 1131-1134.YAN Z C, LI L, WANG Z W. Spatio-Temporal Index Based on Extended HR-tree[J]. Geomatics and Information Science of Wuhan University, 2007, 32(12): 1131-1134.
[16] 林基艳, 张雅琼, 张慧. 基于出租车GPS轨迹数据挖掘的居民出行特征研究[J]. 计算机时代, 2017(5): 37-39, 41.LIN J Y, ZHANG Y Q, ZHANG H. Research on the characteristics of resident travel based on the taxi GPS trajectory data mining. COMPUTER ERA, 2017(5): 37-39, 41.
[17] Wonhee C, Eunmi C. Spatial Big Data Analysis System for Vehicle-Driving GPS Trajectory[J]. Advanced Multimedia and Ubiquitous Engineering, MUE/FutureTech 2017. LNEE 448, 2017: 296-302.
[18] Mckenna A, Hanna M, Banks E, et al. The Genome Analysis Toolkit: A MapReduce framework for analyzing next-generation DNA sequencing data[J]. GENOME RESEARCH, 2010, 20(9): 1297-1303.

基金项目：国家自然科学基金委员会项目(41771410)；教育部哲学社会科学研究重大课题(19JZD023)

作者简介：朱延冰(1994-)，男(满族)，硕士，研究方向为交通GIS

通信联系人：李响(1975-)，男，博士，教授，研究方向为集成时空大数据与人工智能的空间分析. E-mail: xli@geo.ecnu.edu.cn