一种基于平稳分布的信息搜索方法

在容迟网络(delay tolerant networks,DTNs)中,源节点和目的节点之间一般不存在端到端的路径,因此快速方便地获得信息是容迟网络的一个热点问题。文章将信息搜索过程拆分为查询和反馈2个阶段,并由此提出了一种基于平稳分布的信息搜索算法(information search algorithm based on stationary distribution,ISSD)。用半马尔科夫链模型中的平稳分布来构造函数,分别表示节点的查询和反馈能力;在查询阶段,选择查询概率比较大的节点作为查询节点,当查询节点到达目的社区后即进入反馈阶段,选择自己和邻居中反馈概率最大的节点作为反馈节点。真实跟踪数据上的实验结果表明,与现有算法相比,该文提出的算法能够提高查询率且减少网络资源消耗。     

基于覆盖码预排序的数据立方体部分和top-k查询算法

在决策支持系统中,排序查询是研究的热点问题。提出了一种在OLAP(数据仓库)数据立方体中对部分和查询结果进行排序的高效算法,该算法综合利用覆盖码和预排序,有效地解决了对部分和结果的top-k查询问题。实验结果表明无论数据在随机分布还是存在主导集情况下,该算法都能很好地改进查询的时间代价。     

多序列比对问题的并行近似算法

基于中心方法的思想,采用分治策略,在SIMD-CREW模型上设计了一个使用O(k2m)个处理器(其中k为序列个数,m为最长的序列长度),时间复杂度为O(m logk)的并行近似算法.在实际情况中,由于logk远远小于m,相对于时间复杂度为O(m2k2)的串行中心方法,该算法在理论上达到线性加速.与现有的并行算法相比,它可以适用于任意情况,且易于分析时间复杂度.利用LARPBS模型的特点和并行求前缀和的方法,调用LARPBS模型上求和与最大(小)值的并行算法,首次给出了在LARPBS模型上的多序列比对问题的并行近似算法.该算法使用O(k2m)个处理器,时间复杂度为O(m log log D),其中D为序列两两比对的代价值的最大值.该算法同样适用于任何情况,由于log log D通常远小于m,所以它在理论上也是线性加速的.     

基于深度时空卷积网络的民航需求预测

在线机票预订网站上的用户查询量变化是真实的民航市场需求变化的反映.通过对机票查询数据进行分析,可以准确地预测航班需求,以利于民航业做出快速的市场反应.提出了一种基于深度时空卷积神经网络的民航需求预测模型(DSTCN-FRP),将用户查询量时间序列数据转换成航线网格图,设计多层卷积神经网络来捕捉用户需求与查询数据之间的时间和空间依赖,同时加入节假日等外部因素,最后得到未来一段时间内的民航需求量.在某在线订票网站的真实查询数据集上进行了实验,结果表明:DSTCN-FRP模型优于其他现有的预测方法,其MAE比其他方法降低了15%~50%,RMSE降低了12%~28%.     

高性能网页索引器JU_Indexer的实现

高性能网页索引器JU_Indexer用倒排索引表存储网页索引数据, 以多线程并行的方式对网页建立索引数据, 采用经过优化的检索算法实现用户的查询. 首先给出了JU_Indexer的系统框架, 然后描述了索引数据在JU_Indexer中的存储结构、 建立网页索引的算法、 以及实现用户查询的检索算法. 实验结果表明, JU_Indexer能在毫秒级的时间内完成用户的查询, 它采用的经过优化的词组检索算法缩短了词组的检索时间.     

高阶多元直觉模糊时间序列预测模型

为了突破模糊集理论的限制,更客观地描述不确定性数据,提出一种高阶多元直觉模糊时间序列预测模型.采用模糊聚类算法划分论域,并采用更具客观性的方法建立直觉模糊集的隶属度和非隶属度函数.依据直觉模糊多维取式推理的原理建立基于相似度量的启发式推理规则,作为高阶多元模型的预测规则,并且建立相应的解模糊方法.利用北京市日均气温数据集进行对比实验,结果表明,该模型的预测均方误差(0.86)和平均预测误差(2.57%)较现有方法均明显降低,预测结果优于模糊时间序列预测模型和普通直觉模糊时间序列预测模型.     

基于季节模型及Kalman滤波的道路行程时间

道路行程时间是影响城市交通出行行为的重要因素。当前大多数出行时间研究基于路段进行,假设驾驶人沿着理想最短路径或最快路径行驶,难以对交叉口排队延误等相关时间参数进行精确估计。针对城市任意OD间的出行时间进行分析,采用Kalman滤波方法,利用历史数据对总行程时间进行有效预测。鉴于总行程时间分布存在比较明显的周期性特点,单一Kalman滤波算法难以反映出这种周期性,引入基于季节模型的Kalman滤波算法进行建模和优化。最后,利用深圳浮动车2011年12月连续3d的数据进行实证。研究结果表明:相对于传统的SARIMA模型及普通Kalman滤波算法,优化模型同时考虑总行程时间分布的周期性和时变性,具有较小误差及更好的拟合度;所得预测时间的平均绝对误差(MAE)分别在传统SARIMA模型及普通Kalman滤波算法结果基础上降低了37%和52%,其余误差指标,如均方根误差(RMSE)及最大相对误差(MRE)均有较大下降,从而证明了研究模型的有效性。     

QPE产品的误差评估和订正检验——以伊宁县为例

以新疆伊宁县为研究区,运用2013-2017年定量降水估测(Quantitative Precipitation Estimetion, QPE)小时产品以及区域自动站小时降水数据,通过相关分析法和多元线性回归模型对QPE数据进行误差订正,并从不同降水量级、高程以及空间分布对订正前后的QPE小时产品进行误差评估.经误差分析得出,订正前QPE小时产品大多存在低估现象,随着降水量级的增加,误差依次增大,空间误差分布四周低,且东北方向的误差要大于西南方向;利用海拔、经度、距雷达距离3个对研究区降水影响较大的要素,建立多元线性回归订正模型,订正后的QPE小时产品在不同降水量级、不同高程以及空间分布上的估测能力较订正前均有不同程度的提升.     

用于交通流预测的带距离权重模式识别算法

基于带权重的模式识别算法(WPRA)的交通流短时预测根据历史交通模式所属时段特征区分不同历史状态值权重系数的大小,但权重值的主观设定降低了方法实际应用的可靠性.通过分析基于数据驱动的非参数回归交通流预测算法核心原理,针对WPRA模型权重系数的主观随机性进行预测算法改进,建立了能预测短时交通流的带距离权重的模式识别算法(DWPRA).最后,应用实际交通流数据引入均方根误差进行算法验证,验证结果显示相同近邻K值情况下,DWPRA比WPRA均方根误差降低约4.8%~7.1%,证明了算法的有效性.     

多面体面上任意两点间最短路径算法

提出计算多面体面上任意两点之间最短路径的算法:近似算法、最短路径或近似最短路径算法.近似算法的思想是采用将折线不断嵌入三角形串上的方法,而另2个算法则是通过特定法线寻找三角形串,而且将这些三角形旋转到同一平面上,从而得到最短路径.前者的时间复杂性为O(n),而后者的时间复杂性分别是O(n2)及低于O(2nn2).     

P2P数据交换系统的非一致性数据管理

给出了P2P数据交换系统的形式模型,描述了对等体的本地数据一致性约束、对等体间的信任关系以及对等体间的数据交换约束。并在此基础上提出了基于"查询候选数据集"的全局一致性查询处理策略。一个对等体的"查询候选数据集"是满足其本地数据一致性约束和对等体间所有数据交换约束的全局数据库虚拟子视图。提交到一个对等体的查询操作通过在其查询候选集上进行便可以得到全局一致的查询结果。给出了"查询候选数据集"的构造算法。     

传感器网络分布式多维概率Top-k查询处理算法

针对分布式传感器网络提出多维概率Top-k查询处理算法DMPT.利用Skyline操作返回Top-k元组,通过反馈机制和过滤机制减少数据传输量及查询处理时间.DMPT考虑了数据的不确定性、多维属性以及网络的分布式和能源受限特征,根据Skylayer计算得到Top-k结果.通过真实数据和模拟数据实验验证得到:DMPT算法比传统算法具有更高的节能效率和更快的响应速度.     

基于启发函数的网格数据库查询算法

查询处理技术是网格数据库研究的核心,但是传统的查询处理技术无法适应动态变化的网格环境,导致网格资源利用率低、查询效率不高。给出了基于副本的网格数据库查询处理代价模型和两种查询处理算法,利用不同的数据集和网格环境参数进行实验验证。实验结果表明,基于启发函数的网格数据库查询算法在一定程度上提高了查询处理效率,生成子查询时间代价为O(n),消耗时间比采用穷举策略下降10%左右。     

GPU加速的高超声速目标双通道IMM跟踪算法

提出一种改进的双通道交互多模型(IMM)算法,使用x和y维残差的边缘分布独立表征预测误差的似然函数,使滤波模型在不同维度与目标运动中分别匹配.首先分析了残差-似然函数-模型概率更新之间的映射关系,证明算法的可行性和有效性,然后引入图形处理器(GPU)并行运算平台,设计了通道级-模型级嵌入式并行方案,提高算法的实时性.仿真表明:相比于传统基于CPU平台下的IMM算法,该算法预测误差与真实噪声似然分布契合度更高、实时性更强、跟踪误差更小.     

一种高效的不确定数据流Top-K 查询算法

在传感器网络、RFID等各种应用中会产生大量不确定性数据,有效的Top-K查询处理是不确定性数据管理中一项重要技术。针对已有的Top-K查询没有很好地结合元组的分值和不确定性,在分析不确定性数据模型和可能世界模型的基础上,定义了不确定数据流元组的查询语义。设计并实现了一种有效的Top-K查询算法。该算法按照元组的得分值进行降序排列,概率值最高的前K个元组集合就是Top-K的查询结果,实验结果表明,与CSQ和SCSQ算法相比,更具高效性和实用性。     

一种社交网络环境下并行短文本查询算法

随着移动社交网络的迅速发展,如何从海量带有时间属性和地理位置属性的短文本信息中快速查询到有效信息具有重要意义.社交网络环境下传统短文本查询算法忽略时间维度,并且在海量数据下无法满足用户快速响应的需求.针对以上问题,提出一种社交网络环境下并行短文本查询算法.提出的算法设计了基于MapReduce模型下的查询框架,该框架使用了基于滑动窗口下的多版本时空索引(MVSTR-tree),保证了查询过程中融合了时间和空间属性,实现了对海量数据高效查询的目标.最后,通过真实数据集的实验证明该算法能有效缩短查询时间.     

基于摘要图的不确定社会网络Top-k子图查询算法

针对不确定W eb社会网络的Top-k子图查询问题,以无向、顶点带标签及边赋权重的简单图为基本模型,设计了用来简洁描述社会网络并编码原始图信息的摘要图,提出了Top-k子图同构查询算法。针对真实和虚拟网络数据进行了大量实验,结果表明:基于摘要图的Top-k子图查询算法较VF2算法运算时间缩短;由于构建摘要图时的主要依据是顶点的标号,因此查询图的标号分布对查询性能有较大影响;顶点标号数目增加时该算法的查询性能呈类似指数形式提高,而VF2算法的查询性能没有受到较大影响;当数据图的顶点数量增大时,该算法与VF2算法相比,消耗时间的增长更缓慢;该算法在处理Top-k查询时体现出了稳定高效的性能。     

对称矩阵行压缩的下标变换定理及在测绘中的应用

证明了整数环误差引理,进一步证明了对称阵行压缩的下标逆变换公式,这将其解压缩算法的时间复杂度从O(n2)降低到O(1).分析了对称阵的行压缩方式下的2种解压缩算法的相对运行效率,分析表明,当采用下标逆变换算法从压缩的对称矩阵中查询元素时,其查询效率比二重循环算法高得多.将这些公式和算法用来管理测绘工作中的大规模对称矩阵,如ITRF2000-ALASKA站群的协方差矩阵,既可进一步节约计算机存储空间和网络资源,还可提高其数据查询效率.     

用模拟退火算法求解无向排列的反转排序问题

分子生物学中基因无方向的反转基因组重排问题在数学上已被证明是一个NP-难问题.目前,较好的算法是Christie(2001)的3/2-近似算法.本文给出一种适合于计算基因无方向的反转基因组重排问题的模拟退火算法,定义了解的邻域结构.数据实验的结果表明该算法性能优于3/2-近似算法.