多样k-支配轮廓查询方法研究

摘要

轮廓查询技术是空间查询及优化领域的研究热点，k-支配轮廓技术是近年来轮廓查询技术领域的新的研究方向。k-支配轮廓查询及其动态处理被广泛使用在多种空间数据库中，在数据挖掘、数据库可视化、多目标决策等方面的潜在应用很大。本文在对k-支配轮廓查询及其更新技术进行研究的基础上，提出多样k-支配轮廓的概念，并对其进行了深入的研究，主要内容如下。
　　首先，针对现有的k-支配轮廓算法返回结果单一的问题，首先提出k-支配属性的概念，其次给出k-支配轮廓的k-支配属性集的查找算法，然后证明k-支配属性集查找的NP完全性，最后对所提的算法进行了理论证明和实例分析。
　　其次，在分析现有的k-支配轮廓查询算法的优缺点的基础上，首先提出多样k-支配轮廓的概念，其次证明多样k-支配轮廓性质定理，然后并以此为基础给出多样 k-支配轮廓枚举算法和多样 k-支配轮廓索引算法来实现空间数据集的多样k-支配轮廓查找问题，最后对给出的算法进行理论证明和实例分析。
　　再次，对于数据的属性值更新时多样k-支配轮廓需要重新计算的问题，提出多样k-支配轮廓更新算法。对于单个数据点的属性值变化给出点属性算法，同时针对若干点的属性值变化的情况给出集合属性算法，最后对所提出的算法进行理论分析。
　　第四，对于数据集中数据点增加和删除时多样 k-支配轮廓失效的情况，提出新的多样k-支配轮廓求解方法。针对不同的情形，分别提出增加点多样k-支配轮廓算法和删除点多样k-支配轮廓算法，最后对每个算法进行理论分析。
　　最后，对上述部分算法进行实验验证，给出实验结果图表，并对实验的结果进行分析和比较。

目录

封面

声明

中文摘要

英文摘要

目录

第1章 绪论

1.1 研究背景

1.2 研究现状

1.3 研究意义

1.4 研究内容

1.5 本文组织结构

第2章 基础知识

2.1 引言

2.2 空间数据模型

2.3 空间查询语言

2.4 空间操作

2.5 本章小结

第3章 k-支配属性集的查找

3.1 引言

3.2 基本定义

3.3 k-支配属性集性质

3.4 k-支配属性集枚举查找算法

3.5 空间索引

3.6 k-支配属性集索引查找算法

3.7 本章小结

第4章 多样k-支配轮廓的查找方法

4.1 引言

4.2 基本定义

4.3 基本性质

4.4 多样k-支配轮廓枚举算法

4.5 多样k-支配轮廓索引算法

4.6 本章小结

第5章 动态环境下多样k-支配轮廓查找

5.1 引言

5.2 属性值变化时多样k-支配轮廓查找方法

5.3 非数据流下多样k-支配轮廓的查找

5.4 本章小结

第6章 算法的实验验证

6.1 引言

6.2 验证多样k-支配轮廓查询算法

6.3 验证单点属性值变化多样k-支配轮廓更新技术

6.4 验证若干点属性值变化多样k-支配轮廓更新技术

6.5 本章小结

结论

参考文献

攻读硕士学位期间承担的科研任务与主要成果

致谢

作者简介