Density-based clustering method in the moving object database

With the rapid advance of wireless communication, tracking the positions of the moving objects is becoming increasingly feasible and necessary. Because a large number of people use mobile phones, we must handle a large moving object database as well as the following problems. How can we provide the customers with high quality service, that means, how can we deal with so many enquiries within as less time as possible? Because of the large number of data, the gap between CPU speed and the size of main memory has increasing considerably. One way to reduce the time to handle enquiries is to reduce the I/O number between the buffer and the secondary storage. An effective clustering of the objects can minimize the I/O cost between them. In this paper, according to the characteristic of the moving object database, we analyze the objects in buffer, according to their mappiigs in the two-dimension coordiiate, and then develop a density-based clustering method to effectively reorganize the clusters. This new mechanism leads to the less cost of the I/O operation and the more efficient response to enquiries.     

Density-based clustering method in the moving object database

With the rapid advance of wireless communication, tracking the positions of the moving objects is becoming increasingly feasible and necessary. Because a large number of people use mobile phones, we must handle a large moving object database as well as the following problems. How can we provide the customers with high quality service, that means, how can we deal with so many enquiries within as less time as possible? Because of the large number of data, the gap between CPU speed and the size of main memory has increasing considerably. One way to reduce the time to handle enquiries is to reduce the I/O number between the buffer and the secondary storage. An effective clustering of the objects can minimize the I/O-cost between them. In this paper, according to the characteristic of the moving object database, we analyze the objects in buffer, according to their mappings in the two-dimension coordinate, and then develop a density-based clustering method to effectively reorganize the clusters. This new mechanism leads to the less cost of the I/O operation and the more efficient response to enquiries.     

运动目标的快速检测、跟踪和判别

为完成自然环境中大范围的环境监控 ,实现了一个运动目标检测、跟踪和判别系统。该系统利用一个固定平台上的、有 3 60°旋转和一定俯仰的两自由度摄像机监视自然环境 ,利用 2 -D仿射模型和鲁棒参数估计的主运动分析得到背景运动参数 ,能够在短时间内完成 3 60°全景图的拼接 ,并能利用出格点检测和聚类自动检测、通过限制搜索范围的检测和维护运动目标缓冲池主动跟踪运动目标 ,还能按目标区域的周期性变化判别目标种类 (人或车辆 )。实验表明 ,系统能够实时可靠地检测、跟踪运动目标并完成判别 ,满足特定的监控要求。另外 ,该运动目标判别方法简单可靠 ,其结果可作为视频序列识别和检索的一项重要特征     

Indexing large moving objects from past to future with PCFI

In moving object database, the moving objects' current position must be kept in memory, also to the trajectory, in some case, as same as the future. But the current existing indexes such as SEB tree, SETI tree, 2+3R tree, 2 3RT tree and etc. can only provide the capability for past and current query, and the TPR Tree, TPR * Tree and etc. can only provide the capability for current and future query. None of them can provide a strategy for indexing the past, current and also the future information of moving objects. In this paper, we propose the past current future Index (PCFI Index) to index the past, current & future information of the moving objects. It is the combination of SETI tree and TPR * tree, the SETI liking index is used for indexing the historical trajectory segments except the front line structure, and the moving objects' current positions, velocities are indexed via the in memory frontline structure which mainly implemented with TPR * tree. Considering the large update operations on TPR tree of large population, a hash table considering cache sensitivity is also introduced. It works with the frontline part, leading a bottom up update of the tree. The performance analysis proves that the PCFI index can handle most of the query efficiently and provides a uniform solution for the trajectory query, time slice query, internal query and moving query.     

一种实时有效的蜂群模式挖掘算法

针对实时相关运动模式挖掘应用的需求,提出了一种实时地发现关闭蜂群模式的簇重组算法(CLUR).该算法维护一个候选蜂群模式列表,在每个时间戳采用基于密度的聚类算法对移动目标进行聚类,根据聚类结果组合所有的最大移动目标集,记录相应的时间集,然后构建候选蜂群模式,并更新到候选列表.算法给出了三种更新规则和一种插入规则,用于实现候选蜂群模式列表的更新,同时降低了候选列表的冗余度,提高了算法的效率.在每个时间戳结束时可通过关闭检测规则实时地发现当前时刻的关闭蜂群模式.在合成数据上的综合实验验证了CLUR算法的正确性、实时性和高效性,CLUR算法适用于实时相关运动模式挖掘系统.     

路径表达式的并行正向指针跟踪算法:设计与性能分析

在对象数据库系统中,路径表达式是用于定位复杂对象的不可缺少的工具·由于路径表达式的计算非常耗时,因此若要提高数据库性能,优化和并行计算路径表达式的执行是关键环节·并行正向指针跟踪算法(PFPC)充分利用了管道并行性和I/O并行性·在基于分布式共享虚拟存储器(DSVM)的分布式对象数据库FISH系统上完成了实现和测试·对算法的设计进行了详细描述并分析其性能·     

Indexing large moving objects from past to future with PCFI

In moving object database, the moving objects' current position must be kept in memory, also to the trajectory, in some case, as same as the future. But the current existing indexes such as SEB-tree, SETI-tree, 2+3R-tree, 2-3RT-tree and etc. can only provide the capability for past and current query, and the TPR-Tree, TPR*-Tree and etc.can only provide the capability for current and future query. None of them can provide a strategy for indexing the past, current and also the future information of moving objects.In this paper, we propose the past-current-future Index (PCFI-Index) to index the past,current & future information of the moving objects. It is the combination of SETI-tree and TPR*-tree, the SETI liking index is used for indexing the historical trajectory segments except the front line structure, and the moving objects' current positions, velocities are indexed via the in-memory frontline structure which mainly implemented with TPR*-tree.Considering the large update operations on TPR-tree of large population, a hash table considering cache sensitivity is also introduced. It works with the frontline part, leading a bottom-up update of the tree. The performance analysis proves that the PCFI-index can handle most of the query efficiently and provides a uniform solution for the trajectory query, time-slice query, internal query and moving query.     

一种基于空间邻接关系的聚类算法及实现

空间聚类分析是空间数据挖掘的一种方法,空间聚类分析能从空间数据库中直接发现一些有用的聚类结构。在此引入了一种基于邻接关系的空间聚类算法,该算法可以实现对空间复杂地理对象的聚类分析。在具体的模拟试验中,利用该算法可以将相邻的并且符合选取条件的空间目标聚类成一类。     

公路网上移动对象连续k近邻查询的一种方法

公路网上移动对象连续k近邻查询是最近时空数据库查询中的一个研究热点,它是在一个时间段内找到离查询点最近的K个移动对象.我们分析了现有查询方法,存在的问题主要是运动对象位置随时间而频繁变化以至于不能及时更新运动对象的信息而导致返回KNN结果不正确.为了解决这些问题,采用一种距离预计算方法,使计算量减少,从而为更新通讯获得更多时间.通过实验证明,我们提出的方法是有效的.     

面向对象数据库中对象的存储策略和聚簇

面向对象数据库系统(OODBS)的核心是把现实世界的事物描述为对象,数据存储、操作和管理都以对象为依据.对象可以是简单的,也可以是复杂的或复杂对象中引用了其它的对象.首先对OODBS实现过程中复杂对象存储的若干问题进行讨论.具体介绍对象的存储策略、类层次的存储策略和对象的缓冲区管理实现方案.最后就系统的聚簇技术进行详细阐述.     

一种基于K近邻团的聚类算法

在K近邻和逆K近邻理论基础上提出了K近邻团的概念。通过度量对象间的相似度,任意两个元素都互为K近邻和逆K近邻的对象集合构成一个K近邻团。利用同一个K近邻团中的对象彼此都具有较高相似性的特点,选取不同的K值对目标集合进行聚类。通过实验证明了该方法的有效性。     

组移动模式挖掘中轨迹聚类的置信区间法

在借鉴空间数据挖掘技术的基础上,定义了移动对象轨迹之间的时态距离和平均距离,提出了标准差法和置信区间法两种轨迹聚类算法。两种方法能够找出所有具有相似轨迹的对象对,在不同距离采样点数的基础上配合使用两种方法能够明显降低轨迹聚类算法的时间复杂度。基于标准差法和置信区间法的轨迹聚类算法在仿真数据集和真实数据集进行了验证。表明两种方法能够为其他轨迹聚类算法进行数据筛选,筛选后的数据量将大大减少,从而可提高算法效率。     

一种基于密度的聚类算法实现

基于密度的聚类算法OPTICS是一种大规模数据库的聚类算法,它是基于核心对象和可达距离来实现的.对于每一个核心对象将其邻域内的所有对象按到该核心对象的可达距离进行排序,每次都选择1个到该核心对象具有最小的可达距离的对象进行信息更新.算法实现采用优先队列保存候选对象以加快处理速度,最后用UCI数据集对算法进行聚类效果测试,结果表明OPTICS算法对数据集产生一个基于密度的簇排序结构.     

工程数据库的双缓冲区管理机制

提出了一面向对象数据库系统Ｏ２Ｓ的双缓冲区机制，阐述了页面缓冲区和对象缓冲区的管理数据结构及其缓冲区内的废品回收等，双缓冲机制能有效地提高应用对象的访问效率。     

基于Kalman的运动物体跟踪和预测方法研究

目前,很多应用需要跟踪图像序列中的运动物体。但是,有时不知道运动物体的特性,因此,提出一个完整的跟踪预测模型;使用无需先验知识的Kalman滤波器跟踪和预测运动物体。利用提取的Harris角点,通过L-K金字塔方法得到前后两帧光流;通过光流聚类得到当前帧中运动物体的凸包,使运动物体从背景中分离出来。由Kalman滤波器跟踪和预测各运动物体凸包的重心,并划出运动轨迹。计算机仿真及现场测试结果表明所提出的方法具有较高的跟踪精度,且计算量小。     

Distributed location-based query processing on large volumes of moving items

Recently, new techniques to efficiently manage current and past location information of moving objects have received significant interests in the area of moving object databases and location-based service systems. In this paper, we exploit query processing schemes for location management systems, which consist of multiple data processing nodes to handle massive volume of moving objects such as cellular phone users.To show the usefulness of the proposed schemes, some experimental results showing performance factors regarding distributed query processing are explained. In our experiments, we use two kinds of data set: one is generated by the extended GSTD simulator and another is generated by the real-time data generator which generates location sensing reports of various types of users having different movement patterns.     

Distributed location-based query processing on large volumes of moving items

Recently, new techniques to efficiently manage current and past location information of moving objects have received significant interests in the area of moving object databases and location-based service systems. In this paper, we exploit query processing schemes for location management systems, which consist of multiple data processing nodes to handle massive volume of moving objects such as cellular phone users. To show the usefulness of the proposed schemes, some experimental results showing performance factors regarding distributed query processing are explained. In our experiments, we use two kinds of data set: one is generated by the extended GSTD simulator and another is generated by the real-time data generator which generates location sensing reports of various types of users having different movement patterns.     

WIDE:海量数据的聚类算法

给出了一种新的处理海量数据的聚类算法WIDE（window-density clustering algorithm）．它通过网格方法将数据之间的相互关联局部化，通过窗口技术来提高算法的效率，通过密度方法提高聚类的精度．以窗口为中介将网格方法和密度方法融合在一起是算法的主要思想．在此基础上对算法进行了扩展，在功能方面实现了混合型数据聚类、含障碍物数据聚类和增量数据聚类；在速度方面实现了分布式并行聚类．WIDE算法能够在局域网中的多台计算机上并行工作，效率高，计算复杂度为O（N），且能够发现任意形状的聚类，对噪声不敏感．     

基于动态时间间隔的超声波定位系统设计

针对传统的被动式超声波定位方法,无法对快速移动物体进行精确定位的问题,提出一种改进被动式定位方法。通过射频信号实现发送端与接收端的时间同步,根据移动目标的上一次位置信息,动态调整超声波发射端的发射间隔,使其既能保持多个物体同时定位的优点,又能保证系统的实时性。基于STC 12LE5612AD单片机搭建了自动导引运输车(automated guided vehicle,AGV)室内定位系统,对改进前后的超声波定位方法进行验证对比,结果表明,改进后的方法弥补了传统定位方法的不足,可以显著提高快速移动物体的定位精度。     

时空网格(ST-GRID)移动对象数据库模型

有效的存储和查询数据库管理系统中的移动对象受到了大量的关注，有一些是针对管理移动对象动态改变信息的应用。在本文中，把时间和空间变换成时空网格模型(ST-GRID)，把移动对象的运动轨迹转换成时空网格上的折线，用这种存储结构来管理移动对象，并给出产生折线轨迹的RippleInsert算法及移动对象突然改变目的地的解决方案。