【作者】 徐红波；

【导师】 郝忠孝；

【作者基本信息】 哈尔滨理工大学 ， 计算机应用技术， 2010， 博士

【摘要】 空间数据库是当前数据库领域中一个前沿研究课题。空间数据库突破了传统数据库主要基于文字和数字信息的应用,能够存储和分析大量具有复杂结构的空间信息。空间数据库是一种存储非空间和空间数据的数据库系统,在查询语言和数据模型中支持空间数据类型、空间索引、空间分析和空间查询。近年来,在很多领域中出现了高维数据应用,例如基于内容的多媒体检索和数据仓库,数据常常以高维向量的形式存在,并且数据量都比较大。在实际查询过程中,例如在医疗诊断领域,电子商务,用户不仅对检索精度有一定的要求,对检索时间也会提出更高的要求,必须保证系统有较高的检索效率,因此有必要研究针对大规模高维向量空间的高效查询算法。在低维空间中线性扫描算法及基于R树、VA文件和NB树的空间查询算法的查询效率较高,而在高维空间中这些算法的查询效率均出现不同程度上的恶化现象。空间填充曲线是一种把d维空间映射成一维空间的方法。它像一条线一样穿过高维空间中每个离散单元,且只穿过一次。它按照线性顺序对这些单元进行编号。针对上述算法应用到高维空间时查询效率较低的问题,本文利用空间填充曲线的降低空间维度和数据聚类性质,依据曲线的构造过程将高维空间分割成大小相等的网格,从而将位于高维空间网格中的点映射到线性空间中。提出一种基于Hilbert曲线高维近似k最近邻查询算法AKNN。算法AKNN将d维空间中的点进行(d+1)次平移,将平移后的点映射到线性空间中,并用B~+树进行存储。算法AKNN扫描查询点在每棵B~+树中的k个前驱点和k个后继点,从2k(d+1)个候选点集中选择距离查询点最近的k个点作为近似k最近邻。提出一种基于Z曲线高维近似k最近对查询算法AKCP。算法AKCP在点集上进行(d+1)次线性扫描,每次扫描计算包含当前点与其k个后继点的最小网格,当最小网格的边长大于候选解的最大值时停止当前点的扫描操作,继续扫描下一点。使用Z区域聚类相似数据,设计一种改进的索引结构B~Z树,提出一种采用深度优先高维空间范围查询算法B~ZRQ。算法B~ZRQ采用高效剪枝策略,能够快速遍历B~Z树。提出一种基于Hilbert曲线网格划分聚类算法HC。算法HC首先以网格为单位合并出面积较小的聚集,然后将小聚集经过若干次合并形成较大聚集,最终使得聚集最优。实验结果表明这些算法可行且高效。更多还原

【Abstract】 The spatial database is a popular research of the database domain. The spatial database breaks through the traditional database system, which applys for the application of the information about the data of text and number. The spatial database can store and analyze massive data, which has complex structure. The spatial database is a kind of database system, which can store spatial and non-spatial data. Data model and query language of the spatial database sustains spatial data type, spatial index structure, spatial query and spatial analysis.Recently, the application of high-dimensional data appears in many domains, such as data warehouse and multimedia query based on the content of objects. In real query process, such as electronic commerce, medical diagnosis, the users not only have high demand of query precision, but also have high demand of query time. Therefore, these application systems must have high query efficiency. There is a need to study fast query algorithms of massive high-dimensional space.The spatial query algorithms based on Brute-Force method, R-tree, VA-file and NB-tree achieve better performance in low-dimensional space, but their performance suffers greatly in high-dimensional space. The reduction of the dimensionality is the key to the spatial query in high-dimensional space. The space-filling curve is a mapping method from high-dimensional space to linear space, divides the whole space into equal-size grids, and imposes a linear order of the points in the grids.Because the performance of above algorithms suffers greatly in high-dimensional space, the paper uses the characteristics of reducing dimensionality and clustering data of space-filling curves. According to the procedure of constructing the space-filling curves, divide high-dimensional space into equal-size grids. Therefore, map the points lying in the grids into linear space.The paper presents a high-dimensional approximate k-nearest-neighbor query algorithm AKNN based on Hilbert curve. The algorithm AKNN transforms the points in d dimensional space (d+1) times, maps the points into linear space, uses B~+-tree to store the points. The algorithm AKNN scans k previous and successive points of the query point in B~+-trees, and chooses 2k(d+1) points which are nearest as approximate k nearest neighbors.The paper presents a high-dimensional approximate k-closest-pair query algorithm AKCP based on Z curve. The algorithm AKCP scans the points (d+1) times linearly, calculates the minimum grid of the current point and its kth successive point. When the border length of the minimun grid is greater than the muminun of the candidates, the current point is neglected.Using the notion Z-region to cluster similar data, the paper presents an improved index structure B~Z-tree, a depth-first range query algorithm B~ZRQ in high-dimensional space. The algorithm B~ZRQ uses effective strategy to cut the branches, scans B~Z-tree quickly.The paper presents a grid-partition cluster algorithm HC based on Hilbert curve. First, the algorithm HC merges numerous small clusters based on the grids. Then it merges the clusters in many rounds. Finally, it gets large better clusters.The experiments show these algorithms are applicable and effective.更多还原