度量空间索引与查询技术研究

摘要

随着计算机、互联网、通信以及定位技术的快速发展，科学计算、社会生活及工业生产不断产生出各类复杂数据。这些数据在形态上具有海量、高维、多源、异构、不确定/不完整等特征，因而需要借助于更广泛的空间模型，即度量空间。度量空间不受数据对象的几何特性限制，而只需要知道数据对象之间的距离度量方式即可。所以，度量空间具有更广阔的适用范围。
　　查询/搜索是计算机科学的基本问题，存在于目前几乎所有的计算机应用领域。为此，如何高效、智能地查询/检索数据，挖掘有价值的信息，服务于社会，理解和发现事物演化的规律，进而影响科技和社会的发展进程，已成为当今信息技术的重大挑战。
　　现有的（空间）索引和查询处理大多关注欧氏空间，使用多维向量表示数据对象，并用欧氏距离来度量对象之间的邻近关系。然而，在度量空间下，数据对象可能不存在维度信息且相似性的度量方式也不局限于欧氏距离。因此，欧氏空间下的索引与查询技术不能有效地解决度量空间下的索引与查询问题。鉴于此，本文对度量空间下的索引与查询技术进行了深入研究，主要包括:
　　1)度量空间索引:现有的度量空间索引结构可以分为基于支枢点的索引方法、基于划分的索引方法和混合索引方法。基于支枢点的索引方法在距离计算次数上（即CPU代价）优于基于划分的索引方法，但其存储空间消耗过大且I/O代价较大。为此，本文将展开结合基于支枢点的索引和基于划分的索引这两类方法的研究，开发支持度量空间查询（如度量相似查询等）的高效度量空间索引结构。此外，在现实生活中，设备的局限性、持续的数据更新、隐私保护、高通量测序技术等原因可能导致数据的不确定性。所以，本文设计了不确定数据上的度量空间索引结构，以支持不确定数据上的度量空间查询（如度量概率区域查询等）。
　　2)度量空间查询:尽管已有许多的专家学者致力于度量查询处理技术研究，并取得了大量可喜的研究成果，但距离满足人们不断出现的、复杂而多样的查询需求还有一定的差距，仍有待相关研究的进一步深入。例如，已有的度量全k最近邻查询和度量k最近对查询的处理技术都是基于内存的方法（即假设整个数据集可以保存在内存中），因而适用性有限且扩展性差，故不能用来处理大规模数据。因此，本文研究了基于外存的高效度量全k最近邻查询和度量k最近对查询的处理技术。
　　3)度量空间查询可用性:在实际应用中，查询返回的结果可能是用户预料之外的。这时，用户可能想要寻求相应的解释以更好地进行查询。现有的度量查询研究仅仅关注查询效率的提高，而并未关注查询的可用性。因此，针对查询结果与用户期望不一致的情况，本文展开了度量查询交互问题（即度量概率区域查询上的why-not问题）研究，以实现查询与用户的良好交互。
　　4)度量空间应用系统:集成上述研究成果，本文开发了一个分布式的社交图像检索与推荐系统。该系统利用社交网络中的图像、文本、时间和位置等数据，采用度量索引与查询技术，从而支持热点发现、图像检索以及图像推荐等功能。

目录

声明

摘要

第1章 绪论

1．1 研究背景及意义

1．2 存在的问题

1．3 研究目标与内容

1．3．1 研究目标

1．3．2 研究内容

1．4 论文结构组织

第2章 度量空间索引与查询综述

2．1 度量空间索引

2．2 度量空间查询

2．3 度量空间其它相关工作

2．4 本章小结

第3章 度量空间索引

3．1 确定度量数据索引

3．1．1 研究动机

3．1．2 索引构建框架

3．1．3 支枢点选择方法

3．1．4 SPB树

3．1．5 基于SPB树的度量区域查询

3．1．6 基于SPB树的度量k最近邻查询

3．1．7 分析与讨论

3．1．8 实验评估

3．2 不确定度量数据索引

3．2．1 研究动机

3．2．2 数据表达模型

3．2．3 UPB树和UPB森林

3．2．4 支枢点选择方法

3．2．5 基于UPB树的度量概率区域查询

3．2．6 基于UPB森林的度量概率区域查询

3．2．7 分析与讨论

3．2．8 实验评估

3．3 本章小结

第4章 度量空间查询

4．1 度量全k最近邻查询

4．1．1 研究动机

4．1．2 问题陈述

4．1．3 剪枝策略

4．1．4 查询算法

4．1．5 分析与讨论

4．1．6 实验评估

4．2 度量k最近对查询

4．2．1 研究动机

4．2．2 问题陈述

4．2．3 剪枝策略

4．2．4 查询算法

4．2．5 分析与讨论

4．2．6 实验评估

4．3 本章小结

第5章 度量概率区域查询上的why-not问题

5．1 研究动机

5．2 问题陈述

5．3 查询算法

5．3．1 修改查询MPRQ(q，R，θ)

5．3．2 修改why-not数据集W

5．3．3 修改MPRQ(q，R，θ)和W

5．4 分析与讨论

5．5 实验评估

5．5．1 算法有效性评估

5．5．2 算法性能评估

5．6 本章小结

第6章 社交图像检索与推荐系统

6．1 研究动机

6．2 数据模型和查询

6．3 系统框架与实现

6．3．2 社交图像索引

6．3．3 查询处理

6．4 系统演示

6．5 本章小结

第7章 总结与展望

7．1 全文总结及创新点

7．2 未来工作

参考文献

攻读博士学位期间的主要研究成果

致谢