[發(fā)明專利]獲取路網(wǎng)上單反向最遠(yuǎn)鄰居的層次分區(qū)方法及系統(tǒng)

有效

• 申請(qǐng)?zhí)枺?/td>: 201310279130.9
• 申請(qǐng)日: 2013-07-04
• 公開（公告）號(hào): CN103365983A
• 公開（公告）日: 2013-10-23
• 發(fā)明（設(shè)計(jì)）人: 姚斌;邢昊原;李飛飛
• 申請(qǐng)（專利權(quán)）人: 上海交通大學(xué)
• 主分類號(hào): G06F17/30
• 分類號(hào): G06F17/30
• 代理公司: 上海思微知識(shí)產(chǎn)權(quán)代理事務(wù)所(普通合伙) 31237
• 代理人: 鄭瑋

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

本發(fā)明涉及一種獲取路網(wǎng)上單反向最遠(yuǎn)鄰居的層次分區(qū)方法及系統(tǒng)。

背景技術(shù)

空間數(shù)據(jù)庫(spaitial?database)是指提供了空間數(shù)據(jù)類型(spatial?database?type,SDT)和相應(yīng)實(shí)現(xiàn)支持的數(shù)據(jù)庫（參見文獻(xiàn)1：R?H.An?introduction?to?spatial?database?systems[J].The?VLDB?Journal,1994,3(4):357-399）。隨著移動(dòng)計(jì)算與云計(jì)算的日益發(fā)展，空間相關(guān)算法的應(yīng)用日益增多。距離查詢(proximity?query)包括最近鄰居(Nearest?Neighbor)查詢、反向最近鄰居(Reverse?Nearest?Neighbor)查詢、反向最遠(yuǎn)鄰居查詢(Reverse?Furthest?Neighbor)等，是空間數(shù)據(jù)庫查詢中最常見的類型之一。本發(fā)明關(guān)注在路網(wǎng)(road?network)數(shù)據(jù)庫上的反向最遠(yuǎn)鄰居(reverse?furthest?neighbor,RFN)查詢，即給定一組路網(wǎng)上的數(shù)據(jù)集P與查詢集Q，我們希望求取P中所有與Q相比距離q更遠(yuǎn)的點(diǎn)。該問題根據(jù)P與Q是否相同可劃分為單反向最遠(yuǎn)鄰與復(fù)反向最遠(yuǎn)鄰問題。該問題在實(shí)踐中擁有重大意義，例如在開設(shè)新的商店時(shí)，我們希望得知受某一競爭對(duì)手影響最小的點(diǎn)。如果我們將不同地點(diǎn)之間的影響程度以帶權(quán)的邊表示，這一問題就相當(dāng)于在路網(wǎng)上求取以現(xiàn)有商戶地點(diǎn)為查詢點(diǎn)的單反向最遠(yuǎn)鄰居問題。進(jìn)一步說，尋找一個(gè)受現(xiàn)有的所有競爭對(duì)手相對(duì)影響最小的點(diǎn)，可以轉(zhuǎn)化為目標(biāo)點(diǎn)在這一路網(wǎng)上求以競爭對(duì)手地點(diǎn)為查詢集Q的復(fù)反向最遠(yuǎn)鄰居數(shù)量的最大化問題。

據(jù)我們所知，目前對(duì)于路網(wǎng)上單反向最遠(yuǎn)鄰問題所提出的唯一解決方案是Tran等人對(duì)于路網(wǎng)上反向最遠(yuǎn)鄰的研究，他們以路網(wǎng)中的每一個(gè)興趣點(diǎn)為生成點(diǎn)預(yù)處理建立Voronoi分區(qū)，然后使用分區(qū)的鄰接性質(zhì)對(duì)分區(qū)進(jìn)行遍歷，以枚舉查詢點(diǎn)可能的反向最遠(yuǎn)鄰居（reverse?furthest?neighbor）。但這一方法在路網(wǎng)中興趣點(diǎn)數(shù)量大時(shí)，將與暴力算法沒有本質(zhì)區(qū)別。而對(duì)于復(fù)反向最遠(yuǎn)鄰問題目前尚無有關(guān)解決方案。

在其他相關(guān)研究方面，最引人注意的是最近鄰居(nearest?neighbor)問題（參見文獻(xiàn)2，文獻(xiàn)3：Hjaltason?G?R,Samet?H.Distance?browsing?in?spatial?databases[J].ACM?Transactions?on?Database?Systems(TODS),1999,24(2):265-318，文獻(xiàn)4：Berchtold?S,C,Keim?D?A,etc.A?cost?model?for?nearest?neighbor?search?in?high-dimensional?data?space[A].In?Proceedings?of?the?sixteenth?ACM?SIGACT-SIGMOD-SIGART?symposium?on?Principles?of?database?systems[C],1997:78-86，文獻(xiàn)5，文獻(xiàn)6：Jagadish?H,Ooi?B?C,Tan?K-L,etc.iDistance:An?adaptive?B+-tree?based?indexing?method?for?nearest?neighbor?search[J].ACM?Transactions?on?Database?Systems(TODS),2005,30(2):364-397，文獻(xiàn)7：Tao?Y,Papadias?D,Shen?Q.Continuous?nearest?neighbor?search[A].In?Proceedings?of?the28th?international?conference?on?Very?Large?Data?Bases[C],2002:287-29）與反向最近鄰居（參見文獻(xiàn)8：Korn?F,Muthukrishnan?S.Influence?sets?based?on?reverse?nearest?neighbor?queries[J].ACM?SIGMOD?Record,2000,29(2):201-212，文獻(xiàn)9：Singh?A,Ferhatosmanoglu?H,Tosun?AHigh?dimensional?reverse?nearest?neighbor?queries[A].In?Proceedings?of?the?twelfth?international?conference?on?Information?and?knowledge?management[C],2003:91-98，文獻(xiàn)10：Tao?Y,Papadias?D,Lian?X.Reverse?kNN?search?in?arbitrary?dimensionality[A].In?Proceedings?of?the?Thirtieth?international?conference?on?Very?large?data?bases-Volume30[C],2004:744-755，文獻(xiàn)11：Achtert?E,C,P,etc.Efficient?reverse?k-nearest?neighbor?search?in?arbitrary?metric?spaces[A].In?Proceedings?of?the2006ACM?SIGMOD?international?conference?on?Management?of?data[C],2006:515-526，文獻(xiàn)12：Sankaranarayanan?J,Samet?H.Distance?oracles?for?spatial?networks[A].In?Data?Engineering,2009.ICDE′09.IEEE25th?International?Conference?on[C],2009:652-663）問題。以R-Tree（參見文獻(xiàn)13：Guttman?A.R-trees:a?dynamic?index?structure?for?spatial?searching[M].ACM,1984）為基礎(chǔ)的深度（參見文獻(xiàn)2：Roussopoulos?N,Kelley?S,Vincent?F.Nearest?neighbor?queries[A].In1995:71-79）與廣度（參見文獻(xiàn)5：Cui?B,Ooi?B?C,Su?J,etc.Contorting?high?dimensional?data?for?efficient?main?memory?KNN?processing[A].In?Proceedings?of?the2003ACM?SIGMOD?international?conference?on?Management?of?data[C],2003:479-490）優(yōu)先搜索、增量歐氏限制(Incremental?Euclidean?Restriction)、增量網(wǎng)絡(luò)擴(kuò)展(Invremental?Network?Expansion，參見文獻(xiàn)14：Papadias?D,Zhang?J,Mamoulis?N,etc.Query?processing?in?spatial?network?databases[A].In2003:802-813)與Voronoi圖相關(guān)的技術(shù)（參見文獻(xiàn)8～12）被廣泛用于解決歐氏空間(Euclidean?space)與路網(wǎng)上的相應(yīng)問題，但由于反向最遠(yuǎn)鄰居問題不具有最近鄰居問題所具有的本地性特點(diǎn)，這些解決方案難以應(yīng)用在本發(fā)明所解決的問題上。