博士論文摘要| 仇阿根:基於分布式內存計算的空間數據近似查詢處理方法

2021-02-14 測繪學報

基於分布式內存計算的空間數據近似查詢處理方法

仇阿根     

中國測繪科學研究院, 北京 100830

收稿日期：2017-10-26

基金項目：測繪地理信息公益性行業科研專項（201512032）；測繪地理信息公益性行業科研專項（201512027）；中國測繪科學研究院基本科研業務費（7771614）；國家重點研發計劃（2016YFC0803108）

第一作者簡介：仇阿根(1976-), 男, 2017年6月畢業於武漢大學, 獲工學博士學位(指導教師:劉紀平研究員), 研究方向為政府地理信息服務與地理空間大數據技術。E-mail:qiuag@casm.ac.cn

In-memory Distributed Computing Based Approximate Query Processing on Spatial Data

QIU A'gen     

地理數據交互式可視化與空間分析等是地理信息系統(Geographic Information System, GIS)應用的重要功能，而現有的地理空間資料庫與地理數據服務標準難以滿足實時數據可視化及空間分析的要求。根源在於空間資料庫中地理要素的查詢結果是精確、唯一的；查詢時間和數據量只與要素本身相關；查詢時地理要素無法根據條件動態生成。而在實際應用中，地理要素可以是近似的、變化的；查詢時間和數據量可以作為查詢約束條件；地理要素可以根據查詢條件動態生成。

為此，本文提出以空間近似查詢結果表達地理要素，即通過頂點採樣實時生成要素並報告近似誤差，實現查詢時間和數據量的靈活控制。基於此，提出了海量空間數據集的多解析度表達模型，設計了以分布式內存計算、頂點樹型層次結構、加權廣度遍歷算法為基礎的空間近似查詢處理方法，實現了基於關係資料庫的空間近似查詢引擎，形成了基於空間近似查詢的網絡GIS架構，解決了網絡GIS的交互式可視化與空間分析的功能與性能問題。具體研究內容如下：

(1) 基於分布式內存計算的空間近似查詢理論。總結了近似查詢與分布式計算的基礎理論，根據地理要素的特點、地理數據交互式可視化與空間分析的需求，針對空間查詢數據量難以有效控制的問題，定義了面向交互式可視化的空間近似查詢，提出了多解析度表達模型。通過遞歸細分、數據採樣、應用處理、誤差計算等步驟建立表達模型，並將計算密集型任務分布化，提供了誤差與數據量可控的空間近似查詢基礎算法與數據結構。

(2) 地理要素近似誤差計算與頂點層次結構構建方法。基於遞歸細分與誤差計算的多解析度表達模型，將地理要素數據分布式內存計算處理，建立頂點樹型層次結構，形成了地理要素的多解析度表達。面向數據可視化，將地理要素數據遞歸細分係數設為2，提出了地理要素頂點層次結構的構建方法與存儲模型，設計實現了顧及誤差條件的空間索引等。

(3) 地理要素近似查詢算法。以加權廣度優先算法為基礎，提出了時間/數據量約束、誤差約束的地理要素窗口近似查詢處理算法，包括時間/數據量約束條件下樹型層次結構的加權廣度優先遍歷，在查詢過程中使用近似查詢約束條件與空間範圍約束條件，進行聯合剪枝以提高效率的方法；在關係模型的基礎上，研究查詢條件與空間連接的特點運用多維索引以提高效率的方法。

(4) 地理要素頂點層次結構動態更新算法。根據地理要素連續更新的特點，提出了基於最小化代價函數的頂點層次更新算法。以關係模型下頂點層次結構為基礎，研究代價最小的頂點層次結構局部更新方法，分析頂點序列的插入、刪除、修改等操作的計算複雜度及I/O複雜度，研究不同的頂點層次結構構建參數對於動態化更新算法的影響。

(5) 海岸線數據實證研究。提出了基於空間近似查詢引擎的網絡GIS架構，開發了地理數據交互式可視化原型系統。針對OpenStreetMap海岸線數據，建立了海岸線數據的頂點層次化資料庫，實現了地理要素的交互式可視化，並對試驗結果進行了對比分析，驗證了網絡GIS架構的可行性及空間近似查詢處理方法的實用性。

【引文格式】仇阿根。基於分布式內存計算的空間數據近似查詢處理方法[J]. 測繪學報，2017，46(12)：2044-2044. DOI: 10.11947/j.AGCS.2017.20170602

李德仁院士：老師教我做人做學問

8個地球的科學冷知識顛覆你的世界觀！

關於稿件「時間」安排那些事兒~

重磅！新增博士、碩士學位授權點名單出爐，有你的母校嗎

適合所有研究生讀的好文：陽光溫熱 科研靜好

世界上最有趣最冷門的地圖，刷新你的世界觀！

組建「自然資源部」的來龍去脈

黃昕：當你動筆，成敗已定——來自IEEE評審專家的體會與思考


這個遙感學科的排名比較全，值得分享！

院士論壇| 高俊：圖到用時方恨少, 重繪河山待後生——《測繪學報》60年紀念與前瞻

武漢大學老師推出最美賞櫻專題地圖

學術前沿| 李廣云：精密工程測量技術及其發展

SCI收錄的中文期刊有哪些？

權威 | 專業 | 學術 | 前沿

微信投稿郵箱 | song_qi_fan@163.com

微信公眾號中搜索「測繪學報」，關注我們，長按上圖二維碼，關注學術前沿動態。

歡迎加入《測繪學報》作者QQ群： 297834524

進群請備註：姓名+單位+稿件編號



相關焦點

  • 基於向量空間的知識圖譜查詢及結果解釋
    它的主要內容包括五個方面，分別是知識圖譜及SPARQL查詢、查詢空集問題、知識圖譜表示學習、基於向量空間的近似查詢和實際應用。知識圖譜及SPARQL查詢知識圖譜是機器生成並為機器服務的，服務對象不是人類，需要追求機器可理解的東西。
  • 分布式SQL查詢引擎:Presto
    Presto是由Facebook開發的一個分布式SQL查詢引擎，為進行大數據實時查詢計算而專門設計開發的產品。它解決了Hive的MapReduce模型太慢，不能通過BI或Dashboards直接展現HDFS數據等問題。Presto適用於交互式分析查詢，數據量支持GB到PB字節級別。它可以用來完成聯機分析處理（OLAP）任務，如數據分析、聚合大量數據和生成報告等。
  • Presto:分布式 SQL 查詢引擎
    負責具體的查詢計算和數據讀寫Discovery Server　負責發現集群的各個節點，用於節點間心跳監控一般 Discovery Server 混布在 Coordinator 節點上，也支持單獨部署數據源Connector　負責訪問不同的數據源，相當於訪問資料庫的驅動Catalog　負責記錄 Schema 信息和 DataSource
  • 這100篇論文,使您成大數據高手……
    文件系統層由於文件系統層關注的焦點，開始向「低延時處理」方向轉移，所以傳統基於磁碟存儲的文件系統，也開始向基於內存計算的文件系統轉變 —— 這樣做，會大大降低I / O操作和磁碟序列化帶來的訪問開銷。Tachyon【21】–是一個高容錯的分布式內存文件系統，其設計的核心內涵是，要滿足當下「低延遲」的數據處理要求（註：Tachyon是在內存中處理緩存文件，允許文件以訪問內存的速度在集群框架中進行可靠的共享，類似於Spark。Tachyon的吞吐量比HDFS高出100倍。
  • ACL2016最佳論文:通過整合基於路徑的方法和分布式的方法,改善詞對...
    聯合編譯：章敏，高斐，陳圳摘要在自然語言處理（NLP）中，理清詞對關係是一項的關鍵任務 ，在一份使用兩種互補方法的文獻中也強調這一點。分雖然這些方法似乎是互補的，但整合他們的工作卻不少。在本文中，我們提出了HypeNET，一種結合基於路徑和分布式的方法，用於上下文語境檢測。受到最近關係分層方面研究的啟發，我們使用了一個長短期的記憶（LSTM）網絡，進行依賴路徑的編碼。為了給我們的網絡創造足夠的訓練數據，，我們遵循了以前的方法，即構建一個基於知識資源的數據集。
  • Tachyon:Spark生態系統中的分布式內存文件系統
    本質上， Tachyon是個分布式的內存文件系統， 它在減輕Spark內存壓力的同時，也賦予了Spark內存快速大量數據讀寫的能力。Tachyon把內存存儲的功能從Spark中分離出來， 使Spark可以更專注計算的本身， 以求通過更細的分工達到更高的執行效率。
  • 讀完這100篇論文,你就能成大數據高手!
    文件系統層由於文件系統層關注的焦點，開始向「低延時處理」方向轉移，所以傳統基於磁碟存儲的文件系統，也開始向基於內存計算的文件系統轉變——這樣做，會大大降低I / O操作和磁碟序列化帶來的訪問開銷。Tachyon【21】–是一個高容錯的分布式內存文件系統，其設計的核心內涵是，要滿足當下「低延遲」的數據處理要求（註：Tachyon是在內存中處理緩存文件，允許文件以訪問內存的速度在集群框架中進行可靠的共享，類似於Spark。Tachyon的吞吐量比HDFS高出100倍。
  • PayPal高級總監:讀完這100篇論文,你就能成大數據高手!
    文件系統層由於文件系統層關注的焦點，開始向「低延時處理」方向轉移，所以傳統基於磁碟存儲的文件系統，也開始向基於內存計算的文件系統轉變 —— 這樣做，會大大降低I / O操作和磁碟序列化帶來的訪問開銷。Tachyon【21】–是一個高容錯的分布式內存文件系統，其設計的核心內涵是，要滿足當下「低延遲」的數據處理要求（註：Tachyon是在內存中處理緩存文件，允許文件以訪問內存的速度在集群框架中進行可靠的共享，類似於Spark。Tachyon的吞吐量比HDFS高出100倍。
  • Oracle資料庫中的內存計算那點事
    基於內存計算的另外一個問題始終困擾著業內人士——內存有限而數據相對無限：單一伺服器的內存遠遠不足以存儲需要處理的數據，頻繁的內存交換消耗太多資源，用戶不得不使用手工分庫的方式把數據分散到多個伺服器上來處理，這又帶來了管理、開發複雜，擴展性差等諸多問題。
  • 大數據核心技術介紹:大數據處理技術
    大數據處理，其實最主要的支撐技術就是分布式和並行計算、大數據云以及大數據內存計算。 大數據的分布式和並行計算 分布式計算，將複雜任務分解成子任務、同時執行單獨子任務的方法，所以稱之為分布式並行計算
  • 面向大數據的分布式緩存設計
    設計的面向大數據應用的分布式緩存系統，在讀寫流程、I/O事件驅動並發模型及元數據模型等方面進行了合理設計與優化，並使用fio工具測試了順序寫、隨機寫、順序讀及隨機讀場景下的吞吐率與IOPS等性能指標，驗證了該分布式緩存系統的高性能優勢和應對高並發場景的擴展能力。大數據處理平臺主要由上層的分布式計算組件和底層的分布式存儲系統兩層構成。
  • 機器學習的分布式優化方法
    整個會議一共錄用 34 篇論文。 在本篇提前看中，我們選擇了三篇文章進行詳細分析，以了解機器學習與系統（Machine Learning and Systems）領域最新的研究成果。其中，前兩篇文章屬於經典的機器學習分布式優化方法（通信方式、內存分配方法），第三篇文章則是關於一種新的用於機器學習的具有高度系統性和設備（統計、數據）異質性的分布式方法--聯邦學習。
  • 基於新型存儲的大數據存儲管理
    但目前在傳統計算體系結構下，單臺計算機只能支持每秒150～300幀的低解析度圖像實時異常事件檢測[2,3]。如果要做進一步的目標識別，根據目前的處理技術，性能將下降到每秒16幀左右[4,5]，遠遠不能滿足每秒幾千幀高清圖像的實時處理要求。因此，迫切需要研究能夠滿足大數據高效存儲與實時處理的新型體系結構與新方法。
  • 大規模分布式存儲如何優化?Facebook說自己的方法能把CPU負載降一半
    比如把兩個經常需要同時訪問的數據放在同一個存儲託管伺服器上就能夠提升會用到這些數據的查詢性能。平衡圖分區（balanced graph partitioning）就提供了一種有用的方法來處理任務背後的工作量分配問題。
  • KDD2016論文精品解讀(一)
    然而，CFD模擬通常是計算昂貴，內存要求大、且耗時的迭代過程。CFD的這些缺點，限制了設計空間探索的機會，同時也破滅了互動設計的想法。我們提出了一個通用且靈活的近似模型，用於實時預測基於卷積神經網絡（CNNs）的二維或三維領域中不均勻的穩態層流體。我們探索了幾何表示的替代品和CNNs的網絡體系結構。
  • 用Apache Spark進行大數據處理——第一部分:入門介紹
    Spark特性Spark通過在數據處理過程中成本更低的洗牌（Shuffle）方式，將MapReduce提升到一個更高的層次。利用內存數據存儲和接近實時的處理能力，Spark比其他的大數據處理技術的性能要快很多倍。Spark還支持大數據查詢的延遲計算，這可以幫助優化大數據處理流程中的處理步驟。
  • 百度分布式交互查詢平臺——PINGO架構迭代
    在PINGO之前，百度的大數據查詢作業主要由基於Hive的百度QueryEngine去完成。QueryEngine很好的支持著百度的離線計算任務，可是它對交互式的在線計算任務支持並不好。為了更好的支持交互式任務，我們在大約一年前設計了基於SparkSQL與Tachyon的PINGO的雛形。在過去一年中， 通過跟不同業務的結合，PINGO逐漸的演變成一套成熟高效的交互式查詢系統。
  • AI攢論文指日可待?Transformer生成論文摘要方法已出
    我們還表明這個方法能得到比之前的使用複製機制的方法更抽象的摘要，同時還能得到更高的 rouge 分數。」讀起來怎麼樣？事實上，以上你看到的摘要內容都不是人類完成的，它是由論文中的機器學習模型寫出來的。這是來自 Element AI 的研究者最新公布的研究成果，他們使用了一種類似 GPT 的方法生成了相關研究論文的摘要。
  • 大數據基礎知識:Hadoop分布式系統介紹
    隨著智能化、萬物互聯時代的快速發展，數據量開始暴增，一方面我們需要開始思考如何高效可靠地存儲海量的數據，另一方面我們還需要對這些數據進行分析處理，以獲得更多有價值的信息。這時期我們就需要用到Hadoop了。
  • ICML 2018最佳論文出爐:伯克利、MIT最佳論文,復旦大學榜上有名
    該論文討論的這種在線流算法可以在只有非常小的協方差誤差的情況下，從大型矩陣抽取出最能近似它的小矩陣。.pdf摘要：給定一個 n×d 維的大型的矩陣 A，我們考慮計算一個 l×d 維的概要矩陣（sketch matrix）B，概要矩陣的維度 l 要顯著小於原矩陣 A，但它仍是矩陣 A 優良的近似。