多维与度量数据结构基础

出版时间：2011-5  出版社：清华大学出版社  作者：萨姆特 (Hanan Samet)  页数：892  译者：周立柱,王宏,邓俊辉,赵颖  
Tag标签：无  

内容概要

　　《多维与度量数据结构基础》的出版，终于令纷繁多样的空间与多维索引方法得以统一连贯起来。hanan
samet乃是“空间数据索引”领域的资深权威。其早先出版的另两本专著，在过去的20年内已成为重要的文献。《多维与度量数据结构基础》则进一步整合了这些工作，并将此领域拓展至度量空间中的信息索引和查找。
　　《多维与度量数据结构基础》内容综合全面，却又不失为一本系统讲解相关思路的好教材。《多维与度量数据结构基础》由点、物体、矩形等多维区间、高维数据等4大章组成，叙述简明翔实，各节配有习题，且在最后给出了详细解答。本书还附有对b-树、线性散列、螺旋散列等的专题讲解，并给出了2000余条参考文献及作者索引，同时还通过网站(http：／／www．cs．umd．edu／~hjs／quadtree／)提供了演示程序及数据集。
　　通晓《多维与度量数据结构基础》绝非一日之功，对于那些有志于驾驭空间数据、科学计算数据场、体查询等图形学和视觉问题、数据挖掘中常见的高维数据场的人们而言，此书无疑足无价之宝。

作者简介

作者：（美国）萨姆特（Hanan Samet） 译者：周立柱 王宏 邓俊辉 等

书籍目录

第1章 多维点数据
　1.1 引言
　1.2 区域树
　1.3 优先搜索树
　1.4 四叉树
　　1.4.1 点四叉树
　　1.4.2 基于前缀树的四叉树
　　1.4.3 点四叉树与基于前缀树的四叉树之间的比较
　1.5 k-d树
　　1.5.1 点k-d树
　　1.5.2 基于前缀树的k-d树
　　1.5.3 结合树
　1.6 一维排序
　1.7 桶方法
　　1.7.1 树目录方法
　　1.7.2 网格目录方法
　　1.7.3 存储利用率
　1.8 pk-树
　　1.8.1 动机 　　
　　1.8.2 概述
　　1.8.3 定义
　　1.8.4 和桶式方法的比较
　　1.8.5 操作
　　1.8.6 讨论
　1.9 结论
第2章 基于物体与基于图像的图像表示
　2.1 基于内部的表示
　　2.1.1 单位大小的单元
　　2.1.2 块
　　2.1.3 非正交块
　　2.1.4 任意形状的物体
　　2.1.5 分层的基于内部的表示
　2.2 基于边界的表示
　　2.2.1 边界模型
　　2.2.2 基于图像的边界表示
　　2.2.3 基于物体的边界表示
　　2.2.4 基于表面的边界表示
　2.3 基于差别的压缩方法
　　2.3.1 行程编码
　　2.3.2 链码
　　2.3.3 顶点表示
　2.4 历史回顾
第3章 区间及小矩形
　3.1 平面扫描法与矩形求交问题
　　3.1.1 线段树
　　3.1.2 区间树
　　3.1.3 优先搜索树
　　3.1.4 其他方法及相关问题
　3.2 平面扫描法与测度问题
　3.3 基于点的方法
　　3.3.1 代表点
　　3.3.2 代表点集合
　　3.3.3 小结
　3.4 基于区域的方法-
　　3.4.1 mx-cif四叉树
　　3.4.2 mx-cif四叉树的替代方案
　　3.4.3 多四叉树块表示法
第4章 多维数据
　4.1 最佳优先的最近邻查找
　　4.1.1 动机
　　4.1.2 搜索层次
　　4.1.3 算法
　　4.1.4 重复对象实例算法
　　4.1.5 算法扩展(k-最近、k-最远、轮廓)
　　4.1.6 空间网络中的最近邻
　　4.1.7 相关工作
　4.2 深度优先的k-最近邻查找
　　4.2.1 基本算法
　　4.2.2剪枝规则
　　4.2.3 聚类法对剪枝的影响
　　4.2.4 活跃表元素的处理次序
　　4.2.5 改进的算法
　　4.2.6 在最佳优先算法中整合maxnearestdist
　　4.2.7 实例
　　4.2.8 比较
　4.3 近似的最近邻查找
　4.4 多维索引法
　　4.4.1 x-树
　　4.4.2 包围球法：sphere树、ss树、ball树、sr树
　　4.4.3 提高扇出：tv-树、混合树和a树
　　4.4.4 基于voronoi图的方法：os-树
　　4.4.5 近似voronoi图(avd)
　　4.4.6 避免所有叶块的交叠
　　4.4.7 金字塔技术
　　4.4.8 基于顺序扫描的方法
　4.5 基于距离的索引法
　　4.5.1 距离度量与搜索剪枝
　　4.5.2 球划分法
　　4.5.3 广义超平面划分法
　　4.5.4 m-树
　　4.5.5 sa-树
　　4.5.6 knn图(k近邻图)
　　4.5.7 距离矩阵法
　　4.5.8 sash：无需借助三角不等式的索引
　4.6 降维法
　　4.6.1 降维空间中的搜索
　　4.6.2 仅用一维
　　4.6.3 代表点法
　　4.6.4 变换为不同、更小的特征集
　　4.6.5 小结
　4.7 嵌入法
　　4.7.1 概述
　　4.7.2 lipschitz嵌入
　　4.7.3 fastmap
　　4.7.4 位置敏感散列法
附录a b-树概览
附录b 线性散列
附录c 螺旋散列
附录d 伪代码语言描述
习题解答
参考文献
关键词索引
　　　　

章节摘录

版权页：插图：多维点数据的表示是数据库设计以及许多应用领域，如计算机图形学、计算机视觉、计算几何、图像处理、地理信息系统（GIS）、模式识别、超大规模集成电路设计（VLSI）等的核心问题。这些数据可以代表空间的位置与物体，也可以代表一般记录。以一般记录为例，一条雇员的记录可以含有姓名、地址、性别、年龄、身高、体重以及社会安全号等属性。数据库管理系统中的这些记录可以看成是7维（每个属性或关键字代表一维）空间的一个点，而每个维度的数据具有不同的类型（如姓名和地址是字符串，性别是二进制的位，年龄、身高、体重以及社会安全号是数字）。形式化地说，数据库是称为文件的许多记录的集合，每个数据点是一个记录，而每个记录含有若干属性或关键字。为了处理按属性值。检索记录，我们假定对于每个属性的值是可以排序的。对于位置或者数值性的属性，因为它们的值都是数，所以排序是自然的事情。对于字符型的数据，排序一般按照属性值所包含的字符序列进行。其他数据，例如颜色，可以按照组成它们的字符串排序，也可以按照它们的波长排序。显然，总可以找到一个属性值的排序方法，而究竟使用哪种方法则是问题的关键。多维点数据的表示的最终选择部分地和以下问题紧密相关：1.数据的性质（如是离散还是连续，其值域是否有穷）。2.数据所执行的操作。3.是要对数据还是要对嵌入数据的空间进行组织。4.数据库是动态还是静态（即数据点是否根据需要增减）。5.数据量是否可以仅存于内存还是必需磁盘空间的支持。以上问题至关重要。当然，我们必须区分数据是由一个还是多个属性组成这样两种不同的情况。传统的属性值包括二进制的位、整数、实数、复数、字符、字符串等。与数据的性质有关的另一个问题是属性所取的这些值是否有穷（即有限）。对于这一问题的回答会部分地对上面问题3中的数据组织的选择产生影响。就数据是离散还是连续而言，在通常的科学计算中离散数据对应的是整数，而连续数据对应的是实数或复数。空间数据，我们有离散数据（指不同的样本或实例），例如空间点（本章的重点，另在第4章少量涉及）；还有构成线段、区域、表面、体积的连续数据等（第2章的重点，另在第3章少量涉及）。同样，时态数据也有离散与连续之分。例如，事件时间以及事务时间就是离散的。而速率则更多是连续的，因为它随着时间在不停地变化。在本书里，我们不会涉及时态数据或者与之关系密切的时空数据。

编辑推荐

《多维与度量数据结构基础》是世界著名计算机教材精选之一。

用户评论 (总计16条)

•   印刷和包装质量很好。内容侧重于多维数据的搜索，比如各种树数据结构，内容和参考文献很丰富，是一本好书。
•   不错，翻译质量很好！
  书的内容也很好，有参考价值，值得购买！
•   深深的感觉到国外和国内教材的巨大差距
•   东西很好吧。有点复杂。看啦一下。呵呵
•   国内的作者怎么写不出这种书呢
•   出自大家之手，块头不小，值得参考吧
•   内容不错，中文，内容有点深，慢慢读
•   非常好的一本书，慢慢看。
•   需要细细品读，并不是很容易理解。
•   “它们采用单值分解（singular value de***position, SVD）等方法……”
  奇异值分解这么基本的东西都错。
•   书精装 很厚，排版还行
•   好处是书中讲的算法很全面，我硕士论文就是写这个的，受益匪浅，缺点是新算法不够多。
  翻译的比较流畅，不过有些名词翻译不合常规，别的不说，书名的翻译都有点歪曲原来的意思，什么多维与度量，模棱两可
•   看了 一部分了，挺好的……
•   有点专业性太强，不建议本科生或非此专业的研究生读
•   不好 看不懂 翻译的不好
•   很多概念没交代清楚，东西泛但不精，最关键是要命的翻译，翻译得太乱了