圖書信息
書名：《多維與度量數據結構基礎》
作者：周立柱
多維與度量數據結構基礎定價：129元
印次：1-1
裝幀：平裝
出版社：清華大學出版社
印刷日期：2011-4-21
內容簡介
數據結構是計算機學科知識體系中重要的基礎部分，是計算機專業本科與研究生教育必設的課程。近年來，計算機領域研究的持續深入和新研究方向的不斷出現，給數據結構帶來了嶄新的內容。這些內容極大地豐富和發展了數據結構的內涵。美國馬里蘭大學Hanan Samet教授撰寫的Foundations of Multidimensional and Metric Data Structures 一書則是對這些進展的一次可貴的總結和提升。該書系統地收集和整理了近年來地理資料庫、多媒體技術、圖像處理、數據挖掘與分析等領域裡著名的數據結構和算法，無論是站在基礎知識學習的角度，還是站在科學研究的角度看，它都是一本彌足珍貴的參考書。也正是出於對本書價值的以上認識，作者把它翻譯成中文，即大家所看到的這本《多維與度量數據結構基礎》。
在數據結構領域，Hanan Samet教授是公認的集大成者和國際著名學者。他對前面提到的諸多研究領域的豐富成果進行匯集，把它們歸納為多維空間數據的表示、組織、索引及查找等重要研究方向，其涉及的問題源自於各種實際套用，並從理論的角度得以抽象和統一。他在書中對相關算法和數據結構性能優劣的分析，為紛繁複雜的實際套用問題的成功解決提供了十分有益的啟迪。因此，本書不僅能為我們了解相關領域最新進展提供重要的參考，也必將為有志於相關研究的讀者提供方向性的指導。此外，得益於其翔實而精闢的講解、數量眾多而形象生動的插圖、要點突出且啟發性與挑戰性兼具的習題、全面而系統的參考索引，本書也是難得的絕佳教材。
圖書目錄
第1章 多維點數據 1
1.1 引言 4
1.2 區域樹 13
1.3 優先搜尋樹 17
1.4 四叉樹 25
1.4.1 點四叉樹 25
1.4.2 基於前綴樹的四叉樹 35
1.4.3 點四叉樹與基於前綴樹的
四叉樹之間的比較 44
1.5 k-d樹 45
1.5.1 點k-d樹 46
1.5.2 基於前綴樹的k-d 樹 65
1.5.3 結合樹 82
1.6 一維排序 84
1.7 桶方法 89
1.7.1 樹目錄方法 90
1.7.2 格線目錄方法 121
1.7.3 存儲利用率 153
1.8 PK-樹 154
1.8.1 動機 154
1.8.2 概述 157
1.8.3 定義 158
1.8.4 和桶式方法的比較 160
1.8.5 操作 160
1.8.6 討論 169
1.9 結論 172
第2章 基於物體與基於圖像的圖像表示 178
2.1 基於內部的表示 180
2.1.1 單位大小的單元 180
2.1.2 塊 192
2.1.3 非正交塊 220
2.1.4 任意形狀的物體 241
2.1.5 分層的基於內部的表示 252
2.2 基於邊界的表示 296
2.2.1 邊界模型 299
2.2.2 基於圖像的邊界表示 338
2.2.3 基於物體的邊界表示 364
2.2.4 基於表面的邊界表示 381
2.3 基於差別的壓縮方法 389
2.3.1 行程編碼 390
2.3.2 鏈碼 396
2.3.3 頂點表示 397
2.4 歷史回顧 403
第3章 區間及小矩形 407
3.1 平面掃描法與矩形求交問題 408
3.1.1 線段樹 410
3.1.2 區間樹 414
3.1.3 優先搜尋樹 418
3.1.4 其他方法及相關問題 422
3.2 平面掃描法與測度問題 425
3.3 基於點的方法 430
3.3.1 代表點 430
3.3.2 代表點集合 436
3.3.3 小結 442
3.4 基於區域的方法 443
3.4.1 MX-CIF四叉樹 444
3.4.2 MX-CIF四叉樹的替代
方案 451
3.4.3 多四叉樹塊表示法 457
第4章 多維數據 461
4.1 最佳優先的最近鄰查找 466
4.1.1 動機 466
4.1.2 搜尋層次 467
4.1.3 算法 469
4.1.4 重複對象實例算法 474
4.1.5 算法擴展（k-最近、k-最遠、
輪廓） 477
4.1.6 空間網路中的最近鄰 482
4.1.7 相關工作 490
4.2 深度優先的k-最近鄰查找 491
4.2.1 基本算法 492
4.2.2 剪枝規則 495
4.2.3 聚類法對剪枝的影響 503
4.2.4 活躍表元素的處理次序 508
4.2.5 改進的算法 512
4.2.6 在最佳優先算法中整合
MAXNEARESTDIST 521
4.2.7 實例 526
4.2.8 比較 527
4.3 近似的最近鄰查找 529
4.4 多維索引法 537
4.4.1 X-樹 538
4.4.2 包圍球法：Sphere樹、
SS樹、Ball樹、SR樹 538
4.4.3 提高扇出：TV-樹、混合樹
和A樹 542
4.4.4 基於Voronoi圖的方法：
os-樹 544
4.4.5 近似Voronoi圖（AVD） 550
4.4.6 避免所有葉塊的交疊 556
4.4.7 金字塔技術 558
4.4.8 基於順序掃描的方法 563
4.5 基於距離的索引法 568
4.5.1 距離度量與搜尋剪枝 570
4.5.2 球劃分法 575
4.5.3 廣義超平面劃分法 584
4.5.4 M-樹 595
4.5.5 Sa-樹 600
4.5.6 kNN圖（K近鄰圖） 609
4.5.7 距離矩陣法 615
4.5.8 SASH：無需藉助三角
不等式的索引 622
4.6 降維法 633
4.6.1 降維空間中的搜尋 634
4.6.2 僅用一維 638
4.6.3 代表點法 640
4.6.4 變換為不同、更小的
特徵集 641
4.6.5 小結 653
4.7 嵌入法 653
4.7.1 概述 655
4.7.2 Lipschitz嵌入 658
4.7.3 FastMap 664
4.7.4 位置敏感散列法 678
附錄A B-樹概覽 683
附錄B 線性散列 693
附錄C 螺旋散列 699
附錄D 偽代碼語言描述 706
習題解答 709
參考文獻 816
關鍵字索引 884
