[發(fā)明專利]基于帶序興趣區(qū)域的軌跡查詢的擴(kuò)張搜索擴(kuò)展算法

在審

• 申請(qǐng)?zhí)枺?/td>: 201710659339.6
• 申請(qǐng)日: 2017-08-04
• 公開（公告）號(hào): CN107463672A
• 公開（公告）日: 2017-12-12
• 發(fā)明（設(shè)計(jì)）人: 毛睿;李榮華;陸敏華;王毅;羅秋明;商爍;劉剛
• 申請(qǐng)（專利權(quán)）人: 深圳大學(xué)
• 主分類號(hào): G06F17/30
• 分類號(hào): G06F17/30
• 代理公司: 上海宏京知識(shí)產(chǎn)權(quán)代理事務(wù)所(普通合伙)31297
• 代理人: 王函

1.一種基于帶序興趣區(qū)域的軌跡查詢的擴(kuò)張搜索擴(kuò)展算法，其特征在于，包括如下步驟：

步驟1：初始設(shè)置全局空間密度相關(guān)性下限LB＝0，全局空間密度相關(guān)性上限UB＝+∞；定義空間密度相關(guān)性計(jì)算公式：

C,sd(c,v)=Σpi∈cpi.g·e-sd(p,v)]]>

C,sd(C,τ)=max(21+e-C,sd(C.head,τ.head)-1)+C,sd(C.tail,τ)C,sd(C,τ.tail)]]>

其中，v是軌跡τ上的點(diǎn)，C’_sd(c,v)是查詢區(qū)域c與v之間的空間密度相關(guān)性；C’_sd(C,v)表示查詢區(qū)域集合C與軌跡τ的空間密度相關(guān)性；p_i。g是附屬于p_i的空間對(duì)象的數(shù)量；sd(p,v)代表點(diǎn)p與點(diǎn)v之間的距離；*.head表示列表中第一個(gè)元素，*.tail表示列表中除head之外的所有元素構(gòu)成的列表；

步驟2：從查詢區(qū)域中心中選擇一組查詢?cè)矗?/p>

步驟3：對(duì)每個(gè)查詢?cè)催M(jìn)行Dijkstra擴(kuò)展算法，每次擴(kuò)展距離最小的點(diǎn)；

步驟4：計(jì)算空間密度的上限和下限，更新LB和UB；

步驟5：判斷LB>UB或所有搜索半徑超過ε+p.dist/2是否成立，其中，ε是事先設(shè)置的閾值，p.dist＝max{sd(p,p’),sd(p,p”)}，p’和p”是p的鄰近查詢?cè)矗瑂d(p,p’)代表點(diǎn)p和點(diǎn)p’之間的網(wǎng)絡(luò)距離，sd(p,p”)代表點(diǎn)p和點(diǎn)p”之間的網(wǎng)絡(luò)距離；如成立則網(wǎng)絡(luò)的相鄰查詢?cè)磾U(kuò)展終止，進(jìn)入下一步驟6；如不成立，則回到步驟4；

步驟6：根據(jù)空間密度上限的值對(duì)軌跡進(jìn)行排序；

步驟7：按照軌跡排序進(jìn)一步細(xì)化，返回具有最大空間密度相關(guān)性的軌跡。