下载文档原格式
第４４卷 第３期２０２１年３月计 算 机 学 报ＣＨＩＮＥＳＥＪＯＵＲＮＡＬＯＦＣＯＭＰＵＴＥＲＳＶｏｌ．４４Ｎｏ．３Ｍａｒ．２０２１收稿日期：２０１９ １１ １６；在线发布日期：２０２０ １１ ０６．本课题得到国家自然科学基金（６１７７２２１１，Ｕ１８１１２６３）、国家重点研发计划（２０１８ＡＡＡ０１０１３００）、广东省教育厅创新团队（粤教科函２０１８ ６４／８Ｓ０１７７）、广州市科技计划项目（国际合作）（２０１８０７０１００４３）资助．汤 娜，博士，副教授，中国计算机学会（ＣＣＦ）会员，主要研究方向为时态数据库、大数据管理、移动对象数据库和知识发现．Ｅ ｍａｉｌ：ｓｉｎｃｅｒｅｔｎ＠ｑｑ．ｃｏｍ．朱展豪，硕士研究生，主要研究方向为数据处理与挖掘．李晶晶，博士，副教授，主要研究方向为计算智能与优化．汤 庸（通信作者），博士，教授，博士生导师，主要研究领域为时态数据管理、社交网络与协同计算．Ｅ ｍａｉｌ：ｙｔａｎｇ＠ｓｃｎｕ．ｅｄｕ．ｃｎ．叶小平，博士，教授，主要研究领域为时态数据库、移动对象数据库和知识发现．时空相点移动对象数据索引犘犕 犜狉犲犲汤 娜 朱展豪 李晶晶 汤 庸 叶小平（华南师范大学计算机学院 广州 ５１０６１３）摘 要 随着移动定位技术和无线通讯技术发展，移动对象的应用领域越来越广阔．位置随时间而变化的移动对象产生的时空数据具有规模大、多维性、结构复杂和关系复杂等特点．由于移动对象的运动轨迹大多被限定在特定的交通网络中，因此基于路网的移动对象索引成为时空数据索引研究的一个重要应用分支．目前，针对移动对象历史数据的区域查询优化的研究重点是如何提高窗口查询的效率．这类索引通常以同一线路为单位来组织轨迹数据的存储．索引通常采用两层的Ｒ ｔｒｅｅ索引结构，上层的２ＤＲ ｔｒｅｅ用于索引在某个区域内的线路，下层的２ＤＲ ｔｒｅｅ用于索引某个时间段内在这些区域的移动对象．这类索引在处理轨迹信息的时间维度的时候，仅仅是把时间维度等同于空间的维度来进行Ｒ树维度的扩展．由于Ｒ树算法不能有效地降低最小限定矩形的空间堆叠问题，尤其是在数据量较大、数据维数增加时表现得更为明显．所以，为了提高路网中移动对象时空信息的存储以及查询的效率，本文则将轨迹信息中的时间数据和空间数据整合起来，提出了一种移动对象数据索引ＰＭ ｔｒｅｅ（Ｐｈａｓｅ ｐｏｉｎｔＭｏｖ ｉｎｇＯｂｊｅｃｔＴｒｅｅ）．首先运用映射函数把路网中移动对象运动轨迹的二维时空矩形投影成带参数的一维“时空相点”，并讨论了时空相点之间的偏序关系，建立了基于相点偏序划分的相点序分枝结构，为索引的建立提供了理论支撑．接着论文以ＭＯＮ ｔｒｅｅ索引为基础，以相点序分枝结构来改进其下层索引结构，提出了时空相点移动对象数据索引，该索引能完成运动轨迹时空的一体化查询，能避免类Ｒ ｔｒｅｅ索引中最小限定矩形堆叠导致的效率低下的问题，有效地缩小搜索空间．最后论文实现了索引的增量式动态更新管理．通过实验的对比分析，表明ＰＭ ｔｒｅｅ索引不但能有效提高储存空间的利用率，“一次一集合”的查询模式还提高了查询性能．关键词 时空矩形；路网；移动对象索引；时空映射；相点偏序中图法分类号ＴＰ３１１ 犇犗犐号１０．１１８９７／ＳＰ．Ｊ．１０１６．２０２１．００５７９犜犲犿狆狅狉犪犾 犛狆犪狋犻犪犾犘犺犪狊犲犘狅犻狀狋犕狅狏犻狀犵犗犫犼犲犮狋犇犪狋犪犐狀犱犲狓犻狀犵：犘犕 犜狉犲犲ＴＡＮＧＮａ ＺＨＵＺｈａｎ Ｈａｏ ＬＩＪｉｎｇ Ｊｉｎｇ ＴＡＮＧＹｏｎｇ ＹＥＸｉａｏ Ｐｉｎｇ（犛犮犺狅狅犾狅犳犆狅犿狆狌狋犲狉犛犮犻犲狀犮犲，犛狅狌狋犺犆犺犻狀犪犖狅狉犿犪犾犝狀犻狏犲狉狊犻狋狔，犌狌犪狀犵狕犺狅狌 ５１０６３１）犃犫狊狋狉犪犮狋 Ｗｉｔｈｔｈｅｄｅｖｅｌｏｐｍｅｎｔｏｆｍｏｂｉｌｅｌｏｃａｔｉｏｎｔｅｃｈｎｏｌｏｇｙａｎｄｗｉｒｅｌｅｓｓｃｏｍｍｕｎｉｃａｔｉｏｎｔｅｃｈｎｏｌｏｇｙ，ｔｈｅａｐｐｌｉｃａｔｉｏｎｏｆｍｏｖｉｎｇｏｂｊｅｃｔｓｈａｓｅｘｈｉｂｉｔｅｄａｂｒｏａｄａｐｐｌｉｃａｔｉｏｎｐｒｏｓｐｅｃｔ．Ａｓｍｏｖｉｎｇｏｂｊｅｃｔｓ’ｐｏｓｉｔｉｏｎｖａｒｉｅｓａｓｔｉｍｅｇｏｅｓｏｎ，ｔｈｅｓｐａｔｉａｌｄａｔａａｎｄｔｅｍｐｏｒａｌｄａｔａｇｅｎｅｒａｔｅｄｃｏｎｔｉｎｕｏｕｓｌｙｂｙｍｏｖｉｎｇｏｂｊｅｃｔｓｈａｓｔｈｅｃｈａｒａｃｔｅｒｉｓｔｉｃｓｏｆｍｕｌｔｉ ｄｉｍｅｎｓｉｏｎ，ｃｏｍｐｌｅｘｄａｔａｓｔｒｕｃｔｕｒｅ，ｍａｓｓｉｖｅｄａｔａｓｃａｌｅａｎｄｃｏｍｐｌｅｘｄａｔａｒｅｌａｔｉｏｎｓｈｉｐ．Ｕｓｕａｌｌｙｔｈｅｔｒａｊｅｃｔｏｒｙｏｆｍｏｖｉｎｇｏｂｊｅｃｔｓｗａｓｃｏｎｆｉｎｅｄｔｏａｓｐｅｃｉｆｉｃｒｏａｄｎｅｔｗｏｒｋ，ｓｏｔｈｅｉｎｄｅｘｏｆｍｏｖｉｎｇｏｂｊｅｃｔｓｂａｓｅｄｏｎｔｈｅｒｏａｄｎｅｔｗｏｒｋｈａｓｂｅｃｏｍｅａｎｉｍｐｏｒｔａｎｔｂｒａｎｃｈｏｆｔｈｅｒｅｓｅａｒｃｈｏｆｔｅｍｐｏｒａｌｓｐａｔｉａｌｄａｔａｉｎｄｅｘ．Ａｔｐｒｅｓｅｎｔ，ｆｏｒｔｈｅｑｕｅｒｙｏｐｔｉｍｉｚａｔｉｏｎｏｆｔｈｅｈｉｓｔｏｒｉｃａｌｄａｔａｏｆｍｏｖｉｎｇｏｂｊｅｃｔｓ，ｔｈｅｒｅｓｅａｒｃｈｆｏｃｕｓｏｎｈｏｗｔｏｉｍｐｒｏｖｅｔｈｅｅｆｆｉｃｉｅｎｃｙｏｆｔｈｅｗｉｎｄｏｗｑｕｅｒｙ．Ｕｓｕａｌｌｙｓｕｃｈｋｉｎｄｏｆｉｎｄｅｘｅｓｐａｒｔｉｔｉｏｎｅｄｔｈｅｔｒａｊｅｃｔｏｒｙｄａｔａｏｆｍｏｖｉｎｇｏｂｊｅｃｔｓｂｙｒｏｕｔｅ，ｓｏｔｈｅｔｒａｊｅｃｔｏｒｙｄａｔａｏｆｍｏｖｉｎｇｏｂｊｅｃｔｓｏｎａｓｐｅｃｉｆｉｃｒｏｕｔｅｗａｓｓｔｏｒｅｄｔｏｇｅｔｈｅｒ．Ｓｏｔｈｉｓｋｉｎｄｏｆｉｎｄｅｘｅｓｗａｓａｔｗｏ ｌａｙｅｒＲ ｔｒｅｅｉｎｄｅｘｓｔｒｕｃｔｕｒｅ，ｔｈｅｕｐｐｅｒｌａｙｅｒｗａｓａ２ＤＲ ｔｒｅｅｆｏｒｉｎｄｅｘｉｎｇｔｈｅｒｏｕｔｅｓｉｎａｒｅｇｉｏｎ，ａｎｄｔｈｅｌｏｗｅｒｏｎｅｗａｓａｌｓｏａ２ＤＲ ｔｒｅｅｆｏｒｉｎｄｅｘｉｎｇｔｈｅｍｏｖｉｎｇｏｂｊｅｃｔｓｉｎｔｈｅｒａｎｇｅｓｏｆｒｏｕｔｅｓｉｎａｃｅｒｔａｉｎｐｅｒｉｏｄｏｆｔｉｍｅ．Ｉｎｔｈｅｖｉｅｗｏｆｔｈｅｓｅｐａｐｅｒｓ，ｔｈｅｄｉｍｅｎｓｉｏｎｏｆｔｉｍｅｉｎｔｒａｊｅｃｔｏｒｙｉｎｆｏｒｍａｔｉｏｎｗａｓｔｈｅｓａｍｅａｓｔｈｅｄｉｍｅｎｓｉｏｎｏｆｓｐａｃｅ．Ｓｏｄｅａｌｉｎｇｗｉｔｈｔｈｅｄｉｍｅｎｓｉｏｎｏｆｔｉｍｅ，ｔｈｉｓｋｉｎｄｏｆｔｅｍｐｏｒａｌｓｐａｔｉａｌｍｏｖｉｎｇｏｂｊｅｃｔｉｎｄｅｘｊｕｓｔｅｘｔｅｎｄｅｄｔｈｅｔｅｍｐｏｒａｌｄｉｍｅｎｓｉｏｎｔｏＲｔｒｅｅ．Ｈｏｗｅｖｅｒ，ｂｅｃａｕｓｅｔｈｅａｌｇｏｒｉｔｈｍｏｆＲｔｒｅｅｃａｎｎｏｔｅｆｆｅｃｔｉｖｅｌｙｒｅｄｕｃｅｓｐａｃｅｏｖｅｒｌａｐｐｉｎｇｏｆＭｉｎｉｍａｌＢｏｕｎｄｉｎｇＲｅｃｔａｎｇｌｅ（ＭＢＲ），ａｎｄｉｔｉｓｍｏｒｅｓｅｒｉｏｕｓｗｈｅｎｔｈｅｄａｔａｖｏｌｕｍｅｉｓｌａｒｇｅａｎｄｔｈｅｄｉｍｅｎｓｉｏｎｉｎｃｒｅａｓｅｓ．Ｉｎｏｒｄｅｒｔｏｉｍｐｒｏｖｅｔｈｅｅｆｆｉｃｉｅｎｃｙｏｆｓｐａｔｉａｌ ｔｅｍｐｏｒａｌｔｒａｊｅｃｔｏｒｙｉｎｆｏｒｍａｔｉｏｎｓｔｏｒａｇｅａｎｄｑｕｅｒｙｏｆｍｏｖｉｎｇｏｂｊｅｃｔｓｉｎｒｏａｄｎｅｔｗｏｒｋａｔｓｏｍｅｉｎｔｅｒｖａｌ，ｔｈｉｓｐａｐｅｒｉｎｔｅｇｒａｔｅｄｔｅｍｐｏｒａｌｄａｔａａｎｄｓｐａｔｉａｌｄａｔａ，ａｎｄｐｒｏｐｏｓｅｄａｔｅｍｐｏｒａｌ ｓｐａｔｉａｌｐｈａｓｅｐｏｉｎｔｍｏｖｉｎｇｏｂｊｅｃｔｄａｔａｉｎｄｅｘ（ＰＭ Ｔｒｅｅｉｎｄｅｘ）．Ｆｉｒｓｔｌｙ，ｔｈｉｓｐａｐｅｒｍｏｄｅｌｅｄｔｈｅｓｐａｔｉａｌｔｒａｊｅｃｔｏｒｙｏｆｔｈｅｍｏｖｉｎｇｏｂｊｅｃｔａｔｓｏｍｅｉｎｔｅｒｖａｌａｓａｓｅｔｏｆｔｗｏ ｄｉｍｅｎｓｉｏｎａｌｒｅｃｔａｎｇｌｅｓ，ａｎｄｍａｐｐｅｄｉｔｉｎｔｏａｓｅｔｏｆｓｉｎｇｌｅ ｄｉｍｅｎｓｉｏｎａｌｔｅｍｐｏｒａｌａｎｄｓｐａｔｉａｌｐｈａｓｅｐｏｉｎｔｓｗｉｔｈｐａｒａｍｅｔｅｒｓ．Ｓｅｃｏｎｄｌｙ，ｔｈｅｐａｐｅｒｄｉｓｃｕｓｓｅｄｔｈｅｐａｒｔｉａｌｏｒｄｅｒｒｅｌａｔｉｏｎｓｈｉｐａｍｏｎｇｔｈｅｔｅｍｐｏｒａｌａｎｄｓｐａｔｉａｌｐｈａｓｅｐｏｉｎｔｓｏｎｔｈｅｐｈａｓｅｐｌａｎｅ．Ｂｙｐａｒｔｉｔｉｏｎｉｎｇｔｈｅｐｈａｓｅｐｏｉｎｔｓｗｉｔｈｔｈｅｐａｒｔｉａｌｏｒｄｅｒ，ａＰｈａｓｅ ＰｏｉｎｔＯｒｄｅｒＢｒａｎｃｈｉｎｇｗａｓｃｏｎｓｔｒｕｃｔｅｄ．Ｔｈｅｎ，ｂａｓｅｄｏｎＭｏｎ ｔｒｅｅｉｎｄｅｘ，ｔｈｅｐａｐｅｒｉｍｐｒｏｖｅｄｉｔｓｌｏｗｅｒｌａｙｅｒｏｆｉｎｄｅｘｓｔｒｕｃｔｕｒｅｂｙｕｓｉｎｇｔｈｅＰｈａｓｅ ＰｏｉｎｔＯｒｄｅｒＢｒａｎｃｈｉｎｇｓｔｒｕｃｔｕｒｅ，ａｎｄｐｒｏｐｏｓｅｄｔｈｅｓｐａｔｉａｌ ｔｅｍｐｏｒａｌｐｈａｓｅｐｏｉｎｔｍｏｖｉｎｇｏｂｊｅｃｔｄａｔａｉｎｄｅｘ．ＴｈｉｓＩｎｄｅｘｃａｎｒｅａｌｉｚｅｔｈｅｑｕｅｒｙｏｐｔｉｍｉｚａｔｉｏｎｂｙｔｈｅｉｎｔｅｇｒａｔｉｏｎｏｆｓｐａｔｉａｌｉｎｆｏｒｍａｔｉｏｎａｎｄｔｅｍｐｏｒａｌｉｎｆｏｒｍａｔｉｏｎａｓｓｐａｔｉａｌｐｈａｓｅｐｏｉｎｔｓ，ａｌｓｏｉｔｃａｎａｖｏｉｄｔｈｅｌｏｗｅｆｆｉｃｉｅｎｃｙｃａｕｓｅｄｂｙＭＢＲｏｖｅｒｌａｐｉｎＲｔｒｅｅａｎｄｅｆｆｅｃｔｉｖｅｌｙｒｅｄｕｃｅｔｈｅｓｅａｒｃｈｓｐａｃｅ．Ｆｉｎａｌｌｙ，ｔｈｅｐａｐｅｒｒｅａｌｉｚｅｄｔｈｅｉｎｃｒｅｍｅｎｔａｌｄｙｎａｍｉｃｕｐｄａｔｅｍａｎａｇｅｍｅｎｔｏｆｉｎｄｅｘ．ＢｙｃｏｍｐａｒｉｎｇｔｈｅｐｅｒｆｏｒｍａｎｃｅｏｆＰＭ ｔｒｅｅｉｎｄｅｘｗｉｔｈｔｈａｔｏｆＭｏｎ ｔｒｅｅｉｎｄｅｘ，ｔｈｅｅｘｐｅｒｉｍｅｎｔａｌｒｅｓｕｌｔｓｓｈｏｗｔｈａｔｔｈｅＰＭ ｔｒｅｅｉｎｄｅｘｃａｎｎｏｔｏｎｌｙｅｆｆｅｃｔｉｖｅｌｙｉｍｐｒｏｖｅｔｈｅｕｔｉｌｉｚａｔｉｏｎｏｆｓｔｏｒａｇｅｓｐａｃｅ，ｂｕｔａｌｓｏｉｍｐｒｏｖｅｔｈｅｑｕｅｒｙｐｅｒｆｏｒｍａｎｃｅ．犓犲狔狑狅狉犱狊 ｔｅｍｐｏｒａｌａｎｄｓｐａｔｉａｌｒｅｃｔａｎｇｌｅ；ｒｏａｄｎｅｔｗｏｒｋ；ｍｏｖｉｎｇ ｏｂｊｅｃｔｉｎｄｅｘｉｎｇ；ｔｅｍｐｏｒａｌａｎｄｓｐａｔｉａｌｍａｐｐｉｎｇ；ｐｈａｓｅｐｏｉｎｔｓｐａｒｔｉａｌ ｏｒｄｅｒ１ 引 言交通管理、目标跟踪等大量应用中都存在着基于位置的应用，需要处理大量随着时间而演变的空间数据，即移动对象或移动数据［１］．移动对象数据库（ＭｏｖｉｎｇＯｂｊｅｃｔＤａｔａｂａｓｅｓ，ＭＯＤ）技术成为一个热门的研究领域之一．ＭＯＤ技术对移动对象的位置及其他相关信息进行表示、存储和管理，提供了对移动对象进行过去、现在查询和对未来预测等操作［２ ３］．ＭＯＤ实现的基本功能包括对移动对象数据的存储、查询和更新［４］．移动对象数据具有时间与空间双重特性［５］，并具有多维性、结构复杂性、规模海量性和关系复杂性等特点．因而研究移动对象数据索引对提高查询的效率尤为重要．在移动对象存取这个研究领域涌现了一大批工作［６］．根据索引时态信息的不同，移动对象索引可分为移动历史索引和当前及未来位置索引．当前及未来位置索引研究是针对移动对象位置的不确定范围所做的研究，大多采用函数估值计算，采用的方法有原时空存取方法ＰＭＲ ｑｕａｄｔｒｅｅ［７］、空间转换方法［８］、参数化时空存取方法等．例如，ＴＰＲ ｔｒｅｅ［９］通过在Ｒ ｔｒｅｅ上定义时参范围框形以覆盖移动对象集合，但随时间的推移，边界矩形不断扩大导致了矩形间重叠增加，致使查询性能下降，文献［１０］改进了ＴＰＲ ｔｒｅｅ这个问题．由于基于当前和未来位置的应用往往具有实时性，而且移动对象的位置不断发生变化，所以这一类数据管理研究的其中一个重点在于如何有效地实现数据的更新与存储［１１ １２］．范围查询也逐渐演变为概率范围查询［１３ １４］、连续范围查询［１５］和预测范围查询［１６］这三种［１７］．而对于移动对象历史数据的查询，经典的查询０８５计 算 机 学 报２０２１年包括轨迹查询（某段时间，移动对象的移动轨迹变化）和区域查询两类，区域查询又包括时刻查询（找到时刻狋时在线路狉上的移动对象）和窗口查询（找到时刻狋１至狋２时在线路狉上的移动对象）．针对区域查询优化所建立的索引的研究重点是如何提高时刻查询和窗口查询的效率，优先考虑以同一空间为单位来组织数据和建立索引．有两类建立索引的方法，一类基于一般Ｒ ｔｒｅｅ［１８］上进行时空扩展，把二维空间和一维时间的时空数据转化成“纯”三维空间数据处理，此时时间维度转化为空间的维度．如３ＤＲ ｔｒｅｅ［１９］、ＲＴ ｔｒｅｅ［２０］、ＳＴＲ ｔｒｅｅ［２１］．另一类的索引在每个更新时刻上建立一棵版本树．如ＭＲ ｔｒｅｅ［２２］是在Ｒ ｔｒｅｅ上利用重叠Ｂ ｔｒｅｅ的思想．ＭＶ３Ｒ ｔｒｅｅ［２３］是基于多版本Ｂ ｔｒｅｅ的思想，用一棵ＭＶＲ ｔｒｅｅ来处理时间戳查询和３ＤＲ ｔｒｅｅ来处理长时间间隔．由于移动对象位置不断变化，引起了数据的大量更新，在面向轨迹的查询应用中，这类索引在创建时往往优先考虑以同一个移动对象为单位来聚集数据，即同一移动对象的运动轨迹尽量存储在一起［２４］．如经典轨迹索引ＴＢ ｔｒｅｅ［２５］，它采用了类Ｒ ｔｒｅｅ结构，并在ＳＴＲ ｔｒｅｅ上进行扩展，把同一轨迹的线段储存在每个叶节点中以保存移动对象的运动轨迹．ＳＥＴＩ索引［２６］将静态的空间区域进行非重叠分区，利用分区函数把数据同一轨迹的线段储存在同一分区中［２７］．以上的基于移动历史的索引研究主要是针对移动轨迹没有任何限定的情况下所做的研究．在许多现实场景中，移动对象的运动轨迹并不是杂乱无章的，而是被限制在特定的或者具有一定规律的网络上，例如高速路上的汽车．因而它们的位置信息可以借助网络上固定线路的相对位置来表示．因而相比轨迹无限定的移动对象查询，基于路网的历史查询的复杂度相对降低［２３］．这一类索引通常是一个两层的索引结构．均采用Ｒ ｔｒｅｅ索引结构或是其变种结构进行存储．如Ｆｒｅｎｔｚｏｓ提出的路网移动对象经典索引ＦＮＲ ｔｒｅｅ［２８］，它是一个两层混合索引结构：上层是一棵２ＤＲ ｔｒｅｅ，用于索引道路网络的路段；下层是１ＤＲ ｔｒｅｅ森林，用于索引路段中运动的移动对象．ＦＮＲ ｔｒｅｅ具有良好的窗口查询性能，但对于时间片查询和历史轨迹查询，则需要遍历整个１ＤＲ ｔｒｅｅ森林．ＦＮＲ ｔｒｅｅ还假定移动对象在路网中速度不变．但在现实的应用场景中往往对象的移动不是以同一个速度进行．郭景峰等人提出了ＦＮＲ＋ ｔｒｅｅ索引结构［２９］，它在ＦＮＲ ｔｒｅｅ的基础上增添了一个哈希结构来储存对象的历史轨迹，从而改善了ＦＮＲ ｔｒｅｅ在轨迹查询上的效率．Ｐｆｏｓｅｒ等人提出用Ｈｉｌｂｅｒｔ曲线把复杂的三维空间转化成用Ｒ ｔｒｅｅ表示的低维子空间［３０］，虽然查询处理较ＦＮＲ ｔｒｅｅ要复杂，但可以把移动对象的运动方式表示得更具体．ＤｅＡｌｍｅｉｄａ等人提出了具有两层结构的ＭＯＮ ｔｒｅｅ［３１］，上层是一棵用于索引线路／线段的２ＤＲ ｔｒｅｅ，下层是一个用于索引指定线路中移动对象位置和时间信息的２ＤＲ ｔｒｅｅ森林．在道路表达上ＭＯＮ ｔｒｅｅ提供了两种表达方式，一种是以道路作为基本元素，另一种是将道路表示为折线段，以折线段作为基本元素．当道路长度较大时，ＭＯＮ ｔｒｅｅ会产生大量的死空间，查询效率相对降低．实验表明，相比较于ＦＮＲ ｔｒｅｅ，ＭＯＮ ｔｒｅｅ具有更好的性能，且ＭＯＮ ｔｒｅｅ的两种不同表达方式索引中，基于道路的ＭＯＮ ｔｒｅｅ的查询效率更高．一些研究人员还针对一些混合模式进行研究：（１）同时处理移动对象过去、当前以及未来位置信息的索引模型ＡＭＨ［３２］、ＲＰＰＦ ｔｒｅｅ［３３］、ＰＣＩ［３４］．这类索引往往是移动历史索引与当前未来位置两类索引技术的整合．但由于两种索引结构的更新效率是不同的，所以针对两种不同的查询，需要有两种数据结构来分别存储数据，并建立两种数据结构的联系，将现在的数据不断转化成过去的数据；（２）为了利用多核处理器的并行性以满足大数据处理的需求，提出了基于内存和磁盘的轨迹索引［３５ ３６］，这类工作的挑战是如何处理查询和更新上锁之间的争用．本文针对在限定路网上的历史区域查询，提出一种基于时空相点的路网移动对象数据索引技术ＰＭ ｔｒｅｅ，目的在于提高路网中移动对象时空信息的存储以及历史区域查询的效率．本文首先将路网中的移动对象轨迹信息建模为时空数据矩形集合，通过映射函数将其投影成带参数的一维“时空相点”数据．其次，讨论了时空相点集合上基于相点序分支结构的数据结构．最后，构建了基于时空相点序分枝结构的路网移动对象索引，该索引改进了ＭＯＮ ｔｒｅｅ的下层用于索引指定线路中移动对象位置和时间信息的２ＤＲ ｔｒｅｅ森林，采用相点序分枝结构实现了指定线路中移动对象位置和时间信息的一体化存储和查询，同时可以避免最小限定矩形大量重叠导致的查询效率低下问题；最后讨论了该索引的查询和增量式更新算法．本文主要贡献是：把二维的时空数据矩形通过映射函数投影成带参数的一维“时空相点”数据，实现了时空数据的降维以及时空数据的一体化查询；通过研究时空相点之间的关系提出相点序分支结１８５３期汤 娜等：时空相点移动对象数据索引ＰＭ Ｔｒｅｅ构，该结构可以有效缩减区域查询的搜索范围；构建了基于相点序分支结构的路网移动对象数据索引ＰＭ ｔｒｅｅ，提出了“一次一集合”的查询模式和动态更新算法．本文第２节基于路网的移动对象数据模型和时空相点集合的数据关系，提出相点序分支数据结构；第３节讨论以相点序分支数据结构为基础建立的路网移动对象索引模式ＰＭ ｔｒｅｅ，并研究ＰＭ ｔｒｅｅ的数据查询和更新算法；第４节是相应的实验仿真；第５节是对本文的总结与展望．２ 时空数据结构线路犚由一组固定的有序线段｛〈犪０，犪犾〉，〈犪１，犪２〉，…，〈犪狀－２，犪狀－１〉，〈犪狀－１，犪狀〉｝组成，其中犪犻（０ 犻 狀）为二维平面线段的点，犪０和犪狀分别为线路始点和终点．犚上点犪犻的位置用犪犻关于犪０的距离参数犇犻＝犇（犚，犪犻）表示，当犪犻＝犪０时，犇（犚，犪犻）＝０；当犪犻≠犪０时，犇（犚，犪犻）＝犇（犚，犪犻－１）＋犱（犪犻－１，犪犻），其中犱（犪犻－１，犪犻）是犪犻－１到犪犻之间的欧式距离（１ 犻狀）．一条线路对应了地图中的一条道路．路网是由一组有序线路集合｛狉１，狉２，…，狉犻，…，狉犿｝连接组成的图．移动对象犿在线路狉犻上运动所产生的运动轨迹可以一系列点〈犕０，犕１，…，犕狀〉来表示，犕犻－１＝（犱犻－１，狋犻－１）表示在时刻狋犻－１位于点犕犻－１，距离线路狉犻的始点的距离为犱犻－１，其中犱犻－１＝犇（犚，犪犼）＋犱（犪犼，犕犻－１），其中犪犼是从道路的初始点犪０到犕犻－１之间最靠近犕犻－１的点，犱（犪犻－１，犪犻）是犪犼到犕犻－１之间的欧式距离．下一个时间点狋犻的轨迹则为犕犻＝（犱犻，狋犻），即点犕犻距离线路狉犻的始点的距离为犱犻，相邻两个结点犕犻－１和犕犻组成一个折线段狊犲犵（犕犻－１，犕犻）．定义１． 时空数据矩形ＴＳＤＲ（Ｔｅｍｐｏｒａｌ ＳｐａｔｉａｌＤａｔａＲｅｃｔａｎｇｌｅ）．移动对象犿运动轨迹上的折线段狊犲犵（犕犻－１，犕犻）可用一个平行于坐标轴的时空数据矩形犛犻＝（犱犻－１，犱犻；狋犻－１，狋犻）来表示，其中犱犻－１ 犱犻∧狋犻－１ 狋犻，即（犱犻－１，狋犻－１）和（犱犻，狋犻）分别表示犛犻左下和右上顶点坐标，如图１所示．１ ＴＳＤＲ由上述定义可得，移动对象犿在线路狉上的运动轨迹〈犕０，犕１，…，犕狀〉可以建模为时空数据矩形ＴＳＤＲ序列〈犛１，犛２，…，犛狀〉，其中犛犻＝（犱犻－１，犱犻；狋犻－１，狋犻）．２ １ 时空相点映射ＴＳＤＲ作为一个二维时空矩形，若直接对其进行数据操作，处理效率较低．本小节基于ＴＳＤＲ数据的固有特性运用数学映射方法把ＴＳＤＲ矩形映射成时空相点，从而实现提高移动对象运动信息的处理效率．首先将时空矩形ＴＳＤＲ的左下和右上端点垂直投影到相点轴（Ｐｈａｓｅ ａｘｉｓ）上，得到投影线段［犪，犫］．参见图２所示．犪和犫的值分别为从原点出发沿相点轴到点犪及点犫的距离．距离值的计算参见图３．［犪，犫］可以记作相平面中的时空相点坐标（犪，犫）在相点轴上的线段或是相点坐标（犪，犫）对应的区间．定义２． 时空相点映射ＰｈａｓｅＰｏｉｎｔｓＭａｐｐｉｎｇ．相点映射定义如下：犛＝（犱１，犱２；狋１，狋２）→犘＝（（犪，犫），犱１，犱２，狋１，狋２，犗犽）犪＝犱１槡×２＋狋１－犱１槡２＝狋１＋犱１槡２，犫＝犱２槡×２＋狋２－犱２槡２＝狋２＋犱２槡２，２８５计 算 机 学 报２０２１年其中，犘称为时空数据矩形ＴＳＤＲ对应的时空相点（Ｔｅｍｐｏｒａｌ ＳｐａｔｉａｌＰｈａｓｅＰｏｉｎｔ，ＴＳＰＰ），（犪，犫）称为犘的时空相点坐标，犱１，狋１，犱２，狋２称为犘的时空判定参数，犗犽为相点所属的移动对象．ＴＳＤＲ与相点犘的映射关系如图４所示．为了简化计算和方便显示，把犪、犫均放大槡２倍，则有犪＝狋１＋犱１，犫＝狋２＋犱２．定理１． ＴＳＤＲ相交关系与相点相交等价性．设犜犛犇犚犻和犜犛犇犚犼所对应的时空相点分别为犘犻（（犪犻，犫犻），犱犻１，犱犻２，狋犻１，狋犻２，犗犽）和犘犼（（犪犼，犫犼），犱犼１，犱犼２，狋犼１，狋犼２，犗犿），由时空相点和其对应的区间的概念可以得到：犜犛犇犚犻∩犜犛犇犚犼≠ ［犪犻，犫犻］∩［犪犼，犫犼］≠ ．证明． 犜犛犇犚犻∩犜犛犇犚犼≠ 意味着两个矩形一定存在着相交的面积犛，此面积可以是点、线、面，则一定此面积投影在相点轴上至少有一个点．即［犪犻，犫犻］∩［犪犼，犫犼］≠ ．证毕．定理２． ＴＳＤＲ不相交关系的相点坐标判定．设犜犛犇犚犻和犜犛犇犚犼所对应的时空相点分别为犘犻（（犪犻，犫犻），犱犻１，犱犻２，狋犻１，狋犻２，犗犽）和犘犼（（犪犼，犫犼），犱犼１，犱犼２，狋犼１，狋犼２，犗犿），则有：［犪犻，犫犻］∩［犪犼，犫犼］＝ 犜犛犇犚犻∩犜犛犇犚犼＝ ．证明． 假设［犪犻，犫犻］∩［犪犼，犫犼］＝ 时犜犛犇犚犻∩犜犛犇犚犼≠ ．由于犜犛犇犚犻∩犜犛犇犚犼≠ 意味着两个矩形一定存在着相交的面积犛，此面积可以是点、线、面，则此面积投影在相点轴至少有一个点．即［犪犻，犫犻］∩［犪犼，犫犼］≠ ，则与假设矛盾．所以可以推出［犪犻，犫犻］∩［犪犼，犫犼］＝ 犜犛犇犚犻∩犜犛犇犚犼＝ ．证毕．为叙述方便，下文把相点犘犻（（犪犻，犫犻），犱犻１，犱犻２，狋犻１，狋犻２，犗犽）与犘犼（（犪犼，犫犼），犱犼１，犱犼２，狋犼１，狋犼２，犗犿）对应的区间［犪犻，犫犻］∩［犪犼，犫犼］记为犘犻∩犘犼．定义３．移动对象时空相点模型（ＭｏｖｉｎｇＯｂｊｅｃｔＰｈａｓｅＰｏｉｎｔＭｏｄｅｌ）．移动对象在线路狉犻上的运动轨迹数据ＴＳＤＲ序列可建模为相平面上的一个时空相点ＴＳＰＰ序列〈犘１，犘２，…，犘狀〉．例１． 对于移动对象犗１，犗２，…，犗１３在线路狉犻上运动产生的数据可以建模如表１所示．表１ 移动对象相点数据模型Ｔｅｍｐｏｒａｌ ＳｐａｔｉａｌＤａｔａＲｅｃｔａｎｇｌｅＴｅｍｐｏｒａｌ ＳｐａｔｉａｌＰｈａｓｅＰｏｉｎｔ犗１（０，２；０，２）（２，７；２，６）（（０，４），０，２，０，２，犗１），（（４，１３），２，７，２，６，犗１）犗２（０，２；３，５）（２，７；５，８）（（３，７），０，２，３，５，犗２），（（７，１５），２，７，５，８，犗２）犗３（０，５；５，９）（（５，１４），０，５，５，９，犗３）犗４（２，５；５，９）（（７，１４），２，５，５，９，犗４）犗５（２，７；３，８）（（５，１５），２，７，３，８，犗５）犗６（２，５；３，６）（５，７；６，７）（（５，１１），２，５，３，６，犗６），（（１１，１４），５，７，６，７，犗６）犗７（０，５；２，５）（５，７；５，７）（（２，１０），０，５，２，５，犗７），（（１０，１４），５，７，５，７，犗７）犗８（５，７；０，４）（（５，１１），５，７，０，４，犗８）犗９（０，２；７，９）（（７，１１），０，２，７，９，犗９）犗１０（０，２；２，３）（２，５；３，７）（（２，５），０，２，２，３，犗１０），（（５，１２），２，５，３，７，犗１０）犗１１（２，５；２，４）（０，２；４，７）（（４，９），２，５，２，４，犗１１），（（４，９），０，２，４，７，犗１１） 犗１２（０，２；２，４）（２，７；４，８）（（２，６），０，２，２，４，犗１２），（（６，１５），２，７，４，８，犗１２）犗１３（２，５；６，８）（（８，１３），２，５，６，８，犗１３）２ ２ 时空相点序分枝结构定义４（相点偏序关系）．设Σ为相点集合，对于犘犻，犘犼∈Σ，若犘犻 犘犼，即（犪犼 犪犻）∧（犫犻 犫犼），则称犘犻与犘犼具有关系“槇 ”，记为犘犻 槇 犘犼，“槇 ”是Σ集合上满足自反性、反对称和传递性的偏序关系．定义５．相点序分枝（Ｐｈａｓｅ ＰｏｉｎｔＯｒｄｅｒＢｒａｎｃｈ，ＰＰＯＢ）．对于移动对象的相点数据集合Σ，其对应的偏序划分记为犘（Σ）＝〈犔１，犔２，…，犔犿〉，称犔犻为犘（Σ）中相点序分支（ＰｈａｓｅＰｏｉｎｔＯｒｄｅｒＢｒａｎｃｈ，ＰＰＯＢ）．每一个犔犻是满足“槇 ”的相点的偏序集合，是Σ偏序划分中的一个全序分枝，即犔犻中的每一个相点之间都满足“槇 ”的全序关系，且每一个相点属于且仅属于一个犔犻．例２．例１中移动对象的相点集合Σ，由算法１中的相点偏序划分算法１中的函数犌犈犖犈犚犃犜犈＿犘犕犜狉犲犲犛狋狉可得：犔１＝〈（０，４）〉，犔２＝〈（２，１０）（２，６）（２，５）〉，犔３＝〈（３，７）〉，犔４＝〈（４，１３）（４，９）〉，犔５＝〈（５，１５）（５，１４）（５，１２）（５，１１）（７，１１）〉，犔６＝〈（６，１５）（７，１５）（７，１４）（８，１３）〉，犔７＝〈（１０，１４）（１１，１４）〉．最终可得相点偏序划分犘（Σ）＝〈犔１，犔２，犔３，３８５３期汤 娜等：时空相点移动对象数据索引ＰＭ Ｔｒｅｅ犔４，犔５，犔６，犔７〉．从本例起，为了更清晰地描述相点，采用相点坐标代表相点，省略了相点的时空判定参数和相点对应的移动对象犻犱．定理３． 相点序分枝相交定理．设有相点序分枝犔犻＝〈狆１，狆２，…，狆犼，…，狆狀－１，狆狀〉，对于任意相点犘，若有狆犼∩犘≠ ，则犔犻中所有位于狆犼前的相点均与犘相交，即（狆１∩犘≠ ∧狆２∩犘≠ ∧…∧狆犼－１∩犘≠ ）．若有狆犼∩犘＝ ，则犔犻中所有位于犘犼后的相点与犘均不相交，即（狆犼＋１∩犘＝ ∧…∧狆狀－１∩犘＝ ∧狆狀∩犘＝ ）．证明． 由定义４和定义５可得，对于犔犻中的元素狆犽和狆犼，若犽＜犼，则必有犪犽 犪犼∧犫犼犫犽．现假设狆犼与相点犘相交，即［犪，犫］∩［犪犼，犫犼］≠ ．由［犪，犫］∩［犪犼，犫犼］≠ 犪犼 犫∧犪 犫犼，又犪犽 犪犼∧犫犼犫犽，则有犪犽 犫∧犪 犫犽，因此狆犽∩犘≠ ．同理可得当犽＞犼时，若狆犼∩犘＝ ，则狆犽∩犘＝ ．证毕．例３． 对于例２中的犔６＝〈（５，１５）（５，１４）（５，１２）（５，１１）（７，１１）〉，设相点犘的坐标为（１２，１５）．由［５，１２］∩［１２，１５］≠ ，可得［５，１５］∩［１２，１５］≠ 且［５，１４］∩［１２，１５］≠ ；由［５，１１］∩［１２，１５］＝ ，可得［７，１１］∩［１２，１５］＝．３ 移动对象数据索引３ １ 时空相点移动对象数据犘犕 狋狉犲犲索引图５ 由线路的最小限定框构建的Ｒ ＴｒｅｅＰＭ ｔｒｅｅ索引（Ｐｈａｓｅ ｐｏｉｎｔＭｏｖｉｎｇＯｂｊｅｃｔＴｒｅｅＩｎｄｅｘ）包括两层结构的建立，上层结构是一棵Ｒ ｔｒｅｅ．使用地图数据的线路单元的最小限定框ＭＢＲ（ＭｉｎｉｍａｌＢｏｕｎｄｉｎｇＲｅｃｔａｎｇｌｅ）作为上层索引结构的构建单元，将地图的所有线路的最小限定的框建立的Ｒ ｔｒｅｅ作为上层结构用于索引线路．如图５所示．下层是移动对象轨迹的索引结构，是由一个包含线路Ｉｄ和该线路对应的ＰＭ ｔｒｅｅ结构的哈希映射结构组成，这个哈希映射包含了每一条线路对应的ＰＭ ｔｒｅｅ结构，哈希表中的每一个ＰＭ ｔｒｅｅ结构负责索引其对应线路下的所有移动对象的轨迹数据．下面着重讨论ＰＭ ｔｒｅｅ结构．定义６． ＰＭ Ｔｒｅｅ结构犘犕犜狉犲犲犛狋狉．ＰＭ ｔｒｅｅ结构犘犕犜狉犲犲犛狋狉是由Ｒｏｏｔ ｌｅｖｅｌ、Ｍａｘ ｌｅｖｅｌ、ＰＰＯＢ ｌｅｖｅｌ和Ｏ ｌｅｖｅｌ构成的四层树形结构．如图６所示．（１）Ｒｏｏｔ ｌｅｖｅｌ．逻辑层，表示数据操作的入口．（２）Ｍａｘ ｌｅｖｅｌ．由ＰＰＯＢ ｌｅｖｅｌ中各个ＰＰＯＢ中的最大、最小元ｍａｘ（犔犻）和ｍｉｎ（犔犻）组成，且ｍａｘ（犔犻）在该层的排列顺序与犔犻在算法１中的获取顺序相对应．（３）ＰＰＯＢ ｌｅｖｅｌ．由各个ｍａｘ（犔犻）相对应的ＰＰＯＢ构成，且ＰＰＯＢ中的每个相点均带有一个指向Ｏ ｌｅｖｅｌ对象的指针．（４）Ｏ ｌｅｖｅｌ．由每个相点对应的移动对象构成，用于存储移动对象的具体信息．图６ ＰＭ ｔｒｅｅ结构例４． 例１的移动对象运动轨迹数据所构成的ＰＭ ｔｒｅｅ结构如图７所示．算法１． 索引建立算法犫狌犻犾犱＿狋狉犲犲．输入：犈犇（犈犱犵犲犇犪狋犪）地图数据，犜犇狊（犜犛犇犚犇犪狋犪狊）各线路上移动对象的轨迹数据输出：ＰＭ ｔｒｅｅ索引，其中犎犕（犎犪狊犺犕犪狆）为将上层索引结构中的线路映射到到下层ＰＭ ｔｒｅｅ结构的哈希结构１．ＦＵＮＣＴＩＯＮ犫狌犻犾犱＿狋狉犲犲（犈犇，犜犇狊）２．／ 建上层索引结构／３．ＦＯＲ每一条线路对应的犕犅犚∈犈犇ＤＯ４．犚犜狉犲犲．犐狀狊犲狉狋（犕犅犚）５．ＥＮＤＦＯＲ６．／ 建下层结构 ／７．ＦＯＲ每一条线路下的ＴＳＤＲ集合犜犇犔∈犜犇狊ＤＯ８．犌犈犖犈犚犃犜犈＿犘犕犜狉犲犲犛狋狉（犜犇犔）９．犎犕ａｄｄ犘犕犜狉犲犲犛狋狉１０．ＥＮＤＦＯＲ１１．ＥＮＤＦＵＮＣＴＩＯＮ１２．／ 相点偏序划分及犘犕犜狉犲犲犛狋狉结构的构建算法／４８５计 算 机 学 报２０２１年图７ ＰＭ ｔｒｅｅ结构犘犕犜狉犲犲犛狋狉实例１３．ＦＵＮＣＴＩＯＮ犌犈犖犈犚犃犜犈＿犘犕犜狉犲犲犛狋狉（犜犇犔）１４．／ 生成犜犇犔对应的相点集合Σ的偏序划分，记为犘（Σ）＝〈犔１，犔２，…，犔犿〉（１ 犻 犿），并构建对应的犘犕犜狉犲犲犛狋狉 ／１５．生成犘犕犜狉犲犲犛狋狉的Ｒｏｏｔ ｌｅｖｅｌ１６．ＦＯＲＡＬＬ犜犇ｉｎ犜犇犔Ｄｏ计算其对应的相点，并按照犪值的升序分成若干列，犪值相同的为同一列，同一列的点按照犫按降序排列，形成相点平面上的相点集合Σ；１７．从Σ“最左上方”点（即犪最小，犫最大）开始，犘＝（犪犻，犫犼），点犘（犪犻，犫犼）所在的列记为犮狅犾（犪犻）．列犮狅犾（犪犻）右边最近的邻列记为犚犻犵犺狋犆（犪犻）．在列犮狅犾（犪犻）中，点犘＝（犪犻，犫犼）的列直接后继节点记为犚狅狑犛狌犮犘（犘）．若列犮狅犾（犪犘），其列值大于犮狅犾（犪犻），则该列中第一个满足犫狇 犫犼的节点犓（犪狆，犫狇）称为犘的在列犮狅犾（犪犘）中的后继节点，记为犆狅犾犛狌犮犘（犮狅犾（犪犘），犘）；狀＝０．１８．狀＝狀＋１，建立列表犔狀，且ｍａｘ（犔狀）＝［犘．犪，犘．犫］，１９．／／ｍａｘ（犔狀）为犔狀中的“最大元”，即“首”元素，ｍｉｎ（犔狀）为犔狀“最小元”，即“尾”元素．２０．将犘加入犔狀，Σ＝Σ－｛犘｝；犮狅犾＝犮狅犾（犘．犪）；ｍｉｎ（犔狀）＝［犘．犪，犘．犫］２１．若犘存在着列直接后继节点犚狅狑犛狌犮犘（犘），则令犘＝犚狅狑犛狌犮犘（犘），返回步骤２０；２２．若犚犻犵犺狋犆（犮狅犾）存在，则犮狅犾＝犚犻犵犺狋犆（犮狅犾），查找犆狅犾犛狌犮犘（犮狅犾，犘），如果存在该节点，则令犘＝犆狅犾犛狌犮犘（犮狅犾，犘），返回步骤２０；否则返回步骤２２；２３．在犘犕犜狉犲犲犛狋狉的Ｍａｘ ｌｅｖｅｌ增加一个新节点（ｍｉｎ（犔狀），ｍａｘ（犔狀）），并对该节点构建子树，ＰＰＯＢ ｌｅｖｅｌ层为犔狀，Ｏ ｌｅｖｅｌ层为犔狀中每个相点所属的对象犻犱．２４．若Σ＝ ，退出算法；否则，查找Σ“最左上方”点犓，并令犘＝犓，返回步骤１８．相点偏序划分算法的平均时间复杂度为犗（狀ｌｏｇ（狀））．３ ２ 数据操作基于ＰＭ ｔｒｅｅ索引的数据操作主要分为数据查询和更新两种操作．路网移动对象的查询类型一般分为窗口查询、时间片查询和点查询．窗口查询是指给定一个时间间隔和一个空间矩形区域，查找在该时间间隔中位于给定空间矩形区域上的移动对象．而时间片查询和点查询均为窗口查询的特殊情况，因此小节仅讨论ＰＭ ｔｒｅｅ索引的窗口查询操作．ＰＭ ｔｒｅｅ索引的查询算法，需要下述定理支持．定理４． ＴＳＤＲ相交关系的相点参数判定．设犛犻＝（犱犻１，狋犻１；犱犻２，狋犻２）→犘犻＝（（犪犻，犫犻），犱犻１，犱犻２，狋犻１，狋犻２，犗犽），犛犼＝（犱犼１，狋犼１；犱犼２，狋犼２）→犘犼＝（（犪犼，犫犼），犱犼１，犱犼２，狋犼１，狋犼２），假设犱犻１ 犱犼１，则犛犻∩犛犼≠ （犱犼１ 犱犻２∧狋犼１ 狋犻２）∧（犱犻１ 犱犼２∧狋犻１ 狋犼２）．证明． 必要性．首先将两矩形投影在犡轴，由于犛犻∩犛犼≠ ，意味着两个矩形有交集，即线段［犱犻１，犱犻２］与线段［犱犼１，犱犼２］必须有交集．两线段有交集要满足的条件为犱犼１ 犱犻２∧犱犻１ 犱犼２．再将两矩形投影在犢轴，由于犛犻∩犛犼≠ ，意味着两个矩形有交集，即线段［狋犻１，狋犻２］与线段［狋犼１，狋犼２］必须有交集．两线段有交集要满足的条件为狋犼１ 狋犻２∧狋犻１ 狋犼２．即由犛犻∩犛犼≠ （犱犼１ 犱犻２∧狋犼１ 狋犻２）∧（犱犻１ 犱犼２∧狋犻１ 狋犼２）．充分性．已知（犱犼１ 犱犻２∧狋犼１ 狋犻２）∧（犱犻１ 犱犼２∧狋犻１ 狋犼２），假设犛犻∩犛犼＝ ，及两个矩形没有交集，如果犱犻１＜犱犼１，则必有犱犻１＜犱犻２＜犱犼１＜犱犼２；与前提中的犱犼１ 犱犻２矛盾．如果犱犻１＞犱犼１，则必有犱犼１＜犱犼２＜犱犻１＜犱犻２与前提中的犱犻１ 犱犼２矛盾矛盾．即命题（犱犼１ 犱犻２∧狋犼１ 狋犻２）∧（犱犻１ 犱犼２∧狋犻１ 狋犼２） 犛犻∩犛犼≠ 得证．证毕．当（犱犻１＝犱犼２）∨（犱犼１＝犱犻２）∨（狋犼１＝狋犻２）∨（狋犻１＝狋犼２）时，犛犻与犛犼只有边相交，不满足窗口查询的定义，所以窗口查询的相交判断定理可以简化为５８５３期汤 娜等：时空相点移动对象数据索引ＰＭ Ｔｒｅｅ。
附件2：中国科学引文数据库（CSCD）简介中国科学引文数据库创建于1989年，通过清华大学和中国科学院资源与技术的优势结合和多年的数据积累，目前已发展成为我国规模最大、最具权威性的科学引文索引数据库——中国的《科学引文索引》（SCI），为中国科学文献计量和引文分析研究提供了强大工具。
中国科学引文数据库（CSCD）为年刊，收录我国数学、物理、化学、天文学、地学、生物学、农林科学、医药卫生、工程技术、环境科学和管理科学等领域出版的中英文科技核心期刊和优秀期刊近千种。
数据库的来源期刊每两年进行一次评选，分为核心库和扩展库两部分内容。
其中，核心库的来源期刊经过严格的评选,是各学科领域中具有权威性和代表性的核心期刊；扩展库的来源期刊也经过大范围的遴选，是我国各学科领域较优秀的期刊。
2011-2012版本的中国科学引文数据库共遴选了1124 种期刊，其中英文刊110 种，中文刊1014 种；核心库期刊 751 种（以C为标记）扩展库期刊 373 种（以E为标记）。
中国科学引文数据库是我国第一个引文数据库。
曾获中国科学院科技进步二等奖。
1995年CSCD出版了我国的第一本印刷本《中国科学引文索引》，1998年出版了我国第一张中国科学引文数据库检索光盘，1999年出版了基于CSCD和SCI数据，利用文献计量学原理制作的《中国科学计量指标：论文与引文统计》，2003年CSCD上网服务，推出了网络版，2005年CSCD 出版了《中国科学计量指标：期刊引证报告》。
2007年中国科学引文数据库与美国Thomson-Reuters Scientific合作，中国科学引文数据库将以ISI Web of Knowledge为平台，实现与Web of Science的跨库检索，中国科学引文数据库是ISI Web of Knowledge平台上第一个非英文语种的数据库。
中国科学引文数据库目前已在我国各大科研院所、高等学校的课题查新、基金资助、项目评估、成果申报、人才选拔以及文献计量与评价研究等多方面作为权威文献检索工具获得广泛应用。
内存对象数据库在输配电网平台并发拓扑分析中的应用李飞;黄琦;纪元;贺彦【摘要】首先设计并开发了面向对象的内存数据库,采用了分区、分页存储技术,可用于大规模电网模型的高效缓存和检索[4-5].该内存对象数据库集成进一个实时GIS平台,为实现了大规模并发的拓扑追踪服务提供模型数据.其次本文介绍了基于任务调度队列的拓扑追踪和开关操作系列的并行处理技术,解决了多客户请求的并行执行及其冲突问题.接着本文针对跨分区的操作请求,采用父子任务的形式加入任务队列.最后本文在某省上线系统中进行了压力测试,本文开发的系统在千万级的电网设备模型规模下,每台服务器1 000并发请求的处理时间小于0.1秒.【期刊名称】《贵州电力技术》【年(卷),期】2016(019)011【总页数】6页(P29-34)【关键词】电网GIS平台;并行电网拓扑分析;内存对象数据库;任务调度队列【作者】李飞;黄琦;纪元;贺彦【作者单位】电子科技大学能源科学与工程学院,四川成都610054;贵州电网有限责任公司信息中心,贵州贵阳510623;电子科技大学能源科学与工程学院,四川成都610054;贵州电网有限责任公司信息中心,贵州贵阳510623;深圳航天科工(集团)公司,广东深圳518048【正文语种】中文【中图分类】TM71地理信息系统(Geographical Information System，GIS)是输配电网规划、运行调度与抢修决策支持系统的基础数据管理和可视化平台［1-3］。
拓扑分析是实现检修调度、停电管理及输配电高级决策的基础功能［6-8］。
而并行的拓扑分析服务是GIS平台应用服务器的主要设计难点之一［9-10］。
一方面，电网模型包括了全省输电网和配电网，设备规模达到千万级，遍布全省的各区县局的不同用户，经常出现大规模的并发访问用户请求［11-13］;而且开关分合操作会产生大量设备动态拓扑关系的变动，同时进行的开关分合操作和拓扑追踪操作相互之间可能产生冲突。
中国科学引文索引数据库的简单和高级检索功能中国科学引文索引数据库（Chinese Science Citation Database，CSCD）是中国科学院研究中心与上海科学技术情报研究所合作开发的一种科学文献检索工具。
它汇集了国内外高水平科技期刊的论文信息，为科研人员提供了方便快捷的文献检索和引文分析功能。
本文将介绍CSCD的简单和高级检索功能。
一、简单检索功能CSCD的简单检索功能提供了快速查找和获取文献信息的便捷途径。
用户可以在主页上的搜索框中输入关键词，系统会根据关键词匹配相应的论文、文献等信息。
此外，CSCD还提供了多种检索方式，如按作者、机构、刊名等进行检索。
用户可以根据自己的需求选择最适合的检索方式，以获得准确且全面的文献搜索结果。
二、高级检索功能CSCD的高级检索功能更为灵活和精确。
用户可以通过高级检索页面进入高级检索界面，进行更加细致和精确的检索。
以下是几种常用的高级检索功能：1. 布尔检索：CSCD支持AND、OR、NOT等布尔逻辑运算符的使用，用户可以通过组合关键词和运算符，构建复杂的检索式来达到更精确的检索结果。
2. 范围检索：用户可以设定文章的检索范围，如时间范围、作者姓名、期刊名称等。
这将减少冗余信息，提高检索准确性。
3. 条件检索：CSCD还提供了针对特定条件的检索功能，如文章类型、语言类型、被引频次等。
这些条件检索的选项能够帮助用户快速定位到自己需要的文献信息。
4. 相关性排序：CSCD的高级检索功能还支持根据相关性进行排序。
用户可以根据自己的需求，将搜索结果按照相关性高低进行排序，以找到与自己研究方向最相关的文献。
总结起来，中国科学引文索引数据库(CSCD)提供了简单和高级两种检索功能。
简单检索功能可以帮助用户快速获取相关文献信息，而高级检索功能则更为灵活和精确，能够满足用户对特定条件的检索需求。
科研人员可以根据自己的需要，选择合适的检索方式，以提高检索效率和准确性。
SCI、SSCI、CSSCI、CSCD1、SCI美国《科学引文索引》（Science Citation Index, 简称 SCI ）于1957 年由美国科学信息研究所（Institute for Scientific Information, 简称 ISI）在美国费城创办，是由美国科学信息研究所(ISI)1961年创办出版的引文数据库。
SCI(科学引文索引 )、EI(工程索引 )、ISTP(科技会议录索引 ) 是世界著名的三大科技文献检索系统，是国际公认的进行科学统计与科学评价的主要检索工具，其中以SCI最为重要，创办人为尤金·加菲尔德（Eugene Garfield, September 16,1925～）。
2、CSSCICSSCI为《中文社会科学引文索引》(Chinese Social Science Citation Information)英文名称首字母缩写，是由南京大学中国社会科学研究评价中心研制成功的、我国人文社会科学评价领域的标志性工程。
其用来检索中文社会科学领域的论文收录和文献被引用情况。
CSSCI遵循文献计量学规律，采取定量与定性评价相结合的方法从全国2700余种中文人文社会科学学术性期刊中精选出学术性强、编辑规范的期刊作为来源期刊。
收录包括法学、管理学、经济学、历史学、政治学等在内的25大类的500多种学术期刊，现已开发的CSSCI （1998—2009年）12年度数据，来源文献近100余万篇，引文文献600余万篇。
目前南大核心来源期刊，受到了学术界的广泛认同。
CSSCI期刊目录是中国人文社会科学学术界学术评价体系的重要组成部分，绝大多数高校和科研机构都以此作为研究成果评价标准。
目前，国家教育部已将CSSCI数据作为全国高校机构与基地评估、成果评奖、高校职称评选、项目立项、名优期刊的评估、硕博士人才培养等方面的重要指标甚至是主要标准。
CSSCI数据库已被北京大学、清华大学、中国人民大学、复旦大学、国家图书馆、中国科学院等100多个单位包库使用，并作为地区、机构、学术、学科、项目及成果评价与评审的重要依据。
联机公共检索目录（）中国国家图书馆中国教育和科研计算机网中国科学院文献信息中心国家科技图书文献中心清华大学图书馆北京大学图书馆联机公共数据库超星数字图书馆中国数字图书馆科技会议录索引一系列数据库（清华站点）【地址】原界面链接【类型】多出版类型【年限】（各种出版物起迄年限不一）【描述】（）收录美国计算机协会种期刊、近种会议录，以及近种出版物，包括和非出版物，形成“计算机文献导读”。
这些非的出版物是不提供全文的。
但读者仍然可以看到文摘或是文章的相...美国物理协会期刊【地址】原界面链接【类型】期刊【年限】【描述】（美国物理学会）出版的物理评论系列期刊为物理学各专业领域最受重视的期刊之一.图书馆订购了电子期刊，可通过()访问，也可以通过平台访问，数据回溯至年。
美国机械工程师协会电子出版物(平台)【地址】原界面链接【类型】多出版类型【年限】－【描述】（美国机械工程师学会）电子期刊包含种学报期刊和（应用力学评论），通过平台访问。
数据回溯至年。
<> 请注意：平台上集成有许多学会的出版物，利用检索功能可检索该平台的所有...同方中国知网（交大镜像）【地址】原界面链接【类型】多出版类型【年限】( )【地址】原界面链接【类型】多出版类型【年限】【描述】是目前全球最全面的工程领域二次文献数据库，侧重提供应用科学和工程领域的文摘索引信息，涉及核技术、生物工程、交通运输、化学和工艺工程、照明和光学技术、农业工程和食品技术、计算机和数据处理、应用物理...()【地址】原界面链接【类型】【年限】【描述】（，博硕士论文数据库）收录北美地区余所大学文、理、工、农、医等领域的博硕士论文文摘。
包括了从年美国首篇毕业论文到最近论文的题录，年以后的博士论文增加了由作者写的字文摘...(主站点)【地址】原界面链接【类型】期刊【年限】一般为【描述】荷兰爱思唯尔（）出版集团是全球最大的科技与医学文献出版发行商之一，已有多年的历史。
我国科学引文数据库（Chinese Science Citation Database，简称CSCD）和科学引文数据库（Science Citation Index，简称SCI）是两个重要的学术文献数据库，它们对于我国科学家的学术研究和成果具有重要的参考价值。
本文将以此为主题展开探讨，通过对两个数据库的特点、使用方式、优劣势和对科研工作的影响等方面进行分析，帮助读者更全面地了解这两个学术资源。
1. CSCD的特点我国科学引文数据库是由我国科学院文献情报中心开发和管理的学术文献数据库，涵盖了我国学术期刊的核心内容，包括了自然科学、工程技术、农业科学、医药卫生、哲学、经济、教育、文化等多个学科领域。
CSCD旨在为国内外学者提供我国学术期刊的信息检索、引文分析和评价服务，并集成了引文检索、文献检索和专题分析功能，是我国学术研究领域的重要工具之一。
2. SCI的特点科学引文数据库是由美国 Clarivate Analytics 公司（原瑞士 Ertan Consulting AG 公司)编制和管理的学术文献数据库，涵盖了世界范围内的自然科学、社会科学和人文科学领域，是国际上公认的最具权威性的学术引文数据库之一。
SCI每年都会根据一定的评价标准和指标，对全球范围内学术期刊进行评估和筛选，从而确保其收录的文献具有很高的学术水平和影响力。
3. 使用方式和优劣势比较CSCD作为我国本土的学术文献数据库，在国内具有更好的覆盖面和适应性，特别是对于我国学术研究具有更大的实用性。
而SCI则更注重的是国际学术研究的质量和权威性，在国际学术交流和合作中具有更大的影响力。
在实际的学术研究中，如何更好地利用这两个学术资源，进行合理的引文检索和数据分析，并根据实际需求来选择合适的数据库才是最重要的。
4. 对科研工作的影响在科研工作中，合理地利用CSCD和SCI，对于学术研究的开展、成果的评价和学术交流的活动具有重要的意义。
通过这两个数据库，研究人员可以了解最新的学术研究成果和趋势，进行文献检索和引文分析，评估自己的科研成果，促进国内外学术交流和合作。
中国科学引文索引中国科学引文索引（Chinese Science Citation Database，CSCD）是中国科协下属的中国科学院科技信息所和中国科学技术信息研究所合作创办的文献检索与评价数据库。
该数据库通过收集与中国科学院相关的学术期刊、会议论文、学位论文等科技文献，对这些文献进行标引、检索和评价，以提供科学研究和决策支持相关的信息资源。
中国科学引文索引成立于1997年，是中国科学院发布的唯一一个国内核心期刊双检索评价数据库。
该数据库涵盖了自然科学、工程技术、农业科学、医学与卫生、社会科学等多个学科领域，共计包含了5000多种国家级核心期刊、10000多种核心会议论文和50000多篇学位论文。
中国科学引文索引的主要作用之一是为科研人员提供文献检索服务。
用户可以通过关键词、作者、文献类型、学科分类等多种方式进行检索，查找相关的科技文献。
检索结果以列表形式呈现，用户可以根据自己的需求进行筛选和排序，以获取与研究方向相关且具有高引用量的文献。
这对科研人员来说是一种非常方便和高效的获取信息的方式，有助于他们快速了解和把握科研热点和前沿动态。
除了文献检索，中国科学引文索引还提供了学术评价服务。
数据库对收录的期刊进行了定期评价，并根据综合影响因子进行了排名。
综合影响因子是评价期刊质量和影响力的重要指标，它反映了期刊的被引用情况和每篇文章的平均被引用次数。
一个期刊的综合影响因子越高，意味着它的文章具有更高的被引用数量和影响力。
科研人员可以通过中国科学引文索引了解期刊的综合影响因子，进而选择合适的期刊投稿，提高文章的发表和影响。
中国科学引文索引还为科研机构和政府部门提供科研评价和科技情报分析服务。
它可以根据特定的需求，提供文献引用分析、研究热点分析、学科领域评价等多维度的数据分析。
这些数据分析结果对科研机构和政府部门的科学决策、科研投资和人才引进等方面具有重要的参考价值。
总而言之，中国科学引文索引是中国科学院科技信息所和中国科学技术信息研究所合作创办的文献检索与评价数据库，为科研人员提供了快速获取科技文献和了解期刊质量的服务。
中国科学引文索引csci什么是中国科学引文索引（CSCI）？中国科学引文索引（Chinese Science Citation Database ，简称CSCI ）是中华人民共和国科学技术部和中国科学院共同出资建设和运行的国家级科技信息资源库。
CSCI是一个综合性的科技文献引文数据库，旨在收录与中国有关的科技期刊中的学术论文、学位论文、会议论文等各种学术成果，并提供学术评价、查找和横向对比等多种服务。
CSCI包括两大部分：学科专辑和综合专辑。
学科专辑是根据不同学科的特点，对相关期刊的学术论文进行收录；综合专辑则是对学术论文的全面收录和检索。
在CSCI中，学科专辑部分由众多的期刊组成，每个期刊都经过严格的审定程序和质量评价，确保所收录的论文具有一定的学术水平。
CSCI目前涵盖了科学技术、工程技术和农业科技等多个学科领域，通过学科专辑可以更加便捷地查找到自己感兴趣的学术文献。
而综合专辑则是对所有学术论文的全面收录和检索。
它不限于特定学科，覆盖了从理论研究到实验应用的各个领域。
在综合专辑中，用户可以通过关键词、作者、论文题目等多种方式进行检索，快速找到其所需的信息，满足不同用户的需求。
除了提供学术文献的收录和检索外，CSCI还提供了学术评价服务。
通过CSCI，用户可以查看某个期刊或某篇论文的引用情况，并对学术成果的影响力进行评估。
这对于科研人员选取期刊投稿、学术团体进行绩效评价等方面都具有重要意义。
此外，CSCI还提供了丰富的数据资源和科研分析服务。
用户可以通过数据库快速获取各个领域的热点问题、最新动态和相关研究成果，辅助决策和科研规划。
总而言之，中国科学引文索引（CSCI）是一个综合性的科技文献引文数据库，为广大科研人员提供了丰富的学术资源、学术评价和科研分析服务。
它的建设和发展有力地推动了我国科技研究的进展和创新能力的提升。
国产数据库技术发展第一部分国产数据库技术概述 (2)第二部分发展历程与关键节点 (4)第三部分主流国产数据库产品 (6)第四部分核心技术突破与创新 (10)第五部分行业应用案例分析 (14)第六部分与国际技术的比较分析 (17)第七部分未来发展趋势与挑战 (19)第八部分政策环境与市场机遇 (22)第一部分国产数据库技术概述国产数据库技术发展随着信息技术的迅猛发展和国家大数据战略的推进，国产数据库技术在近年来取得了显著进步。
本文将简要概述国产数据库技术的发展现状，分析其面临的挑战与机遇，并展望未来发展趋势。
一、国产数据库技术概述国产数据库技术是指在中国本土研发、生产的数据库管理系统及相关技术。
这些系统主要服务于政府、企业和个人用户，用于存储、管理和处理各种类型的数据。
国产数据库技术主要包括关系型数据库和非关系型数据库两大类。
1.关系型数据库关系型数据库（RDBMS）是一种以表格形式存储数据的数据库系统，它通过 SQL 语言进行数据的增删改查操作。
国产关系型数据库如OceanBase、TencentDB MySQL、华为 GaussDB 等，它们在性能、可扩展性、高可用性等方面均有优异表现，部分产品甚至达到了国际领先水平。
2.非关系型数据库非关系型数据库（NoSQL）是一种基于键值对存储的数据库，适用于大规模数据存储和高并发访问场景。
国产非关系型数据库如TencentDB Cassandra、华为 OCEANSTOR 分布式文件系统等，它们在大数据处理、实时分析等领域展现出强大的能力。
二、国产数据库技术面临的挑战与机遇尽管国产数据库技术在许多方面取得了突破，但仍面临一些挑战：1.核心技术自主可控：国产数据库需要进一步突破关键技术瓶颈，提高自主研发能力，降低对外部技术的依赖。
2.生态系统建设：国产数据库需要构建完善的生态系统，包括开发工具、应用服务、安全维护等方面的支持。
3.市场认可度：国产数据库需要在市场竞争中树立品牌信誉，提高用户信任度和接受度。
第34卷 第10期2011年10月计 算 机 学 报CH INESE JOURNA L OF COM PU TERSV ol.34N o.10Oct.2011收稿日期:2011-07-10;最终修改稿收到日期:2011-08-29.本课题得到国家重大科技专项基金项目(核高基项目2010ZX01042-001-002)、国家自然科学基金项目(61070054)、中国人民大学科学研究基金(中央高校基本科研业务费专项资金,10XNI018)、中国人民大学研究生基金项目(11XNH120)资助.张延松,男,1973年生,博士,主要研究方向为内存数据库、OLAP 和高性能数据.E -mail:zhangys _ruc@hotm .焦 敏,女,1975年生,博士研究生,讲师,主要研究方向为内存数据库、OLAP 和高性能数据库.王占伟,男,1985年生,硕士,主要研究方向为内存数据库、OLAP 和高性能数据库.王 珊,女,1944年生,教授,博士生导师,中国计算机学会(CCF)高级会员,主要研究领域为高性能数据库、知识工程、数据仓库.周 烜,男,1979年生,博士,副教授,主要研究方向为信息检索、高性能数据库.海量数据分析的One -size -fits -all OLAP 技术张延松1),2)焦 敏1),3)王占伟1),3)王 珊1),3)周 烜1),3)1)(数据工程与知识工程教育部重点实验室(中国人民大学) 北京 100872)2)(中国人民大学中国调查与数据中心 北京 100872)3)(中国人民大学信息学院 北京 100872)摘 要 传统的OL A P 被迅速膨胀的海量数据推动进入了大规模数据分析时代,其主要特点是存储密度大,计算强度大,需要大规模并行存储和处理能力.无论是传统的并行数据库技术还是热点的M apReduce 技术都不得不面对海量数据在大规模并行处理环境下的性能和并行处理效率的问题.以星型模型上复杂多表连接为基础的O L AP 算法的复杂度和并行处理过程中的数据网络传输代价都成为制约性能的重要因素.通过深入分析O LA P 存储模型和查询负载特征,提出了对OL A P 查询中最基础的SPJGA -OL A P 子集在存储、查询处理、数据分布、网络传输和分布式缓存等方面面向海量数据大规模并行处理框架的优化策略和实现技术.通过对T PC -H 和SSB 两个工业界和学术界公认的测试标准的分析,评估了技术的可行性.提出了以内存predicate -v ect or DDT A -JOIN 算法为核心的并行内存OL A P 架构,以维表上规范化的谓词向量操作替代了多样的连接执行计划,实现以一种查询处理模型同时满足集中式处理和大规模并行O LA P 处理的需求,充分利用现代计算机的硬件优势,最小化网络传输和O L AP 查询处理代价.实验中分析了在1T B 和100T B 数据集中数据分布策略的存储代价和传输代价,通过并行OL A P 代价模型和实际数据的实验测试验证了技术的可行性和并行处理效率.关键词 OL A P;海量数据分析处理;谓词向量;星型模型中图法分类号T P 311 DOI 号:10.3724/SP.J.1016.2011.01936O ne -size -fits -all OLAP Technique for Big Data AnalysisZH ANG Yan -Song1),2)JIAO Min1),3)WAN G Zhan -W ei1),3)WANG Shan1),3)ZH OU Xuan1),3)1)(K ey L abor ator y of Data Eng ineering and K now led ge Eng ineering (Renmin Univ ersity of Ch ina)of M inistry of E ducation,B eij ing 100872)2)(Na tional S urv ey Resear ch Cente r at Ren min Univ er sity of China ,Beij ing 100872)3)(S choolof I nf ormation ,R enmin Univ ersity of Ch ina ,B eij ing 100872)Abstract T he traditio nal OLAP is pushed into large scale analy sis era by rapidly ex pending big data volume.The major features are high sto rage density,heav y w or klo ad,larg e scale storage and processing capacity.Both traditio nal par allel database and the hot topic M apReduce technique have to face the critical issues of performance and parallel pro cessing efficiency o f big data analyt-i cal pro cessing in large scale par allel processing framew o rk.The performance of star schema based OLAP w ith star -join is limited by pr ocessing co mplex ity and netwo rk tr ansm issio n cost in parallel pro cessing.This paper makes a deep analysis of features of sto rage m odel and w orkload of OLAP,proposes the o ptimization mechanism s and im plementation technolo gies for the most fun -damental SPJGA -OLAP subset in sto rage,pr ocessing ,distributio n,netw ork transmission,and distributed buffering.The technical feasibility is evaluated w ith the co mmo nly accepted TPC -Hindustr ial benchm ar k and SSB academ ic benchmark.T his paper proposes the predicate -vecto rDDT A -JOIN centric parallel OLAP fr am ew or k,replacing the diverse join ex ecutio n plans with no rmalized predicate -vecto r processing,and enables o ne -size -fits -all OLAP model for both cen -tral pro cessing and large scale parallel processing by making adv antage of now adays hardw are,minim izing netw ork tr ansm issio n co st and pro cessing cost.The analysis of the storage co st and netw ork transmission cost fo r distribution mechanism with datasets of 1TB and 100TB is given.The technical feasibility and parallel pr ocessing efficiency are verified by OLAP co st mo del analy -sis and real data ex periments.Keywords OLAP;big data analy tical processing;predicate -v ector;star schema1 引 言OLAP 是一种多维数据分析处理模型,基于关系数据库的OLAP(Relational OLAP,ROLAP)是一种面向分析型负载的读密集型查询处理.OLAP 以星型模型和雪花型模型为存储模型,一般由一个事实表和多个维表组成,OLAP 的基本功能是切片、切块、上卷、下钻、旋转等操作,即在事实表与维表连接的基础上进行不同粒度的分组聚集计算.在海量数据处理时代,T B 级甚至PB 级的数据需要大规模并行计算网络的支持,巨大的存储、连接、传输和聚集归并等代价使SQL 引擎不堪重负.SQ L 引擎以传统的事务型处理为基础(OLTP),相对于OLAP负载以数据计算为中心的查询处理模式显得过于复杂,一方面复杂的事务和并发机制增加了冗余的代码代价,另一方面面向大数据集的复杂多表连接操作缺乏强有力的技术支持.以传统的并行事务处理为基础的并行数据库技术在扩展性方面受分布式事务控制机制的制约而缺乏良好的可扩展性,当前新兴的分析型数据库(如Ver tica 、ParAccel 、Greenplum 等)虽然面向分析型数据处理的特征优化了存储、查询处理和并行计算等技术,但其查询处理技术仍然带有OLTP 查询处理引擎的影子,是一种由通用SQL 引擎面向OLAP 负载的特殊优化技术.MapReduce 是一种大规模并行计算模型,它良好的扩展性使其成为海量数据大规模OLAP 处理的候选技术方案,但M apReduce 在解决多表连接问题时低下的性能使其难以适应复杂模型的OLAP 处理.因此,问题的关键是,无论是并行数据库技术还是MapReduce 技术都没有根据OLAP 的本质特征来创建订制式的并行存储和处理框架,优化工作难以进一步深入.图1显示了SQL 与OLAP 的包含关系.SQL 可以看作是查询处理技术的全集,包括事务处理和分析型处理,TPC -C 和T PC -E 是典型的OLT P 负载.OLAP 相当于SQL 集合中面向分析型处理的子集,以T PC -H 为代表,查询负载以批量更新和读密集型复杂查询为特征,包含了复杂的子查询嵌套结构.SPJGA -OLAP 是本文提出的OLAP 基本操作集,以OLAP 中最基础的S:选择,P:投影,J:连接,G:分组,A:聚集为主,面向OLAP 模型标准的切片、切块、上卷、下钻、旋转等操作,排除了子查询等复杂操作.SPJGA -OLAP 是通用OLAP 的核心功能子集.SQL OLAP SPJGA -OLAP图1 SQL 与OL A P 的包含关系本文的研究以OLAP 核心的SPJGA -OLAP 操作集上的优化为中心,提出了面向星型模型特点的以维表为中心的分布式存储模型,将事实表对维表的数据依赖规范化为bitm ap 过滤器,通过分布式维表列存储缓存策略和分组编码谓词向量技术最小化OLAP 处理时的网络传输代价.本文的贡献主要体现在以下几个方面:(1)将OLAP 最核心的操作集SPJGA -OLAP 分离出SQL 集合,从而使优化的目标局限于具有最大并行处理潜质的标准多表连接分组聚集计算上,简化了大规模并行计算模型的复杂度;(2)提出了以维表为中心的海量数据分布式存储策略,以最低的负载均衡和数据更新同步代价服务于操作型BI 需求;(3)将OLAP 对应的SQL 操作分解为过滤器、分组器、聚集器,连接谓词根据模式建立内部key -address 映射,将复杂的SQL 简化为简单的谓词表达式和属性输入参数,支持OLAP 向非SQL 查询193710期张延松等:海量数据分析的O ne -size -fits -all O L AP 技术处理引擎的迁移和与各种SQL引擎的融合;(4)谓词向量技术将多表连接的数据依赖规范化为各个维表上的bitm ap过滤器,最小化并行处理时数据依赖所产生的网络传输代价;(5)分布式缓存机制充分利用处理节点的内存容量来优化网络传输代价,减少同步更新代价.本文首先在第2节分析OLAP模型特征和相关研究的技术路线和成果;在第3节中给出SPJGA-OLAP模型的描述和实现技术;在第4节中设计并行SPJGA-OLAP代价模型和实验,并分析实验结果;最后给出论文的结论并讨论了进一步的工作.2 OLAP模型分析和相关工作2.1 TPC-H和SSB模型分析OLAP计算模型的复杂度取决于数据模型的特征.图2中显示了工业界和学术界普通采用的TPC-H和SSB标准.T PC-H是一个双事实表结构,PART SU PP和LINEITEM都是事实表,以组合键(PART KEY,SU PPKEY)连接,OREDER表可以看作是LINEITEM事实表的辅助表,LINEITEM 表以(L_ORDERKEY,L_LINENUM BER)为主键,因此OREDER表与LINEIT EM表的连接通常采用索引连接.在TPC-H的22个标准测试查询中,查询计划树中的主要执行部分是事实表与多个维表连接的查询子树.考虑到并行计算环境下的数据分布,由于OREDER表与LINEIT EM表是1 4的对应关系,通用的规则是将OREDER表与LINEITEM 表按L_ORDERKEY进行H ash分布以减少并行连接时节点间的数据传输代价,提高节点的并行处理能力.但LINEITEM表无法同时满足与OREDER 表和PARTSUPP表进行H ash分布的需求,TPC-H中只有Q9涉及LINEITEM表与PART SU PP 表的连接操作,而LINEITEM表与OREDER表的连接数量较多,因此数据分布策略只考虑OREDER 与LINEITEM表.图2 T P C-H和SSB模型TPC-H在模式上形成雪花状结构,因此查询计划中连接操作较多.对于集中式处理模型,雪花状结构能够最小化存储代价,但对于并行计算模型,雪花状结构增加了大量的节点间数据复制或传输代价,LINEITEM表与OREDER表以及其它维表上的大量连接操作在执行代价和数据分布代价上都较大.因此并行计算环境下模式设计与集中式环境下的模式设计有所不同,考虑的首要问题是复制与传输代价而不是存储代价,即需要采用物化或非规范化思想将复杂的雪花状模型简化星型模型,将聚集计算属性尽量归并到事实表中,而维表只保留基本的选择和分组属性,将OLAP查询计划规范化为维表上的过滤→与事实表连接→分组聚集计算模式的简单操作.只有简单的存储模型和简单的计算模型才能最大化大规模并行处理的收益.图2中的SSB标准[1]是TPC-H标准的星型化1938计 算 机 学 报2011年模型,目前被学术界所广泛采用.它将模式清晰地分解为四个维表和一个事实表,消除了T PC-H中LIENITEM与ORDER表的巨大连接代价,消除了雪花状模型带来的复杂查询执行计划,从而使其更加适合于大规模并行计算环境下的简单数据分布.两种模型的差异还体现在维表数据量上,以SF= 1000(Scale Factor=1000,对应1TB的测试数据集)为例,TPC-H中5个维表的数据总量为50188825KB,而SSB的4个维表数据总量为4062216KB,所占的比例分别为约5%和4 .维表不同的数据量决定着在大规模并行计算环境下采用什么样的数据分布与数据传输策略以及各种策略的执行效率.我们将在后面的部分继续讨论针对模式特点进行的优化工作.2.2 相关工作在关系操作中,连接操作依赖于两个不同的数据集,本文将维表定义为事实表连接依赖数据集(join dependency dataset),连接依赖数据集可以是整个维表、维表上的选择和投影子集、维表属性列或在维表上生成的H ash表.当处理节点获得连接依赖数据集后,各节点即可执行并行查询处理.因此并行数据库优化工作的核心问题是优化连接依赖数据集的复制和传输效率[2].例如,在TPC-H中可以将LINEITEM表与OREDER表按L_ORDERKEY 和ORDERKEY进行H ash分布,保证两表在处理节点上的并行连接性能.当SSB中节点数量较少时,较小的维表可以采用全复制的方式复制到每个处理节点上以支持完全并行的查询处理,其代价是冗余复制的空间代价和维表更新时较高的同步代价.主流的数据库,如T er a Data、Greenplum、ParAccel等一般采用on-the-fly传播的方式在并行查询执行过程中动态分布连接依赖数据集.当维表上的选择率较低且维表数据量较小时,网络传输的效率较高(Gpbs网络的有效传输效率高于单磁盘的数据传输效率).但OLAP负载与OLT P负载不同之处在于, OLT P查询中选择率一般较低,以点查询为主,而OLAP中查询选择率很高,以范围查询为主,在SSB 测试查询的4个维表上,选择率最大值分布在1/5~ 6/7,因此网络传输的数据量依然较大.针对SSB特征的OLAP查询负载,很多研究[3-7]采用最简单的维表全复制策略,包括并行数据库、DB-cluster以及M apReduce模型上的研究,通过减化数据分布模型的方式简化并行计算模型,从而减少并行计算时高昂的网络传输代价.否则,由于事实表是多外键结构,与任何一个维表的连接操作都需要将两个表按特定的连接属性在节点中重新H ash分布后并行处理,网络传输代价非常高昂.文献[8]分析了当前OLAP的新趋势,其中操作型BI(operational BI)的需求与传统OLAP中只读型数据处理的假设相冲突,因此传统OLAP中的物化策略、预处理策略、维表层次编码策略等失去了假设的基础,全复制策略也面临着巨大的同步更新代价.当前解决操作型BI的主要技术路线是双事实表,如SAP[8]和V ertica[9]都采用了双事实表技术来同时提供分析型和操作型处理.但从实际应用特点来看,典型的电子商务企业,如Amazon、淘宝、阿里巴巴等,更新不仅仅体现在不断追加的交易数据,而且包括不断更新的维表数据,而维表数据的变化直接影响OLAP的执行结果.双事实表技术只能解决数据迁移过程中的操作型问题.2.3 海量OLAP时代模型设计原则海量OLAP意味着巨大的数据存储、访问、计算、传输和同步代价,而且需要具有良好的可扩展性支持.大规模并行计算的核心是简单的可并行计算模型和简单高效的数据分布模型.数据仓库的基本特征是按主题组织数据,也就是说一个数据仓库的数据模型在逻辑上就是一张表,简单的数据模型能够支持M apReduce这样的大规模可扩展并行计算框架.为了支持简单并行计算,我们需要维护数据模型的单一性,即以事实表为数据存储和并行处理的中心,从模式设计上缩减维表的规模,避免庞大的连接表或维表所产生的数据分布与并行连接代价.也就是说模式设计应该从TPC-H的以业务逻辑为中心向SSB的以分析逻辑为中心的设计原则转移.从并行计算设计上,OLAP处理集中在易于并行计算的SPJGA-OLAP子集,对于TPC-H中复杂的迭代子查询处理,我们的原则是将其中SPJGA 操作子树并行化,查询树中其它难以并行化的部分交给SQ L引擎来处理,即我们的研究重点集中在并行化收益最大的SPJGA操作部分,不做通用的并行SQL查询优化.3 SPJGA-OLAP模型研究3.1 存储模型本文的研究以SSB模型为基础.SSB是以事实表为中心的星型模型,我们提出了反转星型模型的并行存储模型,即以维表集中存储为中心,以事实表193910期张延松等:海量数据分析的O ne-size-fits-all O L AP技术水平分片为外围处理节点.反转星型模型的优点是简单,维表集中存储能够消除操作型BI 所面临的实时更新所产生的数据复本同步代价,整个存储模型简化为以事实表为中心的分布式单表存储结构,易于数据分布和保持负载均衡,通过分布式缓存策略利用各处理节点内存来加速连接和分组操作.图3所示的存储模型是并行计算框架内的逻辑存储模型,在实际应用中需要与具体的物理存储模型相结合,如在各个处理节点内采用列存储模型[10-11]、压缩等存储优化技术.图3 反转星型存储模型3.2 OLAP 查询功能分解SQ L 具有复杂的语法结构,在SPJGA -OLAP 中,SQL 语法可以简化为三类对象:过滤器、分组器和聚集器.图4显示了SSB 对应的SQL 命令和功能分解,g roup -by 子句中的c _nation 是查询的分组器,用于构建g roup -by 操作的H ash 表;w here 子句中的谓词一部分是连接谓词,与模式中事实表与维表之间的主外键引用参照完整性约束条件相对应,维表上的谓词表达式起到过滤器的作用,在SSB 的SQ L 命令中只包括维表属性上的直接谓词;SELECT 子句中的SU M ( )为聚集器,用于描述事实表度量字段上的聚集计算.图4 SSB 查询分解示例因此,对于SPJGA -OLAP,复杂的SQL 被转换为几个标准的输入参数接口,我们可以将SPJGA -OLAP 定义为NoSQL 模式的API,在算法设计和执行层面上独立于SQL 引擎,避免基于传统的事务型查询处理引擎的设计在OLAP 处理时的效率损失,同时也可以通过标准的SQL 转换接口嵌入传统的SQL 引擎中,作为SPJGA -OLAP 类查询任务的并行处理加速器.通过查询功能的分解,维表只起到过滤器和提供分组器的作用.我们将过滤器优化为bitmap,即用一位来表示维表对应的记录是否满足该维表上所有谓词条件.一方面我们将事实表与维表的连接操作简化为事实表按外键属性与bitm ap 进行匹配,缩减了连接依赖数据集的大小,另一方面,通过维表主键与bitmap 数组下标的直接映射(维表主键一般为自然序列),事实表与bitmap 的连接简化为事实表根据外键值直接访问对应下标的bit 位.3.3 谓词向量并行DDTA -OLAP 算法在反转星型存储模型和OLAP 查询分解的基础上,并行集群上的OLAP 处理被分解为4个阶段:(1)查询改写.将SQL 查询改写为在每个维表上的谓词操作,为每个维表生成唯一的谓词向量(predicate -vector ),谓词向量表示为与维表记录数量等长的bitmap,每一位置0或1,表示该维表记录是否满足维表上所有的谓词.(2)谓词向量广播.通过广播的模式将中心节点生成的谓词向量传播到各处理节点的内存缓冲区中,为并行OLAP 处理做数据准备.采用广播方式一方面降低网络传输延迟,另一方面在节点规模扩大时保持网络传输延迟的稳定性.(3)并行OLAP 处理.每个处理节点拥有自己独立的事实表数据分片,获得了维表谓词向量后即可独立地完成连接操作.图5显示了基于谓词向量1940计 算 机 学 报2011年的连接操作过程.我们在前期研究[12]中提出了DDT A -JOIN 算法来执行OLAP 的多表连接操作,其基本原理是将维表主键顺序化使其与内存维属性列数组的下标直接映射,从而使事实表中的维属性外键值可以直接映射到内存维属性列数组的下标,从而将复杂的多表连接操作优化为简单的按事实表外键值进行内存按地址访问操作.我们将维表属性列进一步优化为整个维表对应一个bitm ap,事实表通过直接访问内存谓词向量bitmap 完成在维表上的过滤操作.图5 基于谓词向量的OL A P 连接操作图5表示一个标准的OLAP 查询由SQL 改写为对指定维表的谓词操作,并将查询结果存储为内存bitmap 形式;在扫描事实表的过程中按事实表中对应的各个维属性外键值直接映射各个谓词向量bitmap 指定的数据位,并根据多个位进行与操作的结果来判断当前记录是否满足连接条件,满足连接条件的记录再从内存维属性列中按照地址直接映射抽取分组属性值,传递给分组聚集器进行聚集计算.谓词向量优化技术最小化了连接依赖数据集,减少网络传输代价.(4)聚集结果集归并.在T PC -H 和SSB 标准中,聚集函数为可分布式聚集函数(SUM ,COUNT )和代数可分布式聚集函数(AVERAGE),因此各个并行处理节点在各自事实表分片上的聚集计算结果具有可归并性,聚集计算可以下推到并行处理节点内执行.如果聚集函数是不可分布式聚集计算函数,如MEDIAN 、RANK 、PERCENT ILE 等,则必须将连接结果集汇集到中心节点后由中心节点完成最终的聚集计算任务.OLA P 查询的结果集以分组聚集计算结果为展示形式,结果集的大小取决于各分组属性的集势(cardinality,即不重复值的数量),通常情况下远远小于连接的记录数量.如SSB 的13个测试查询中,分组聚集结果集最多只有800条记录,远远小于查询中满足条件的连接记录数量.在并行处理规模较小时,我们采用集中式H ash 归并算法来处理并行OLAP 结果集,当并行处理规模较大时,我们采用迭代归并树算法来处理聚集归并问题(迭代归并树算法用于解决大规模集群中查询结果子集的聚集归并问题,与Reduce 功能类似,但采用类似于B +-T ree 的结构,优化归并过程中的网络连接数量和网络传输代价,在本文中不做过多讨论).通过对OLAP 并行查询算法的优化,我们将各种SPJGA -OLAP 负载规范化为统一的并行OLAP 处理模型,实现one -size -fits -all 模式的查询执行计划.3.4 维属性列分布式缓存策略谓词向量将维表简化为bitmap,但OLAP 查询中的分组属性和维表之间的谓词属性如果被压缩到谓词向量中,需要将对应属性值编码并替代谓词向量中的位编码,从而增加谓词向量的宽度.如图6所示,在customer 维表上有选择谓词 c _r egion = AM ERICA 和分组属性c _nation ,则维表需要提供两种类型的数据,一是谓词向量,用于标识哪条维表记录满足选择谓词条件,二是分组属性,将满足选择条件的分组属性提供给连接操作.在此我们考虑两种谓词向量策略:(1)谓词向量与分组属性组合编码策略.图6显示了该策略的原理.我们将custo mer 维表上的选择改写为 SELECT CASE WH EN c _region = AMERICA c _nation ELSE 0FROM customer ,则可以得到以分组列属性值替代过滤结果的value -v ecto r,如图6中间部分所示,然后将value -vector 中的数据编码,根据变元数量分配适当的编码宽度,然后用编码代替value -v ector 中的原始值,形成紧凑的key -vector,如图6中最后一个194110期张延松等:海量数据分析的O ne -size -fits -all O L AP 技术框图中的部分.通过这种编码向量的方式,每个处理节点可以如图5所示的操作步骤同时完成连接过滤和分组聚集操作,本地结果集以编码作为聚集结果的分类值,最终结果在中心节点进行全局归并后再实现将分组编码通过分组编码字典表的还原过程.这种策略增加了维表上的谓词生成代价,增加了谓词向量的宽度和网络传输的数据量,但对处理节点的存储要求最低.缺点是编码谓词向量是查询的私有数据,分组属性在每次查询中都要先过滤再编码,没有重用性.图6 谓词向量与分组属性组合编码(2)维属性列分布式缓存策略.当维表较小时且行数较少时,key -vector (如char -vecto r,可表示28个不同变元)数据量较小,网络传输代价差异不大.而且我们在实验中观测到,按下标地址直接访问bitm ap -v ector 时比直接访问char -v ecto r 需要更多的CPU 周期来解析位操作,因此当维表较小时,分组编码谓词向量(char -vector 或短数据类型v ector )能够获得较为理想的总体性能.当维表数量较大时,bitmap -vector 与char -vector 数量相差8倍以上,基于bitmap 的谓词向量能够更少地消耗处理节点的内存并降低网络传输延迟.在这种策略下,需要将OLAP 查询所需要的维表分组属性和维表间的谓词属性增量地缓存到处理节点的内存中.如图3所示,随着查询的执行,将维表分组属性通过广播方式缓存到各处理节点的内存中形成内存维属性列,支持基于接收的谓词向量执行的DDT A -JOIN 操作.各处理节点的内存相当于分布式缓存,通过中心节点的广播同步更新,缓存的维属性列在缓冲空间不足时可以根据访问频率实行LRU 替换算法,缓存的维属性列也可以物化到磁盘上.在SSB 中,分组属性相对比较集中,在40个维属性中只涉及到7个属性,分组属性一般为低势集数据列,可以应用字典表轻量内存压缩算法[13]大幅度降低存储的空间代价,提高网络传输和分布式缓存的效率.维表列分布式缓存策略将连接操作数据依赖集分为两个部分,一是连接过滤器,二是分组器,连接过滤器的内容随查询内容的变化而各不相同,属于查询的私有数据集,而分组属性具有共享性,即多个查询可能共享一个较小的分组属性集.对于单个查询,在维表谓词操作基础上选择的分组属性子集编码具有最小的网络传输和分布式缓存代价,但在大量并发查询负载下,完整分组属性列的分布式缓存机制能够有效地降低系统整体的传输和缓存代价.在实验中我们具体分析分布式缓存在SSB 中的存储代价.4 并行S PJG A -O LAP 性能分析与实验4.1 网络传输与分布式存储代价分析我们用T PC -H 和SSB 的数据生成器生成1TB 数据集(SF=1000),图7中统计了数据集的数据特征.我们看到在T PC -H 中维表数据量约占5%,而SSB 中维表数据比重为4 ;当采用谓词向量技术TPC -H(1T B)表名大小/KB 行数实际行数SS B(1T B)表名大小/KB 行数实际行数PART24420265SF*200000200000000PART 188523200000*(1+log 2S F)2193157S UPPLIER 1414902SF*1000010000000SU PPLIER 877957SF*20002000000CU STOM ER 24353654SF*150000150000000CUS TOM ER 2995508SF*3000030000000NATION 32525DATE 22825562556REGION 155维表总数据量50188825维表总数据量4062216维表总行数SF*360000360000030维表总行数SF*32000+200000*(1+log 2S F)34193157谓词向量大小43M B谓词向量大小4M B图7 1T B SSB 数据集维表数据特征分析1942计 算 机 学 报2011年。
