[發(fā)明專利]區(qū)間樹及查詢過程可視化方法

在審

• 申請?zhí)枺?/td>: 201710033022.1
• 申請日: 2017-01-13
• 公開（公告）號: CN108304419A
• 公開（公告）日: 2018-07-20
• 發(fā)明（設(shè)計(jì)）人: 許建秋;周劍剛
• 申請（專利權(quán)）人: 南京航空航天大學(xué)
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 暫無信息
• 代理人: 暫無信息

本發(fā)明提供了區(qū)間樹及查詢過程可視化方法，應(yīng)用于數(shù)據(jù)庫領(lǐng)域，在可擴(kuò)充移動對象數(shù)據(jù)庫SECONDO中對區(qū)間樹及區(qū)間查詢過程進(jìn)行可視化。本發(fā)明所述的區(qū)間樹可視化，是將構(gòu)造的區(qū)間樹將每一個區(qū)間結(jié)點(diǎn)的中間值以及結(jié)點(diǎn)所在的高度按一定規(guī)則映射成一個坐標(biāo)點(diǎn)，每個結(jié)點(diǎn)和孩子之間都映射一條線，以此對區(qū)間樹進(jìn)行可視化。對于查詢過程可視化，是根據(jù)要查詢的值從跟結(jié)點(diǎn)開始查詢，將查詢經(jīng)過的每一個結(jié)點(diǎn)按上述同樣的方式映射成坐標(biāo)，以此對查詢過程進(jìn)行可視化。

一、技術(shù)領(lǐng)域

本發(fā)明是數(shù)據(jù)庫領(lǐng)域，用于實(shí)現(xiàn)在可擴(kuò)充移動對象數(shù)據(jù)庫SECONDO中區(qū)間樹以及查詢過程的可視化。

二、背景技術(shù)

隨著應(yīng)用發(fā)展，數(shù)據(jù)存儲對象的數(shù)據(jù)變得越來越復(fù)雜而且龐大，如交通流量監(jiān)控這些應(yīng)用。在這些應(yīng)用中，數(shù)據(jù)的產(chǎn)生非常的快速，很容易即可產(chǎn)生PB級的數(shù)據(jù)。面對如此龐大的數(shù)據(jù)，如何進(jìn)行很好的存儲和查詢是我們能不能高效的利用這些數(shù)據(jù)的至關(guān)重要的一部分。而在此過程中，一個可視化的方法對于直觀的理解有著非常重要的幫助。

在時空數(shù)據(jù)庫中，區(qū)間樹用來有效的組織表示為軸平行線段的區(qū)間，每個區(qū)間包含一個開始和結(jié)束端點(diǎn)。當(dāng)有大量的各不相同的區(qū)間，就需要構(gòu)造一顆區(qū)間樹，以便進(jìn)行高效的存儲和查詢。對于區(qū)間樹的構(gòu)造使用的方法是：首先找到所有區(qū)間的中間點(diǎn)，然后所有與這個中間點(diǎn)相交的區(qū)間放在一個節(jié)點(diǎn)，剩下的在中間點(diǎn)左側(cè)和右側(cè)的區(qū)間再重復(fù)上述步驟；每個節(jié)點(diǎn)僅存放與中間點(diǎn)相交的區(qū)間，左邊的區(qū)間就是其左孩子，右邊的區(qū)間就是其右孩子。這種方法構(gòu)造出的樹形結(jié)構(gòu)當(dāng)節(jié)點(diǎn)非常多時它的高度值就非常大，同時也非常的復(fù)雜，為了可以方便的查看區(qū)間樹，就需要一種可視化的方法將區(qū)間樹形狀顯示出來，同時可以做到查詢給定的一個點(diǎn)被哪些區(qū)間覆蓋的top-k個區(qū)間，同時將查詢經(jīng)過的結(jié)點(diǎn)可視化。

三、發(fā)明內(nèi)容

【發(fā)明目的】

為了圖形化顯示大規(guī)模數(shù)據(jù)的區(qū)間樹結(jié)構(gòu)及數(shù)據(jù)分布，以及圖形化顯示查詢過程來幫助分析查詢算法過程及其正確性，本發(fā)明實(shí)現(xiàn)了在可擴(kuò)充移動對象數(shù)據(jù)庫SECONDO中提供包含區(qū)間樹可視化、覆蓋區(qū)間top-k查詢過程可視化，直觀顯示區(qū)間樹及其查詢過程的方法。

【技術(shù)方案】

本發(fā)明所述的區(qū)間樹及查詢過程可視化方法是分別實(shí)現(xiàn)的，區(qū)間樹可視化是將已經(jīng)建好的區(qū)間樹在可擴(kuò)充移動對象數(shù)據(jù)庫SECONDO中通過GUI顯示出來；覆蓋區(qū)間top-k查詢可視化是對區(qū)間樹查詢出覆蓋點(diǎn)的前k個權(quán)值最大的區(qū)間，并將查詢經(jīng)過的結(jié)點(diǎn)顯示出來。主要步驟如下：

(1)區(qū)間生成和建樹；

本發(fā)明考慮給定數(shù)據(jù)空間情況，為了實(shí)驗(yàn)需要，需提前生成數(shù)據(jù)區(qū)間。區(qū)間是系統(tǒng)自動生成的，但需給定一些區(qū)間參數(shù)：1)區(qū)間最小值和最大值，這個是為了限定區(qū)間值可控，在本發(fā)明中，我們規(guī)定的是區(qū)間最小值是1，最大值是100000；2)區(qū)間最大長度和區(qū)間權(quán)值，最大長度是用來規(guī)定每一個區(qū)間的最大長度，本發(fā)明中規(guī)定區(qū)間最大長度為1000；3)區(qū)間數(shù)量，本實(shí)驗(yàn)中規(guī)定的區(qū)間數(shù)量是2000000。以上值僅是為了實(shí)驗(yàn)需要，可以根據(jù)實(shí)驗(yàn)情況隨時調(diào)整。然后根據(jù)生成的區(qū)間，建立一顆區(qū)間樹，并保持樹的平衡。

(2)區(qū)間樹可視化；

對于已經(jīng)生成的區(qū)間樹，根據(jù)其樹狀結(jié)構(gòu)將其在可擴(kuò)充移動對象數(shù)據(jù)庫SECONDO中的GUI界面進(jìn)行顯示。對于一顆樹，可視化的基本方案就是將其用點(diǎn)和線畫出來：遍歷區(qū)間樹，將其每一個結(jié)點(diǎn)就映射為GUI中的一個點(diǎn)，點(diǎn)的橫坐標(biāo)是所在結(jié)點(diǎn)的中間值x，縱坐標(biāo)是結(jié)點(diǎn)的高度h；結(jié)點(diǎn)如果有左孩子或者右孩子，就將結(jié)點(diǎn)和它的左孩子(右孩子)之間連一條線，線的端點(diǎn)就是跟結(jié)點(diǎn)以及孩子結(jié)點(diǎn)。以此為方案可視化一棵樹。

(3)Top-k查詢可視化；