Opening Window Time Ratio (OPW-TR) 的多线程实现 C/C++

2024-03-13 09:59

本文主要是介绍Opening Window Time Ratio (OPW-TR) 的多线程实现 C/C++,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

1.题目要求

Opening Window Time Ratio (OPW-TR) 的多线程实现C/C++

2.需求分析

近年来,GPS设备被广泛应用。根据Canalys(一个信息公司)报告, 在2006到2007一年间,GPS设备销售增加了116%。 2009年,据估计有2700万安装了GPS设备的手机被销售。截止2009年,有6.8亿的GPS用户。这是设备都能够产生、存储和传输轨迹数据。

随着基于位置的服务应用(Location basedservice, LBS)广泛使用轨迹数据,有如下3个主要问题:

(1)存储开销问题:假设轨迹数据在没有压缩的情况下,以每10s采集一次,一天仅仅4000个移动对象就会产生1Gb的数据。这样,对海量轨迹数据的存储和查询将是一个巨大的问题;

 (2)传输开销问题:移动手机或是传输网络传送轨迹数据的代价是昂贵的,一般 5-7美元/M。假设跟踪4000车辆,一天的费用就是5000-7000美元,一年就是1,800,000 – 2,500,000美元。

 (3)计算开销问题:随着轨迹数据规模的增加,很难快速地从轨迹数据中发现有用的模式。而减少轨迹数据的规模可以加速轨迹数据模式挖掘的速度。

   这三个问题的出现使得数据压缩算法快速的发展,这里我们采用常规开放窗口算法对数据进行在线压缩

3.问题分析

l  采用开放式窗口算法标识一个潜在压缩数据段的开始点。

l  如果压缩效果好,然后尝试去压缩更长的数据段。

l  在线压缩过程从定义一段数据开始:起始点(第一个数据)到浮动点(第三个数据)。

l  如果这段数据中的每个点的误差都低于一个距离阈值,尝试移动浮动点一个点。

(1)当即将超出阈值时,两个策略中的一个被实施:

a.常规开放窗口(NormalOpening Window, NOPW): 导致阈值变化的数据点成为当前段的尾端点,成为下一个段的标签点。

b.前置开放窗口(BeforeOpening Window, BOPW):导致阈值变化的数据点的前一数据点当前段的尾端点,成为下一个段的标签点。

如果没有超越阈值,浮动一位(即窗口近一步开放),整个过程如此循环,只到所有数据被转换。

(2)常规开放窗口(NOPW)策略:阈值超过数据点是断开点,如图1所示, 在这条移动数据轨迹中总共有16个移动数据轨迹点,而我们通过NOPW算法对移动数据轨迹点进行压缩,存取其中的五个点(0,4,8,12,16)来近似的模拟出移动数据轨迹。如果压缩效果好,然后尝试去压缩更长的数据段。在线压缩过程从定义一段数据开始:起始点(第一个数据)到浮动点(第三个数据)。导致阈值变化的数据点成为当前段的尾端点,成为下一个段的标签点。如果没有超越阈值,浮动一位(即窗口近一步开放),整个过程如此循环,直到所有数据被转换。

 

图1

(3)前置开放窗口(BOPW)策略:在阈值超过数据点前一个数据点是断开点。OPW算法能够在有噪音的较短数据序列中进行压缩,其时间复杂度为O(n2),如图2所示。

图2

Opening Window Time Ratio (OPW-TR) 是一个对OPW的扩展。OPW-TR利用SED(synchronized euclidean distance) 代替spatial error。相对OPW, OPW-TR把时间维度考虑进去。类似OPW, OPW-TR的时间复杂度也是O(n2)

(4)集中压缩方法比较如下表所示:

4.模块设计

首先定义移动数据轨迹点的结构体

struct point

{

    float x;        //轨迹点的横坐标

    float y;        //轨迹点的纵坐标

    int t;        //轨迹点所处的时刻t

};

 

然后分为两个模块(输入模块和压缩模块)来实现移动数据轨迹压缩

 

(1) 输入模块

通过设置一个循来依次输入压缩轨迹经过的轨迹点

point p[16];

    printf("请输入压缩轨迹经过几个点\n");

    int n;                //压缩轨迹经过的点

    scanf_s("%d",&n);

    for(i=0;i<n;i++)

    {

       printf("请输入第%d个轨迹点横坐标\n",i);

       scanf_s("%f",&p[i].x);

       printf("请输入第%d个轨迹点纵坐标\n",i);

       scanf_s("%f",&p[i].y);

       printf("请输入第%d个轨迹点时刻\n",i);

       scanf_s("%d",&p[i].t);

    }

 

(2) 压缩模块

分为两层循环,大循环保证这条数据轨迹上的压缩数据轨迹段的移动,判断压缩的数据轨迹段是否压缩完成,是否要开始压缩新的数据轨迹段。小循环保证其中的一段数据轨迹上数据轨迹点的移动,当数据轨迹段上所有的点都不超过阈值,则移动尾端点到下一个点,重新开始压缩新的数据轨迹段,当其中有点超过阈值,则将它压缩存储进来并作为下个数据压缩轨迹段的起始点,当所有的数据轨迹点经过这两层循环后,就能把压缩的数据点存储起来。如图3所示。


图3

 

                                                                

   for(;qishi<=13;)                               //大循环直到检测到最后一个数据段终止

    {

       if((p[zhongzhi+1].x)-p[qishi].x!=0)

       {

           k=(p[zhongzhi+1].y-p[qishi].y)/(p[zhongzhi+1].x-p[qishi].x);

       }

       else

       {

        k=10000; //起始点和终止点横坐标相同,设斜率为无穷大

        }

       b=p[qishi].y-k*p[qishi].x;

       float d;             //d为点到直线的距离

       for(;qishi<=zhongzhi;qishi++)                                    //循环检测起始点到终止点这段数据中每个点和阈值的关系

       {     

           int t=qishi;    //保留一个原始的起始值

           d=(k*p[qishi].x-p[qishi].y+b)/(sqrt(k*k+1));     //点到直线距离公式

              if(d>m)      //如果点到直线的距离超过阈值,则将它设为断开点,并存储在q数组里

              {

                  q[count].x=p[qishi].x;

                  q[count].y=p[qishi].y;

                  q[count].t=p[qishi].t;                

                  count++;

                  zhongzhi=qishi+2;   //新的数据段

                  break;              //跳出循环,开始检测下一个数据段

              }

              else if(qishi==zhongzhi)    //检测到整个数据段的点到直线距离都小于阈值

                  {

                     zhongzhi=zhongzhi+1;   //将终止点往后移动一位

                     qishi=t;      //将起始点回复成原来位置

                 }

       }

    }

5.运行结果

压缩轨迹数据点

(0,0,0)

(1,1,1)

(2,1,2)

(3,2,3)

(4,1,4)

(5,6,5)

(6,7,6)

(7,8,7)

(8 ,6, 8)

(9,1,9)

(10,2,10)

(11,6,11)

(12,10,12)

(13,7,13)

(14,6,14)

(15,1,15)

源代码及测试数据下载网址:http://download.csdn.net/detail/bryank/9532411

这篇关于Opening Window Time Ratio (OPW-TR) 的多线程实现 C/C++的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/804473

相关文章

C++中RAII资源获取即初始化

《C++中RAII资源获取即初始化》RAII通过构造/析构自动管理资源生命周期,确保安全释放,本文就来介绍一下C++中的RAII技术及其应用,具有一定的参考价值,感兴趣的可以了解一下... 目录一、核心原理与机制二、标准库中的RAII实现三、自定义RAII类设计原则四、常见应用场景1. 内存管理2. 文件操

C++中零拷贝的多种实现方式

《C++中零拷贝的多种实现方式》本文主要介绍了C++中零拷贝的实现示例,旨在在减少数据在内存中的不必要复制,从而提高程序性能、降低内存使用并减少CPU消耗,零拷贝技术通过多种方式实现,下面就来了解一下... 目录一、C++中零拷贝技术的核心概念二、std::string_view 简介三、std::stri

C++高效内存池实现减少动态分配开销的解决方案

《C++高效内存池实现减少动态分配开销的解决方案》C++动态内存分配存在系统调用开销、碎片化和锁竞争等性能问题,内存池通过预分配、分块管理和缓存复用解决这些问题,下面就来了解一下... 目录一、C++内存分配的性能挑战二、内存池技术的核心原理三、主流内存池实现:TCMalloc与Jemalloc1. TCM

OpenCV实现实时颜色检测的示例

《OpenCV实现实时颜色检测的示例》本文主要介绍了OpenCV实现实时颜色检测的示例,通过HSV色彩空间转换和色调范围判断实现红黄绿蓝颜色检测,包含视频捕捉、区域标记、颜色分析等功能,具有一定的参考... 目录一、引言二、系统概述三、代码解析1. 导入库2. 颜色识别函数3. 主程序循环四、HSV色彩空间

Python实现精准提取 PDF中的文本,表格与图片

《Python实现精准提取PDF中的文本,表格与图片》在实际的系统开发中,处理PDF文件不仅限于读取整页文本,还有提取文档中的表格数据,图片或特定区域的内容,下面我们来看看如何使用Python实... 目录安装 python 库提取 PDF 文本内容:获取整页文本与指定区域内容获取页面上的所有文本内容获取

基于Python实现一个Windows Tree命令工具

《基于Python实现一个WindowsTree命令工具》今天想要在Windows平台的CMD命令终端窗口中使用像Linux下的tree命令,打印一下目录结构层级树,然而还真有tree命令,但是发现... 目录引言实现代码使用说明可用选项示例用法功能特点添加到环境变量方法一:创建批处理文件并添加到PATH1

Java使用HttpClient实现图片下载与本地保存功能

《Java使用HttpClient实现图片下载与本地保存功能》在当今数字化时代,网络资源的获取与处理已成为软件开发中的常见需求,其中,图片作为网络上最常见的资源之一,其下载与保存功能在许多应用场景中都... 目录引言一、Apache HttpClient简介二、技术栈与环境准备三、实现图片下载与保存功能1.

C++ 函数 strftime 和时间格式示例详解

《C++函数strftime和时间格式示例详解》strftime是C/C++标准库中用于格式化日期和时间的函数,定义在ctime头文件中,它将tm结构体中的时间信息转换为指定格式的字符串,是处理... 目录C++ 函数 strftipythonme 详解一、函数原型二、功能描述三、格式字符串说明四、返回值五

canal实现mysql数据同步的详细过程

《canal实现mysql数据同步的详细过程》:本文主要介绍canal实现mysql数据同步的详细过程,本文通过实例图文相结合给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的... 目录1、canal下载2、mysql同步用户创建和授权3、canal admin安装和启动4、canal

Nexus安装和启动的实现教程

《Nexus安装和启动的实现教程》:本文主要介绍Nexus安装和启动的实现教程,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、Nexus下载二、Nexus安装和启动三、关闭Nexus总结一、Nexus下载官方下载链接:DownloadWindows系统根