计算机图形学论文_论图计算
計算機圖形學論文
自從機械計算開始以來，圖形概念就已經存在，并且在純數學領域已經存在了數十年。 由于數據庫的黃金時代，圖形在軟件工程中變得越來越流行。 圖形數據庫提供了一種持久化和處理圖形數據的方法。 但是，圖形數據庫并不是存儲和分析圖形的唯一方法。 圖形計算在使用圖形數據庫之前已有一段歷史，并且其未來不一定會與典型的數據庫問題糾纏在一起。 有許多圖形技術，每種技術都有其各自的優點和缺點。 有效的圖形計算需要在正確的時間利用正確的技術。
結構：使用圖對真實場景進行建模
圖 （或網絡 ）是一種數據結構。 它由頂點（點）和邊緣（線）組成。 許多現實世界的場景可以建模為圖形。 這不一定是現實的某些客觀性質所固有的，而是主要基于這樣一個事實，即人類根據客體（頂點）及其彼此之間的相互關系（邊緣）來主觀地解釋世界（一種反對這一觀點的論點 ）。 圖計算中常用的數據模型是屬性圖 。 以下示例說明了通過三種不同方案進行的圖形建模。
軟件圖
Stephen是名為TinkerPop的面向圖形的工程小組的成員 。 斯蒂芬為Rexster貢獻力量 。 Rexster通過軟件依賴關系與其他項目相關。 當用戶在Rexster中發現錯誤時，他們會發出票證 。 可以通過圖形方便地捕獲對協作編碼環境的描述。 頂點（或事物）是人員，組織，項目和票證。 邊緣（或關系）例如是成員資格，依賴關系和問題。 可以使用點和線將圖形可視化，下面描述了上述情況。
討論圖
Matthias對圖感興趣。 他是Aurelius的CTO和圖形數據庫Titan的項目負責人。 Aurelius有一個郵件列表 。 在此郵件列表上，人們討論了圖論和技術。 Matthias參與了討論。 他的貢獻越來越多。 郵件列表以遞歸方式表現為一棵樹 。 此外，消息的非結構化文本引用了共享概念。
概念圖
圖可以用來表示任意概念之間的關系，甚至是與圖有關的概念。 例如，請注意后面句子中的概念（斜體）如何關聯。 圖可以表示為鄰接表 。 處理圖的一般方法是通過圖遍歷 。 圖形遍歷有兩種常規類型： 深度優先和寬度優先 。 圖形可以保存在稱為圖形數據庫的軟件系統中。 圖形數據庫以不同于常見軟件知識的關系數據庫的方式組織信息。 在下圖中，與圖相關的概念相互鏈接，表明概念關系形成了圖。
多域圖
前面的三個場景（軟件，討論和概念）是真實系統（例如GitHub ， Google Groups和Wikipedia ）的表示。 這些看似完全不同的模型可以通過共享頂點無縫集成到單個原子圖結構中。 例如，在關聯的圖中， Gremlin是Titan依賴項，Titan由Matthias開發，Matthias在Aurelius的郵件列表中寫消息（軟件與討論合并）。 接下來， 藍圖是Titan的依賴項，Titan是帶標簽的圖 （軟件與概念合并）。 虛線表示其他此類跨域鏈接，這些鏈接演示了如何在跨域共享頂點時如何創建通用模型。 集成的通用模型可以經受比任何單個模型都可以單獨提供的服務更豐富（也許更智能）的服務。
流程：通過遍歷解決實際問題
到目前為止，已經提出了一組相互關聯的域的單個圖形模型。 僅當存在可以利用模型來解決問題的流程時，模型才有用。 就像數據需要算法一樣，圖也需要遍歷 。 遍歷是一種算法/定向遍歷圖，以便確定路徑（稱為導數）或收集信息（稱為統計信息）的過程。 甚至查看圖形可視化的人類視覺系統也是一個遍歷引擎，利用聲波運動來識別模式。 但是，隨著圖形的變大和問題需要精確的邏輯，可視化和人的內部計算器會崩潰。 接下來提供遍歷示例的集合，這些示例解決了先前討論的領域中的典型問題。
確定循環依賴
隨著開源軟件的增長以及將模塊輕松集成到項目中的便利， 循環依賴項比比皆是，并可能導致軟件工程中的問題。 當項目A依賴項目B，并且通過某種依賴路徑，項目B依賴項目A時，發生循環依賴。 當以圖形方式表示依存關系時，遍歷可以輕松識別出這種圓形度（例如，在下圖中， A-> B-> D-> G-> A是一個循環 ）。
排名討論貢獻者
郵件列表由參與和能力水平不同的個人組成。 當郵件列表專注于通過討論進行學習時，僅編寫消息并不一定表示積極貢獻。 如果產生了作者的消息答復，則可以解釋為該作者正在貢獻值得討論的材料。 但是，如果作者的消息結束了對話，那么他們可能貢獻了非演講者或無法使討論蓬勃發展的信息。 在關聯的圖中，米色頂點是作者，而它們各自的編號是唯一的作者ID。
對郵件列表上的貢獻者進行排名的一種方法是計算他們已發布的郵件數（作者對郵件列表中郵件的出奇程度 ）。 但是，如果排名必須考慮到卓有成效的貢獻，則可以根據其消息產生的討論深度（作者消息的樹深度）對作者進行排名。 最后，請注意，可以包含其他技術，例如情感和概念分析，以了解消息的含義和含義。
尋找相關概念
斯蒂芬對圖形的理解是在研究TinkerPop的圖形技術堆棧時發展起來的。 如今，他對學習更多有關圖的理論方面感興趣。 通過網絡瀏覽器，他訪問了Wikipedia 圖形頁面。 Stephen以手動方式單擊鏈接并閱讀文章-深度優先，圖形遍歷，鄰接表等。他意識到頁面之間相互引用，并且由于Wikipedia的鏈接結構，一些概念與其他概念更相關。 可以使用圖形遍歷自動執行步行鏈接的手動過程。 遍歷可以單擊圖形頂點而不是單擊，而不是單擊，而是向外傳播，并報告最受感動的概念。 流動最多的概念是具有許多關系（即路徑）的圖形概念 （請參閱先驗算法 ）。 通過這種遍歷，可以為Stephen提供圖形相關概念的排名列表。 這種遍歷類似于波在水體上擴散-盡管現實世界中的圖形拓撲很少像二維平面那樣簡單（請參見晶格 ）。
多域遍歷
先前討論的不同圖形模型（即軟件，討論和概念）通過共享頂點被集成到單個世界模型中。 類似地，可以構成上述圖遍歷以產生對跨域問題的解決方案。 例如：
“向我推薦參與的項目，這些項目應保持適當的依存關系結構，并請有貢獻的參與者來推廣該空間，并且在概念上與我以前研究過的技術有關。”
當異構的物聯網鏈接在一起并在其中有效移動時，這種類型的問題解決才有可能。 鏈接和移動的方法分別是圖形和遍歷。 總結本節，提供了其他有用的遍歷示例。
“基于項目的數量和其依賴項的數量，以遞歸方式計算項目的'穩定性等級'，以此類推。”
“根據項目之間的共享（或類似）概念進行集群項目。”
“建議一個開發人員團隊開發一個即將使用X依賴項并且與Y概念相關的項目。”
“按每期提交者所貢獻的項目數量來排名。”
圖計算技術
計算的實踐是圍繞兩個糾纏的量：空間和時間之間的細線。 在圖計算領域，存在相同的權衡。 本節將討論各種圖形技術，以識別每種選擇所獲得和犧牲的內容。 此外，提出了一些示例技術。 注意，存在更多的技術，并且所提到的示例絕不是窮舉性的。
內存中圖形工具包
內存中圖形工具包是面向圖形分析和可視化的單用戶系統。 它們通常提供在圖論和網絡科學文獻中定義的眾多圖算法的實現（請參閱Wikipedia的圖算法列表）。 這些工具的局限性在于它們只能對可以存儲在本地主存儲器中的圖形進行操作。 盡管這可能很大（數以百萬計的邊緣），但并不總是足夠的。 如果源圖數據集太大而無法放入主存儲器中，則通常使用此類內存中圖工具包將子集隔離并進行處理。
示例 ： JUNG ， NetworkX ， iGraph ，Fulgora（即將推出）
- [+]豐富的圖算法庫
- [+]豐富的圖形可視化庫
- [+]不同空間/時間折衷的不同內存表示形式
- [-]限于可以放入主內存的圖形
- [-]交互通常非常繁瑣
實時圖形數據庫
圖形數據庫也許是圖形計算技術最流行的化身。 它們提供事務語義，例如ACID（本地數據庫的典型值）和最終的一致性（分布式數據庫的典型值）。 與內存中圖形工具包不同，圖形數據庫利用磁盤來保留圖形。 在合理的機器上，本地圖數據庫可以支持數十億條邊，而分布式系統則可以處理數千億條邊。 在如此規模的情況下，在多用戶并發的情況下（隨機訪問磁盤和內存正在發揮作用），全局圖算法是不可行的。 可行的是局部圖算法/遍歷。 而不是遍歷整個圖形，而是將某些頂點集用作遍歷的源（或根）。
示例 ： Neo4j ， OrientDB ， InfiniteGraph ， DEX ， Titan
- [+]針對本地鄰域分析（“以自我為中心”的遍歷）進行了優化
- [+]經過優化，可處理大量并發用戶
- [+]交互是通過面向圖的查詢/遍歷語言進行的
- [-]由于隨機磁盤交互，全局圖分析效率低下
- [-]由于數據庫功能（例如事務語義）而導致的大量計算開銷
批處理圖框架
批處理圖框架利用計算集群。 該領域中大多數流行的框架都將Hadoop用于存儲（HDFS）和處理（MapReduce）。 這些系統面向全球分析。 也就是說，涉及整個圖數據集的計算，在許多情況下，涉及遍及整個圖多次的計算（迭代算法）。 此類分析不能實時運行。 但是，由于它們執行數據的全局掃描，因此可以利用從磁盤的順序讀取（請參閱《大數據病理學》 ）。 最后，像內存中系統一樣，它們面向數據科學家，或者在生產環境中用于將結果反饋到實時圖形數據庫中。
示例 ： Hama ， Giraph ， GraphLab ， Faunus
- [+]針對全局圖分析進行了優化
- [+]跨機器集群表示的流程圖
- [+]利用對磁盤的順序訪問來縮短讀取時間
- [-]不支持多個并發用戶
- [-]不是實時圖形計算系統
本節介紹了不同的圖形計算解決方案。 重要的是要注意，還存在諸如Convey的MX系列和Cray的YARC圖形引擎之類的硬件解決方案。 討論的每種技術都有一個重要的主題-它們專注于處理圖形數據。 每個類別的權衡取決于現代硬件/軟件以及理論計算機科學提出的限制。
結論
對于熟練的人來說，圖計算不僅是一套技術，而且是一種根據圖來思考世界以及根據遍歷來思考世界的方法。 隨著數據變得越來越可訪問，建立更豐富的環境模型變得更加容易。 越來越困難的是，以可以由不同計算系統方便且有效地處理的形式存儲該數據。 在許多情況下，圖是建模的自然基礎。 當模型是圖形時，則可以將多種圖形計算技術應用于該模型。
致謝
O'Reilly的Mike Loukides非常友好 ，可以審閱本文的多個版本，這樣做可以使本文變得更好。
翻譯自: https://www.javacodegeeks.com/2014/06/on-graph-computing.html
計算機圖形學論文
總結
以上是生活随笔為你收集整理的计算机图形学论文_论图计算的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 《心灵杀手 2》游戏新实机演示放出：艾伦
- 下一篇： 只能在测试中注射吗？