多維與度量數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)

內(nèi)容概要

　　《多維與度量數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)》的出版，終于令紛繁多樣的空間與多維索引方法得以統(tǒng)一連貫起來。hanan
samet乃是“空間數(shù)據(jù)索引”領(lǐng)域的資深權(quán)威。其早先出版的另兩本專著，在過去的20年內(nèi)已成為重要的文獻。《多維與度量數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)》則進一步整合了這些工作，并將此領(lǐng)域拓展至度量空間中的信息索引和查找。
　　《多維與度量數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)》內(nèi)容綜合全面，卻又不失為一本系統(tǒng)講解相關(guān)思路的好教材。《多維與度量數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)》由點、物體、矩形等多維區(qū)間、高維數(shù)據(jù)等4大章組成，敘述簡明翔實，各節(jié)配有習(xí)題，且在最后給出了詳細解答。本書還附有對b-樹、線性散列、螺旋散列等的專題講解，并給出了2000余條參考文獻及作者索引，同時還通過網(wǎng)站(http：／／www．cs．umd．edu／~hjs／quadtree／)提供了演示程序及數(shù)據(jù)集。
　　通曉《多維與度量數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)》絕非一日之功，對于那些有志于駕馭空間數(shù)據(jù)、科學(xué)計算數(shù)據(jù)場、體查詢等圖形學(xué)和視覺問題、數(shù)據(jù)挖掘中常見的高維數(shù)據(jù)場的人們而言，此書無疑足無價之寶。

作者簡介

作者：（美國）薩姆特（Hanan Samet） 譯者：周立柱 王宏 鄧俊輝 等

書籍目錄

第1章 多維點數(shù)據(jù)
　1.1 引言
　1.2 區(qū)域樹
　1.3 優(yōu)先搜索樹
　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 結(jié)合樹
　1.6 一維排序
　1.7 桶方法
　　1.7.1 樹目錄方法
　　1.7.2 網(wǎng)格目錄方法
　　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 結(jié)論
第2章 基于物體與基于圖像的圖像表示
　2.1 基于內(nèi)部的表示
　　2.1.1 單位大小的單元
　　2.1.2 塊
　　2.1.3 非正交塊
　　2.1.4 任意形狀的物體
　　2.1.5 分層的基于內(nèi)部的表示
　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章 區(qū)間及小矩形
　3.1 平面掃描法與矩形求交問題
　　3.1.1 線段樹
　　3.1.2 區(qū)間樹
　　3.1.3 優(yōu)先搜索樹
　　3.1.4 其他方法及相關(guān)問題
　3.2 平面掃描法與測度問題
　3.3 基于點的方法
　　3.3.1 代表點
　　3.3.2 代表點集合
　　3.3.3 小結(jié)
　3.4 基于區(qū)域的方法-
　　3.4.1 mx-cif四叉樹
　　3.4.2 mx-cif四叉樹的替代方案
　　3.4.3 多四叉樹塊表示法
第4章 多維數(shù)據(jù)
　4.1 最佳優(yōu)先的最近鄰查找
　　4.1.1 動機
　　4.1.2 搜索層次
　　4.1.3 算法
　　4.1.4 重復(fù)對象實例算法
　　4.1.5 算法擴展(k-最近、k-最遠、輪廓)
　　4.1.6 空間網(wǎng)絡(luò)中的最近鄰
　　4.1.7 相關(guān)工作
　4.2 深度優(yōu)先的k-最近鄰查找
　　4.2.1 基本算法
　　4.2.2剪枝規(guī)則
　　4.2.3 聚類法對剪枝的影響
　　4.2.4 活躍表元素的處理次序
　　4.2.5 改進的算法
　　4.2.6 在最佳優(yōu)先算法中整合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 金字塔技術(shù)
　　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 小結(jié)
　4.7 嵌入法
　　4.7.1 概述
　　4.7.2 lipschitz嵌入
　　4.7.3 fastmap
　　4.7.4 位置敏感散列法
附錄a b-樹概覽
附錄b 線性散列
附錄c 螺旋散列
附錄d 偽代碼語言描述
習(xí)題解答
參考文獻
關(guān)鍵詞索引
　　　　

章節(jié)摘錄

版權(quán)頁：插圖：多維點數(shù)據(jù)的表示是數(shù)據(jù)庫設(shè)計以及許多應(yīng)用領(lǐng)域，如計算機圖形學(xué)、計算機視覺、計算幾何、圖像處理、地理信息系統(tǒng)（GIS）、模式識別、超大規(guī)模集成電路設(shè)計（VLSI）等的核心問題。這些數(shù)據(jù)可以代表空間的位置與物體，也可以代表一般記錄。以一般記錄為例，一條雇員的記錄可以含有姓名、地址、性別、年齡、身高、體重以及社會安全號等屬性。數(shù)據(jù)庫管理系統(tǒng)中的這些記錄可以看成是7維（每個屬性或關(guān)鍵字代表一維）空間的一個點，而每個維度的數(shù)據(jù)具有不同的類型（如姓名和地址是字符串，性別是二進制的位，年齡、身高、體重以及社會安全號是數(shù)字）。形式化地說，數(shù)據(jù)庫是稱為文件的許多記錄的集合，每個數(shù)據(jù)點是一個記錄，而每個記錄含有若干屬性或關(guān)鍵字。為了處理按屬性值。檢索記錄，我們假定對于每個屬性的值是可以排序的。對于位置或者數(shù)值性的屬性，因為它們的值都是數(shù)，所以排序是自然的事情。對于字符型的數(shù)據(jù)，排序一般按照屬性值所包含的字符序列進行。其他數(shù)據(jù)，例如顏色，可以按照組成它們的字符串排序，也可以按照它們的波長排序。顯然，總可以找到一個屬性值的排序方法，而究竟使用哪種方法則是問題的關(guān)鍵。多維點數(shù)據(jù)的表示的最終選擇部分地和以下問題緊密相關(guān)：1.數(shù)據(jù)的性質(zhì)（如是離散還是連續(xù)，其值域是否有窮）。2.數(shù)據(jù)所執(zhí)行的操作。3.是要對數(shù)據(jù)還是要對嵌入數(shù)據(jù)的空間進行組織。4.數(shù)據(jù)庫是動態(tài)還是靜態(tài)（即數(shù)據(jù)點是否根據(jù)需要增減）。5.數(shù)據(jù)量是否可以僅存于內(nèi)存還是必需磁盤空間的支持。以上問題至關(guān)重要。當(dāng)然，我們必須區(qū)分數(shù)據(jù)是由一個還是多個屬性組成這樣兩種不同的情況。傳統(tǒng)的屬性值包括二進制的位、整數(shù)、實數(shù)、復(fù)數(shù)、字符、字符串等。與數(shù)據(jù)的性質(zhì)有關(guān)的另一個問題是屬性所取的這些值是否有窮（即有限）。對于這一問題的回答會部分地對上面問題3中的數(shù)據(jù)組織的選擇產(chǎn)生影響。就數(shù)據(jù)是離散還是連續(xù)而言，在通常的科學(xué)計算中離散數(shù)據(jù)對應(yīng)的是整數(shù)，而連續(xù)數(shù)據(jù)對應(yīng)的是實數(shù)或復(fù)數(shù)?？臻g數(shù)據(jù)，我們有離散數(shù)據(jù)（指不同的樣本或?qū)嵗?，例如空間點（本章的重點，另在第4章少量涉及）；還有構(gòu)成線段、區(qū)域、表面、體積的連續(xù)數(shù)據(jù)等（第2章的重點，另在第3章少量涉及）。同樣，時態(tài)數(shù)據(jù)也有離散與連續(xù)之分。例如，事件時間以及事務(wù)時間就是離散的。而速率則更多是連續(xù)的，因為它隨著時間在不停地變化。在本書里，我們不會涉及時態(tài)數(shù)據(jù)或者與之關(guān)系密切的時空數(shù)據(jù)。

編輯推薦

《多維與度量數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)》是世界著名計算機教材精選之一。

圖書封面

圖書標(biāo)簽Tags

無

評論、評分、閱讀與下載

---

    多維與度量數(shù)據(jù)結(jié)構(gòu)基礎(chǔ) PDF格式下載

---