随着全球定位系统的发展和应用,巨量的轨迹数据被实时收集,给数据的传输、存储和分析带来挑战.基于分段线性近似(piecewise linear approximation,PLA)的数据压缩技术因具有简单直观、压缩存储低和传输快的特点被广泛应用和研究.针对现...随着全球定位系统的发展和应用,巨量的轨迹数据被实时收集,给数据的传输、存储和分析带来挑战.基于分段线性近似(piecewise linear approximation,PLA)的数据压缩技术因具有简单直观、压缩存储低和传输快的特点被广泛应用和研究.针对现有轨迹PLA压缩方法不能最优化地在线压缩多维数据的现状,在最大误差限定(maximum error bound,记为L_(∞))下提出多维轨迹数据的最优化PLA压缩问题(记为m DisPLA_(∞)),并给出一种在线MDisPLA算法予以解决.该算法利用“分治-融合”的策略扩展一维最优化PLA算法,以最优化地压缩多维轨迹数据.MDisPLA算法具有线性时间复杂性,可以生成最少的不连续分割,且可以保证生成直线表示的质量,即原始数据点和对应解压缩点之间的同步误差具有上界.通过与基于同步距离锥交(cone intersection using the synchronous Euclidean distance,CISED)的轨迹压缩算法进行理论和实验比较,验证了MDisPLA算法是稳健的,可生成具有保质性的直线表示.MDisPLA算法以更低的内存消耗,较CISED算法提高了14倍左右的处理速度,降低了约48%的分割个数和10.5%的存储个数.MDisPLA算法在保证压缩质量的同时,显著提高了处理速度和降低了存储空间,整体上优于CISED算法.展开更多
Graph pattern matching(GPM)can be used to mine the key information in graphs.Exact GPM is one of the most commonly used methods among all the GPM-related methods,which aims to exactly find all subgraphs for a given qu...Graph pattern matching(GPM)can be used to mine the key information in graphs.Exact GPM is one of the most commonly used methods among all the GPM-related methods,which aims to exactly find all subgraphs for a given query graph in a data graph.The exact GPM has been widely used in biological data analyses,social network analyses and other fields.In this paper,the applications of the exact GPM were first introduced,and the research progress of the exact GPM was summarized.Then,the related algorithms were introduced in detail,and the experiments on the state-of-the-art exact GPM algorithms were conducted to compare their performance.Based on the experimental results,the applicable scenarios of the algorithms were pointed out.New research opportunities in this area were proposed.展开更多
文摘随着全球定位系统的发展和应用,巨量的轨迹数据被实时收集,给数据的传输、存储和分析带来挑战.基于分段线性近似(piecewise linear approximation,PLA)的数据压缩技术因具有简单直观、压缩存储低和传输快的特点被广泛应用和研究.针对现有轨迹PLA压缩方法不能最优化地在线压缩多维数据的现状,在最大误差限定(maximum error bound,记为L_(∞))下提出多维轨迹数据的最优化PLA压缩问题(记为m DisPLA_(∞)),并给出一种在线MDisPLA算法予以解决.该算法利用“分治-融合”的策略扩展一维最优化PLA算法,以最优化地压缩多维轨迹数据.MDisPLA算法具有线性时间复杂性,可以生成最少的不连续分割,且可以保证生成直线表示的质量,即原始数据点和对应解压缩点之间的同步误差具有上界.通过与基于同步距离锥交(cone intersection using the synchronous Euclidean distance,CISED)的轨迹压缩算法进行理论和实验比较,验证了MDisPLA算法是稳健的,可生成具有保质性的直线表示.MDisPLA算法以更低的内存消耗,较CISED算法提高了14倍左右的处理速度,降低了约48%的分割个数和10.5%的存储个数.MDisPLA算法在保证压缩质量的同时,显著提高了处理速度和降低了存储空间,整体上优于CISED算法.
文摘Graph pattern matching(GPM)can be used to mine the key information in graphs.Exact GPM is one of the most commonly used methods among all the GPM-related methods,which aims to exactly find all subgraphs for a given query graph in a data graph.The exact GPM has been widely used in biological data analyses,social network analyses and other fields.In this paper,the applications of the exact GPM were first introduced,and the research progress of the exact GPM was summarized.Then,the related algorithms were introduced in detail,and the experiments on the state-of-the-art exact GPM algorithms were conducted to compare their performance.Based on the experimental results,the applicable scenarios of the algorithms were pointed out.New research opportunities in this area were proposed.
