[發明專利]查詢最小距離和位置的動態監控方法及系統

有效

• 申請號: 201310280203.6
• 申請日: 2013-07-04
• 公開（公告）號: CN103336824A
• 公開（公告）日: 2013-10-02
• 發明（設計）人: 姚斌;吳亦凡;李飛飛;肖小奎
• 申請（專利權）人: 上海交通大學
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 上海思微知識產權代理事務所(普通合伙) 31237
• 代理人: 鄭瑋

技術領域

本發明涉及一種查詢最小距離和位置的動態監控方法及系統。

背景技術

在過去幾年中，有很多工作研究一類在存在客戶點集合的情況下的“設施放置問題”（參見文獻8：Farahani,R.Z.,Hekmatfar,M.:Facility?Location:Concepts,Models,Algorithms?and?Case?Studies,1st?edn.Physica-Verlag?HD(2009),文獻15：Nickel,S.,Puerto,J.:Location?Theory:A?Unified?Approach,1st?edn.Springer(2005)）。在最普遍的情況下，問題包含：（1）一個客戶點的集合C和一個設施點候選集合P，并（2）在P中查詢k個新設施點的位置從而滿足一個事先定義的最佳條件。這類問題在k是常數的情況下存在多項式時間內的算法，在k是一般變量的情況下是NP-hard問題（參見文獻8和15），已經存在的工作主要研究其近似算法。

最佳位置查詢問題可以被看做設施放置問題的一個變種，首先P是一個無限集合；然后通常k=1，也就是說只需要為新建一個設施點來選取位置；最后通常事先已經擁有了一個設施點集合F。以上這些是最佳位置查詢問題相對于一般的“設施放置問題”的不同點。

之前的最佳位置查詢問題的研究工作（參見文獻2：Cabello,S.,J.M.,Langerman,S.,Seara,C.,Ventura,I.:Reverse?facility?location?problems.In:CCCG,pp.68–71(2005),文獻6：Du,Y.,Zhang,D.,Xia,T.:The?optimal-location?query.In:SSTD,pp.163–180(2005),文獻21：Wong,R.C.W.,¨Ozsu,T.,Yu,P.S.,Fu,A.W.C.,Liu,L.:Efficient?method?for?maximizing?bichromatic?reverse?nearest?neighbor.PVLDB2(1),1126–1137(2009),文獻24：Zhang,D.,Du,Y.,Xia,T.,Tao,Y.:Progressive?computation?of?the?min-dist?optimal-location?query.In:VLDB,pp.643–654(2006)）中考慮的是設施點和客戶點之間在Lp空間中的距離。其中Cabello等人（參見文獻2）和Wong等人（參見文獻21）的研究是基于L2空間的，而Du等人（參見文獻6）和Zhang等人（參見文獻24）的研究是基于L1空間的。這些工作并沒有研究最佳位置查詢問題在路網中的情況。

現有的研究工作中包括另外兩種與設施點的位置選取有關的問題：單設施點查詢問題（參見文獻8和15）以及設施點實時建立問題（參見文獻9：Fotakis,D.:Incremental?algorithms?for?facility?location?and?kmedian.Theor.Comput.Sci.361(2-3),275–313(2006)，文獻13：Meyerson,A.:Online?facility?location.In:FOCS,pp.426–431(2001)），這兩種問題研究內容與最佳位置查詢問題類似但是有所不同。單設施點查詢問題研究的是，給定一個客戶點的集合，尋找一個設施建立點從而滿足一個最佳條件，在這個問題里，輸入數據中沒有已經建立的設施點集合，然而在最佳位置查詢問題里，需要考慮一個已有的設施點的集合。設施點實時建立問題研究的是，隨著客戶點的不斷增加，實時選取位置建立新的設施點來滿足一個給定的優化條件，與最佳位置查詢問題相似的是，這類問題在尋找新的設施點時，也考慮已有的設施點集合，然而[9]和[13]所采用的方法并不能解決最佳位置查詢問題，這是因為在設施點實時建立問題中，建立新設施點的候選地點是一個有限的集合，但是在最佳位置查詢問題中，建立新設施點的候選地點是一個無限的集合，例如Lp空間中的所有地點或是路網中的所有邊上的所有地點的集合。在我們之前的研究工作中我們提出了靜態一次查詢路網中最佳位置的方法（參見文獻22：Xiao,X.,Yao,B.,Li,F.:Optimal?location?queries?in?road?network?databases.In:ICDE,pp.804–815(2011)），與那篇文章相比，我們的發明提出了新的動態維護路網中最佳位置的解決方案，并為三個不同的最佳位置查詢問題設計了具體的實現方法。