[發(fā)明專利]一種障礙空間中連續(xù)范圍Skyline查詢

在審

• 申請(qǐng)?zhí)枺?/td>: 202111001293.1
• 申請(qǐng)日: 2021-08-30
• 公開（公告）號(hào): CN113688331A
• 公開（公告）日: 2021-11-23
• 發(fā)明（設(shè)計(jì)）人: 王冠群;李松;張麗平
• 申請(qǐng)（專利權(quán)）人: 哈爾濱理工大學(xué)
• 主分類號(hào): G06F16/9537
• 分類號(hào): G06F16/9537
• 代理公司: 暫無信息
• 代理人: 暫無信息

本發(fā)明提出一種障礙空間中連續(xù)范圍Skyline查詢方法，應(yīng)用于數(shù)據(jù)庫領(lǐng)域。本發(fā)明提出了基于事件的增量處理方法，首先根據(jù)靜態(tài)Skyline點(diǎn)約剪數(shù)據(jù)集，減少計(jì)算開銷，接著根據(jù)障礙空間中查詢點(diǎn)移動(dòng)的特點(diǎn)構(gòu)建距離相交模型，最后根據(jù)查詢點(diǎn)和其他數(shù)據(jù)點(diǎn)距離交叉時(shí)刻來更新結(jié)果集。此外，基于事件的剪枝策略，有效提高了效率。

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

本發(fā)明屬于數(shù)據(jù)管理和多屬性數(shù)據(jù)查詢技術(shù)領(lǐng)域，更具體地，涉及一種基于障礙空間的移動(dòng)用戶的連續(xù)范圍Skyline查詢。

背景技術(shù)

隨著個(gè)人通信技術(shù)和全球定位系統(tǒng)的快速發(fā)展，基于位置的服務(wù)越來越受到人們的重視。在移動(dòng)數(shù)據(jù)庫和空間數(shù)據(jù)庫中，Skyline查詢是最常見的查詢之一。Skyline查詢是從多種維度屬性的元祖集合中返回最具有優(yōu)勢(shì)的元祖，是多目標(biāo)決策的重要手段之一。給定兩個(gè)n維數(shù)據(jù)點(diǎn)p₁和p₂，倘若p₁在任意維度上的屬性都不比p₂差，那么p₁支配p₂。

最近幾年,對(duì)Skyline查詢的研究大體上可以分為4類。

(1)單Skyline查詢處理算法，該類算法假定所有的Skyline對(duì)象都處在某一個(gè)特定的D維空間中，返回的結(jié)果集合只有1個(gè)。根據(jù)查詢過程中是否借助索引，單Skyline查詢處理算法又分為兩類：不帶索引算法和帶索引算法，前者假定沒有任何索引存在，通過掃描整個(gè)數(shù)據(jù)集(至少1次)來返回Skyline查詢的結(jié)果，后者通過引入適當(dāng)?shù)乃饕Y(jié)構(gòu)，如R-樹，來提高查詢處理的效率。

(2)多Skyline查詢處理算法。針對(duì)現(xiàn)實(shí)生活中不同的用戶可能有不同的興趣和偏好，需要在不同的子空間中處理Skyline查詢的需求，數(shù)據(jù)倉庫和OLAP領(lǐng)域的研究者對(duì)在不同子空間上進(jìn)行Skyline查詢的研究產(chǎn)生了濃厚的興趣，提出了SKYCUBE的概念SKYCUBE借用傳統(tǒng)的Data Cube的多維層次結(jié)構(gòu),提出了有效的同時(shí)計(jì)算多個(gè)Skyline 查詢的思想。該類算法主要包含針對(duì)SKYCUBE的計(jì)算、維護(hù)和壓縮等。

(3)不同應(yīng)用環(huán)境下的Skyline查詢處理.主要包括Web信息系統(tǒng)中的Skyline查詢處理、P2P網(wǎng)絡(luò)環(huán)境下的Skyline查詢處理、數(shù)據(jù)流環(huán)境下的Skyline 查詢處理、移動(dòng)的公路網(wǎng)絡(luò)環(huán)境下的Skyline查詢處理等。

(4)Skyline查詢處理問題的擴(kuò)展。例如，文獻(xiàn)中首次擴(kuò)展了空間數(shù)據(jù)庫中不同數(shù)據(jù)點(diǎn)之間的控制關(guān)系的概念，將其用于經(jīng)濟(jì)學(xué)框架下的商業(yè)分析，提出了控制關(guān)系分析的概念，文獻(xiàn)針對(duì)高維空間下出現(xiàn)在Skyline查詢結(jié)果中的點(diǎn)非常多，從而導(dǎo)致該結(jié)果在很多時(shí)候?qū)τ脩羰ヒ饬x的問題，提出了k-Dominant的概念。

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

本發(fā)明的目的在于提供一種障礙空間中連續(xù)范圍Skyline查詢。

步驟1：計(jì)算數(shù)據(jù)點(diǎn)集中靜態(tài)Skyline點(diǎn)，并求出距離查詢點(diǎn)最遠(yuǎn)的Skyline點(diǎn)，若查詢點(diǎn)和Skyline點(diǎn)是可視的，則以查詢點(diǎn)為圓心，以查詢點(diǎn)和Skyline點(diǎn)的歐式距離為半徑做圓，若查詢點(diǎn)和Skyline點(diǎn)是不可視的，則查詢點(diǎn)到Skyline點(diǎn)的障礙距離為半徑做圓，剪枝圓外的數(shù)據(jù)點(diǎn)，這樣可以有效避免重復(fù)計(jì)算；

步驟2：根據(jù)查詢點(diǎn)和興趣點(diǎn)距離的交叉時(shí)刻來構(gòu)建模型，其中不同的興趣點(diǎn)在距離上會(huì)相交；

步驟3：根據(jù)興趣點(diǎn)之間的靜態(tài)屬性來判斷是否滿足剪枝策略。如果滿足，無需構(gòu)建event事件，否則構(gòu)建event事件；

步驟4：構(gòu)建event事件，將相交時(shí)間，前繼節(jié)點(diǎn)和后繼節(jié)點(diǎn)插入event中，并表明該事件所屬的類型；