共查询到19条相似文献,搜索用时 187 毫秒
1.
基于空间填充曲线网格划分的最近邻查询算法 总被引:1,自引:0,他引:1
在建树过程中,R树存在最小边界矩形之间重叠的现象。当数据量较大时,重叠现象尤为严重,基于R树最近邻查询算法的性能急剧恶化。针对该问题,利用空间填充曲线的降低维度特性和数据聚类特性,提出一种基于网格划分最近邻查询算法。该算法将整个数据空间划分成大小相等、互不重叠的网格,对网格中的点进行线性排序之后,只需要访问查询点所在网格中的点及其周边邻近网格中的点,就能够获得最近邻。在Hilbert曲线、Z曲线和Gray曲线上实现3种最近邻查询算法,在映射算法和数据聚类特性上实验比较3种曲线之间的性能差异。实验结果表明,算法的查询性能明显优于顺序扫描算法和基于R树的最近邻查询算法。 相似文献
2.
3.
k-最近对查询是空间数据库中重要操作之一.在低维空间中基于R*树分枝限界最近对查询算法(k-self-CPQ)和Brute-Force算法的查询效率较高,而在高维空间中其性能急剧恶化,降低空间维度成为解决问题的关键.依据Z曲线构造过程,将高维空间分割成大小相等的网格,以此将网格中的点映射到线性空间中.提出了基于网格划分的降维方法及最小网格概念,给出了基于Z曲线近似 k-最近对查询算法.利用最小网格的边长,算法优化线性扫描过程.实验结果表明在高维空间中算法性能优于Brute-Fore和 k-self-CPQ,且近似 k-最近对质量较好. 相似文献
4.
CPM(conceptual partitioning monitoring)是一种较为高效的概念划分网格的思想,用以解决二维空间下的连续最近邻查询问题.在此思想的基础上提出一种采用树形结构来索引概念划分网格的连续最近邻查询算法T-CPM,通过一系列改进步骤,提升了这一算法的查询效率.实验证明,相比经典的算法,T-CPM优化了网格的检索顺序并节省了计算代价.此外,验证了将这一新的方法延伸到基于不确定空间对象的连续最近邻查询问题中,以此给出了一种针对动态不确定空间数据最近邻查询问题的思路和方法. 相似文献
5.
局部范围受限的多类型最近邻查询 总被引:4,自引:0,他引:4
多类型最近邻查询在现实中的应用范围比传统的最近邻查询广泛.基于多类型最近邻查询,提出局部范围受限的多类型最近邻查询(PCMTNN)概念,针对范围约束是任意简单多边形区域的数据集给出PCMTNN算法,利用椭圆最小外切矩形的易求性和与椭圆本身覆盖区域的最近似性特点缩小了搜索范围,并用一个链表结构实现了在一次R树的遍历过程中找到包含在所有搜索区域内的数据集中点的过程,从而大幅度减少了无用点的访问数量.实验结果分析表明算法具有较好的性能. 相似文献
6.
一种采用Z曲线高维空间范围查询算法 总被引:2,自引:1,他引:1
低维空间中线性扫描算法及基于R树、VA文件和NB树的空间范围查询算法的效率较高,高维空间中它们的效率出现恶化现象.Z曲线将空间分割成大小相等网格并依次穿过它们,将网格中的点映射到线性空间中,从而能够使用B+树作为点集的索引结构.利用Z曲线聚类和降维特性,本文给出网格划分方法、搜索区域分解过程,提出一种高维空间范围查询算法.实验结果表明在高维空间中算法的效率优于上述算法. 相似文献
7.
连续可见最近邻查询是查询连续空间的最近邻问题,目前的研究基本以二维空间为背景并提出了一些查询算法,但可见性判断方法不能适用于三维或高维空间.以陆地表面的三维数据为研究背景,提出了一种查询地表任意路径的连续可见最近邻方法.该方法以计算步长的方式把整个查询路径分割成若干个连续的查询子路径,循环计算每个子路径的连续可见最近邻直至得到整个路径的查询结果.该方法可以扩展应用于高维空间中的连续最近邻查询. 相似文献
8.
最近邻查询是空间数据查询领域中最重要的查询技术之一.最近邻查询根据所查询的目标对象的运动特性分为静态最近邻查询和动态最近邻查询.静态最近邻查询的关键在于运用最小距离和最小最大距离作为查询条件,对索引树的节点进行排序和剪枝进而查找目标对象 通过对现有最近邻查询算法的分析研究,比较这些现有算法的优缺点 相似文献
9.
10.
11.
12.
A Fast Simulation Method Using Overlapping Grids for Interactions between Smoke and Rigid Objects 总被引:1,自引:0,他引:1
Yoshinori Dobashi Yasuhiro Matsuda Tsuyoshi Yamamoto Tomoyuki Nishita 《Computer Graphics Forum》2008,27(2):477-486
Recently, many techniques using computational fluid dynamics have been proposed for the simulation of natural phenomena such as smoke and fire. Traditionally, a single grid is used for computing the motion of fluids. When an object interacts with a fluid, the resolution of the grid must be sufficiently high because the shape of the object is represented by a shape sampled at the grid points. This increases the number of grid points that are required, and hence the computational cost is increased. To address this problem, we propose a method using multiple grids that overlap with each other. In addition to a large single grid (a global grid) that covers the whole of the simulation space, separate grids (local grids) are generated that surround each object. The resolution of a local grid is higher than that of the global grid. The local grids move according to the motion of the objects. Therefore, the process of resampling the shape of the object is unnecessary when the object moves. To accelerate the computation, appropriate resolutions are adaptively‐determined for the local grids according to their distance from the viewpoint. Furthermore, since we use regular (orthogonal) lattices for the grids, the method is suitable for GPU implementation. This realizes the real‐time simulation of interactions between objects and smoke. 相似文献
13.
A partial semi-coarsening multigrid method based on the high-order compact (HOC) difference scheme on nonuniform grids is developed to solve the 2D convection–diffusion problems with boundary or internal layers. The significance of this study is that the multigrid method allows different number of grid points along different coordinate directions on nonuniform grids. Numerical experiments on some convection–diffusion problems with boundary or internal layers are conducted. They demonstrate that the partial semi-coarsening multigrid method combined with the HOC scheme on nonuniform grids, without losing the high-order accuracy, is very efficient and effective to decrease the computational cost by reducing the number of grid points along the direction which does not contain boundary or internal layers. 相似文献
14.
针对基于网格的聚类算法存在簇边缘网格中包含噪声点、利用网格相对密度差进行网格合并时不能区分密度均匀变化的网格等问题。提出一种利用区域划分的多密度快速聚类算法MFCBR。算法把数据空间划分成密度不同的网格,利用网格索引表和网格中心密度差合并网格形成簇,然后分别计算每个簇的边界网格质心、边界网格和最近簇网格中心位置,利用三者之间的关系来排除簇边界网格数据中包含的噪声点。实验表明,该算法在降低噪声数据对聚类干扰的同时,且对密度均匀变化的多密度数据集也有较优的处理效果。 相似文献
15.
Grid-partition index: a hybrid method for nearest-neighbor queries in wireless location-based services 总被引:1,自引:0,他引:1
Baihua Zheng Jianliang Xu Wang-Chien Lee Dik Lun Lee 《The VLDB Journal The International Journal on Very Large Data Bases》2006,15(1):21-39
Traditional nearest-neighbor (NN) search is based on two basic indexing approaches: object-based indexing and solution-based
indexing. The former is constructed based on the locations of data objects: using some distance heuristics on object locations.
The latter is built on a precomputed solution space. Thus, NN queries can be reduced to and processed as simple point queries
in this solution space. Both approaches exhibit some disadvantages, especially when employed for wireless data broadcast in
mobile computing environments.
In this paper, we introduce a new index method, called the grid-partition index, to support NN search in both on-demand access and periodic broadcast modes of mobile computing. The grid-partition index
is constructed based on the Voronoi diagram, i.e., the solution space of NN queries. However, it has two distinctive characteristics.
First, it divides the solution space into grid cells such that a query point can be efficiently mapped into a grid cell around
which the nearest object is located. This significantly reduces the search space. Second, the grid-partition index stores
the objects that are potential NNs of any query falling within the cell. The storage of objects, instead of the Voronoi cells, makes
the grid-partition index a hybrid of the solution-based and object-based approaches. As a result, it achieves a much more
compact representation than the pure solution-based approach and avoids backtracked traversals required in the typical object-based
approach, thus realizing the advantages of both approaches.
We develop an incremental construction algorithm to address the issue of object update. In addition, we present a cost model
to approximate the search cost of different grid partitioning schemes. The performances of the grid-partition index and existing
indexes are evaluated using both synthetic and real data. The results show that, overall, the grid-partition index significantly
outperforms object-based indexes and solution-based indexes. Furthermore, we extend the grid-partition index to support continuous-nearest-neighbor
search. Both algorithms and experimental results are presented.
Edited by R. Guting 相似文献
16.
Location privacy receives considerable attentions in emerging location based services.Most current practices however either ignore users’ preferences or incompletely fulfill privacy preferences.In this paper,we propose a privacy protection solution to allow users’ preferences in the fundamental query of k nearest neighbors (kNN).Particularly,users are permitted to choose privacy preferences by specifying minimum inferred region.Via Hilbert curve based transformation,the additional workload from users’ preferences is alleviated.Furthermore,this transformation reduces time-expensive region queries in 2-D space to range the ones in 1-D space.Therefore,the time efficiency,as well as communication efficiency,is greatly improved due to clustering properties of Hilbert curve.Further,details of choosing anchor points are theoretically elaborated.The empirical studies demonstrate that our implementation delivers both flexibility for users’ preferences and scalability for time and communication costs. 相似文献
17.
A front-tracking method for compressible multi-fluid flows is presented, where marker points are used both for tracking fluid interfaces and also for constructing the Riemann problem on the interfaces. The Riemann problem between the two fluid phases (defined in the interface normal direction) is solved using the exact Riemann solver on the marker points. The solutions are projected onto fixed grid points and then extrapolated into the corresponding ghost-fluid regions, to be used as boundary conditions. Each fluid phase is solved separately as in the ghost-fluid method. The proposed procedures, especially the projection of the exact Riemann solutions onto the fluid grids, are designed to be simple and consistent in any spatial dimensions. Several multi-fluid problems, including the breakup of a water cylinder induced by the passage of a shock wave were computed in order to demonstrate the capability of the proposed method. 相似文献
18.
针对常用的匹配点筛选算法效率低、对具有角度和尺度变化匹配图像稳定性差等问题,提出一种基于局部聚类的改进网格运动统计特征点筛选算法。首先,通过局部区域抑制算法筛选响应强度较高且成对出现特征点作为种子点,并以种子点为聚类中心分割图像,得到最小外接矩形作为运动网格;随后把运动网格划分为3×3邻域支持估计量网格,计算运动网格在不同方向上的梯度最大值,作为运动网格的主方向;最后,把待匹配图像邻域支持估计量网格旋转至目标图像运动网格的主方向位置,借助网格运动统计算法筛选匹配。实验表明:对具有JPEG压缩变换、光照变化、模糊变换的匹配图像,所提算法匹配正确率在90%以上;对具有旋转和尺度变换图像,所提算法匹配正确率相较运动网格统计算法提高10%左右,高达40%以上;算法耗时仅为13 min,效率较高;所提算法可稳定高效地筛选正确的匹配点。 相似文献
19.
D. L. Marcum 《Engineering with Computers》2001,17(3):211-233
Procedures are presented for efficient generation of high-quality unstructured surface and volume grids. The overall procedure
is based on the well proven Advancing Front/Local-Reconnection (AFLR) method. The AFLR triangular/tetrahedral grid generation
procedure is a combination of automatic point creation, advancing type ideal point placement, and connectivity optimization
schemes. A valid grid is maintained throughout the grid generation process. This provides a framework for implementing efficient
local search operations using a simple data structure. It also provides a means for smoothly distributing the desired point
spacing in the field using a point distribution function. This function is propagated through the field by interpolation from
the boundary point spacing or by specified growth normal to the boundaries. Points are generated using either advancing- front
type point placement for isotropic elements, advancing-point type point placement for isotropic right angle elements, or advancing-normal
type point placement for high-aspect-ratio elements. The connectivity for new points is initially obtained by direct subdivision
of the elements that contain them. Local-reconnection with a min-max type (minimize the maximum angle) type criterion is then
used to optimize the connectivity. The overall procedure is applied repetitively until a complete field grid is obtained.
An advancing-normal procedure is coupled with AFLR for anisotropic tetrahedral and pentahedral element grids. Advancing along
prescribed normals from solid boundaries generates layers of anisotropic elements. The points are generated such that either
pentahedral or tetrahedral elements with an implied connectivity can be directly recovered. The AFLR surface grid procedure
uses an approximate physical space grid to define the surface during grid generation. The mapped space coordinates are mapped
back to the actual surface at completion. Multiple surface definition patches are grouped into a single surface. A global
mapping transformation is generated for the single surface using the grouped surface connectivity. The mapping coordinates
are obtained by solving a coupled set of Laplacian equations. The overall procedure has been applied to a wide variety of
configurations. Selected results are presented which demonstrate that high-quality unstructured grids can be efficiently and
consistently generated for complex configurations. 相似文献