監測運動對象的方法和結構的製作方法

2023-12-04 21:50:36

專利名稱：監測運動對象的方法和結構的製作方法
技術領域：
本發明總體上涉及在移動環境中提供了解位置或者與位置相關的服務。更具體地，一種查詢索引系統和方法允許本發明的用戶定期地、增量式地定位在連續範圍查詢邊界之內的所有運動對象。「增量式地」可以被定義為通過根據對於查詢邊界而言相對於最後位置的相對運動來過濾出一個運動對象子集，來跳過某些查詢評估。
背景技術：
最近已經有可能提供了解位置(location-aware)或者與位置相關(location-dependent)的服務並且正在出現這樣的服務，這是由於移動計算和位置檢測技術的進步，比如全球定位系統(GPS)。由於增加了對許多感興趣的對象比如人、計程車、救護車、膝上型電腦、飛機、火車、貨船等的位置的了解，這些服務可以提高生活質量。基本上，可以為任何運動的對象提供「位置意識」(定位)(locationawareness)，對其監測。
對於提供了解位置的服務來說，其中一個最為基本的技術問題是進行監測，以對定位查詢邊界內的運動對象的連續範圍查詢提供迅速的回答。使用容易獲得的連續範圍查詢的結果，可以提供各種了解位置的服務。例如，使用連續範圍查詢(比如「尋找當前離特定位置五個街區以內的所有計程車」)的結果，計程車公司可以將一輛計程車分派給在該特定位置的一個乘客。之所以將範圍查詢(range query)說成是「連續的」(continual)，是因為在對象連續地四處運動的同時，對範圍查詢反覆地進行評估，以提供最新的應答。每一個範圍查詢規定一個區域的邊界。
為了監測對大量運動對象的連續範圍查詢，通常需要一種有效的索引方式。通常有兩種不同的索引方法。一種是對運動對象進行索引，另一種是對範圍查詢進行索引。
為了對運動對象建立索引，已經進行了各種嘗試。比如提出了以下方法-″Indexing moving objects，″by P.K.Agarwal et al.，inProceedings oJACM Symposium on Principles of Database Systems，2000；-″On indexing mobile objects，″by G.Kollios et al.，inProceedings oJACM Symposium on Principles of Database Systems，1999；-″Novel app roaches to the indexing of moving objecttrajectories，″by D.Pfoser et al.，in Proceedings of Very Large DataBases，2000；以及-″Indexing the positions of continuously moving objects，″by S.Saltenis et al.，in Proceedings oJACMSIGMOD，2000。
但是，因為對象可以以不可預期的速度和方向連續運動，非常難以對運動對象維護一個有效的索引。對象位置的變化要求對對象索引予以更新，這極大地降低了其性能。結果，通常對對象的運動速度或者方向進行某種約束，這極大地限制了對象索引的可應用性。
相反，對範圍查詢建立索引更為有效，這是因為連續範圍查詢的變化不那麼頻繁。使用查詢索引，監測連續範圍查詢的問題就變成了這樣給定一組範圍查詢和一組運動對象，連續地測定位於每一個範圍查詢的邊界之內的對象的集合。
使用查詢索引來快速地檢索出覆蓋給定對象的所有範圍查詢。通過識別每一個範圍查詢所覆蓋的所有對象(將它們的最後位置考慮在內)，定期重新評估所有的範圍查詢。為了使結果有用，兩個相繼的重新評估之間的時間段必須短。結果，進行查詢重新評估的時間必須儘可能短。另外，重要的是，查詢索引方法可以利用對象位置的增量式變化，因為某些對象可能自上次重新評估以來沒有運動出某個查詢的邊界。本發明公開了一種用於監測對運動對象的連續範圍查詢的有效的查詢索引系統和方法。
直到最近才開始在運動對象環境中使用查詢索引。在″Queryindexing and velocity constrained indexingscalable techniques forcontinuous queries on moving objects，″IEEE Transactions onComputers，511124-1140，Oct.2002中，S.Prabhakar等人提出了一種使用R樹的查詢索引方法。但是，為了避免過多的位置更新，對每一個移動對象定義了一個安全區。可惜的是，確定安全區需要高強度的計算。另外，為了計算安全區，對運動對象的最大速率施加了約束。
在″Efficient evaluation of continuous range queries on movingobjects，″Proceedings of 13thInternational Conference on Database andExpert Systems Applications，2002中，D.V.Kalashnikov等人提出了一種基於網格單元(grid cell)的查詢索引方法，其中表明了該方法勝過基於R樹的查詢索引。該方法中，監測區域被劃分為互不重疊的網格單元。每一個單元包含兩個列表完全的和部分的。完全列表保存完全覆蓋該單元的查詢的ID，而部分列表維護與該單元部分交叉的查詢的ID。
但是，需要使用部分列表是一個重大缺陷。一個對象在一個單元內部的事實並不意味著它在保存在該單元的部分列表中的查詢的邊界之內。這迫使連續地比較對象位置與查詢邊界。結果，不能利用對象位置的增量式變化。即使對象沒有運動到單元外面去，仍然需要對保存在部分列表中的所有查詢進行邊界比較。
結果，已經認識到需要一種更好的更有效的查詢索引方法，這種方法應該(1)對對象的運動速度或者方向沒有任何限制；並且(2)可以利用對象位置的增量式變化。
本領域的普通技術人員知道，對於判定匹配(predicate matching)(例如，E.Hanson et al.，″Selection predicate indexing for activedatabases using interval skip lists，″Information Systems，21(3)269-298，1996)以及公開/註冊(pub/sub)(例如M.K.Aguileraet al.，″Matching events in a content-based subscription system，″Proceedings of Symposium on Principles of Distributed Computing，1999；F.Fabret et al，″Filtering algorithms and implementation forvery fast publish/subscribe systems，″Proceedings of the ACMSIGMOD，2001)上下文中的有效匹配事件，已經提出過各種查詢索引方法。
但是，這些查詢索引方法多數基於相等性判定(equalitypredicates)，而不是範圍判定(range predicate)。因此，它們不能一般地應用於對運動對象的連續範圍查詢的評估。
本領域普通技術人員還知道，儘管範圍查詢可以被當作空間對象比如矩形來處理，但是傳統的空間索引方法，比如R樹(例如A.Guttman，″R-treesA dynamic index structure for spatial searching，″Proceedings of ACM SIGMOD，1984；V.Gaede et al.，″Multidimensional access methods，″ACM Computing Surveys，30(2)170-231，1998)，對於監測運動對象來說沒有效，因為它們大多是基於盤形的(disk-based)索引方法。
它們通常太慢，因而不能有效地監測對大量的運動對象的連續範圍查詢。另外，當連續查詢的範圍開始相互重疊時，R樹的性能就迅速退化(V.Gaede et al.，″Multidimensional access methods，″ACMComputing Surveys，30(2)170-231，1998；E.Hanson et al.，″Selectionpredicate indexing for active databases using interval skip lists，″Information Systems，21(3)269-298，1996)。

發明內容
鑑於傳統系統的前述問題和缺陷，本發明的一個典型特徵是提供一種查詢索引結構(和方法)，允許本發明的用戶定期地和增量式地定位在連續範圍查詢的邊界之內的所有運動對象。在這裡的上下文中，「增量式地」的意思是，根據相對於查詢邊界來說自上次位置以來的相對運動，過濾出運動對象的一個子集，從而跳過某些查詢評估。
因此，本發明的一個典型目的是提供一種用於查詢索引結構(和方法)的結構和方法，允許本發明的用戶定期地和增量式地定位在連續範圍查詢的邊界之內的所有運動對象。
因此，在本發明的第一方面，在這裡描述了一種監測對運動對象的連續查詢的方法和結構。標識一個數字格式的查詢區域。用至少一個瓦片區嚴格覆蓋每一個查詢區域，使得每一個查詢區域被所述至少一個瓦片區完全覆蓋，任何所述至少一個瓦片區沒有任何部分在所述查詢區域之外。
在本發明的第二方面，在這裡描述了一種基於監測對運動對象的連續查詢的服務，包括至少下述之一使用上述方法針對連續查詢提供對運動對象的監測；提供使用所述方法的所述監測的結果；以及利用使用所述方法的所述監測的結果。
在本發明的第三方面，在這裡描述了一種信號承載介質，其有形地實現可由數字處理設備執行的機器可讀指令的程序，該程序執行監測對運動對象的連續查詢的上述方法。


從下面結合附圖對本發明的優選實施例的詳細說明，可以更好地理解前述以及其它典型特徵和優點。
圖1圖示了一種移動環境100的系統框圖，其中，可以對大量的運動對象監測多個連續範圍查詢；圖2圖示了本發明的典型的優選實施例的概要流程圖200；圖3圖示了根據本發明用於查詢索引的虛擬瓦片區的概念300；圖4圖示了嚴格覆蓋401和鬆散覆蓋402斜線區的概念400；圖5和圖6使用矩形條和一個或者多個虛擬瓦片區503-504、602-604(它們當中的一些是相互重疊的)的概念圖示了覆蓋一個範圍查詢501的例子500；圖7圖示了基於瓦片區的查詢索引的一個例子700；
圖8圖示了尋找用於任意對象定位的覆蓋瓦片區的一個例子800；圖9圖示了對於一個對象位置列舉所有覆蓋瓦片區的一個舉例的算法的流程圖900；圖10圖示了一個對象運動到一個新位置時，增量式查詢評估的一個例子1000；圖11圖示了通過跳過某些計算來增量式評估查詢的算法的流程圖1100；圖12圖解了包括了本發明的舉例的硬體/信息處理系統1200；圖13圖解了用於存儲本發明的方法的程序步驟的信號承載介質1300(例如存儲介質)。
具體實施例方式
現在看附圖，尤其是圖1，來描述本發明的一個優選實施例。圖1圖示了移動環境的一個舉例的系統框圖100，其中，可以對大量運動對象，比如舉例的對象120-128，監測多個連續範圍查詢110-114。衛星101可以用來向地面的接收器130、131中繼和廣播數據。在地面，有許多移動對象120-128，以及區域計算機伺服器150、151，這些伺服器裝備有無線接收器130、131。
在此舉例的優選實施方式中，所述範圍查詢110-114被圖示為在二維空間中的矩形。但是，本領域的普通技術人員知道，它們也可以是其它形狀，比如二維空間中的圓形，三維空間中的立方體或者球形。
這些連續範圍查詢110-114指定要被監測的區域。查詢結果是位於各查詢區域之內的所有對象。這些範圍查詢的邊界由一臺或者多臺區域性計算機伺服器150、151維護。這些區域伺服器通過通信網絡140連接起來。
所述運動對象120-128裝備有定位設備，比如全球定位系統(GPS)設備。運動對象120-128的位置也由一臺或者多臺區域計算機伺服器150、151維護。對象位置的變化由運動對象120-128報告給計算機伺服器150、151，一般是通過無線鏈路130、131。
圖2圖示了這裡所公開的用於有效地監測對大量的運動對象的許多連續範圍查詢的、舉例的基於瓦片區的查詢索引(SQI)的概要格式200。一個瓦片區(shingle)是一個瓦片式的對象(不一定是矩形)，瓦片一般按重疊的列布置，以覆蓋一個區域。在本發明的上下文中，一個瓦片區可以定義為鋪起來以覆蓋一個區域(例如地理區域)的數字表達的瓦片式對象的數字表達，而不一定是按照重疊的列平鋪。
本發明的核心思想是使用一個或者多個瓦片區來覆蓋每一個範圍查詢。與所述單元(cell)不同，本發明的瓦片區可以相互重疊，這就類似於蓋房頂的瓦片。使用SQI，如果一個點落入覆蓋一個查詢的瓦片區之一之內，則對於該點是否被該查詢覆蓋來說沒有二義性。因此，就可以容易地採用增量式重新評估方法。？？對於那些自上一次重新評估以來沒有運動到一個瓦片區之外的對象來說，可以節約計算量。由於一個對象可能被多個瓦片區覆蓋，首先提供了一種確定覆蓋一個對象的瓦片區的集合的作為舉例的有效算法。利用新位置的覆蓋瓦片區和舊位置的覆蓋瓦片區的集合之間的差異來完成增量式重新評估。
為了實現SQI，預先定義了一組虛擬瓦片區。每一個虛擬瓦片區具有獨有的左下角(a，b)、寬度和高度。一個瓦片區直到它用來覆蓋一個範圍查詢之前都是虛擬的。在用來覆蓋範圍查詢時，該瓦片區就被視為已經被激活。
在步驟201和202，當要插入一個範圍查詢時，首先找到覆蓋該範圍查詢的一組虛擬瓦片區。然後，在步驟203，將查詢ID插入與覆蓋瓦片區相關的每一個ID列表。有許多方法可以用來用瓦片區來覆蓋一個查詢。
在一個優選實施例中，提供了一種簡單但是系統的方法。首先，畫一個從查詢矩形的底部起高k的矩形條，並向上移動。對於最後一個矩形條，允許該矩形條的底部與前一個矩形條重疊。對於每一個矩形條，用虛擬瓦片區來從左側開始覆蓋它，向右側移動。對於最後一個瓦片區，將右側對齊，允許該瓦片區的左側與前一個覆蓋瓦片區重疊。
為了搜索覆蓋給定對象的所有查詢，首先計算該對象的覆蓋瓦片區，然後，從這些覆蓋瓦片區，計算覆蓋該對象的所有查詢。下面說明一種對於任何給定對象位置列舉所有覆蓋瓦片區的一種有效的算法舉例。該列舉算法的實現系藉助於兩個重要的特徵恆定大小，以及相同間隔模式。對於所有對象位置，覆蓋瓦片區的數量是一樣的。如果按照升序排列覆蓋瓦片區的ID，則對於任意兩個位置來說，匹配位置的任意兩個瓦片區之間的間隔是相同的。
完全的查詢重新評估如下進行。對於每一個對象，找到其覆蓋瓦片區，然後找到覆蓋這些瓦片區的所有查詢。然後將該對象ID保存到與這些查詢相關的對象列表中。在最後，如步驟204所示，對象列表就是查詢結果。
但是，如下所述，提出了一種增量式重新評估以節約計算量。對於增量式重新評估，首先計算新位置和舊位置的覆蓋瓦片區。對於屬於新位置但是不屬於舊位置的所有覆蓋瓦片區，將對象的一個實例插入覆蓋這些瓦片區的查詢所指的對象列表中。這解決了對象已經移動到這些瓦片區中的情況。
對於屬於舊位置但是不屬於新位置的所有覆蓋瓦片區，從覆蓋這些瓦片區的查詢所指的對象列表中刪除對象的一個實例。這解決了對象已經移出這些瓦片區的對象的情況。對於既屬於新位置又屬於老位置的覆蓋瓦片區，不需要做任何事情。這解決了對象仍然留在這些瓦片區的邊界之內的情況。
監測對運動對象的連續範圍查詢的系統和方法主要由一種有效的查詢索引方法構成。對於這種查詢索引，定期地用每一個新的對象位置來尋找覆蓋它的所有查詢。對象ID然後被保存到與每一個覆蓋查詢相關的對象列表(OL)中。
在所有的對象位置被處理之後，就得到一個完整的新的查詢結果集合。換句話說，對象列表OL(q)包含當前位於查詢q的邊界之內的所有對象。用於查詢索引及其相關操作的數據結構作為計算機可執行的程序被保存在圖1中的一臺或者多臺區域伺服器150、151中。這些連續範圍查詢的結果可以被用來提供各種定位服務。
本發明的查詢索引系基於虛擬瓦片區。圖3舉例地圖示了虛擬瓦片區301-305的概念300。虛擬瓦片區是覆蓋瓦片區。虛擬瓦片區可以相互重疊。使用重疊的瓦片區，對於存儲量和性能來說取得了折衷。直到這些瓦片區被用來覆蓋一個範圍查詢之前，這些瓦片區都保持為虛擬的。在被用來覆蓋範圍查詢時，它們被激活。注意，示於圖3的每一個瓦片區301-305是4×4，在舉例的優選實施例中，該瓦片區大小保持恆定。
另外，每一個虛擬瓦片區301-305具有如下所述能夠系統計算的獨有ID。假設監測區域是由Rx和Ry限定的矩形，則，作為舉例，可以如下計算左下角位於坐標(a，b)的虛擬瓦片區的標識(ID)s(a，b)＝bRx+a。
這樣，在圖3中，由於監測區域306的大小是Rx＝16且Ry＝12，對於左下角在坐標(8，8)的虛擬瓦片區304來說，其ID為s(8，8)＝8×16+8＝136。類似地，瓦片區305的ID為s(12，8)＝8×16+12＝140。
在一個範圍查詢可以被插入到查詢索引中之前，首先找到一個或者多個虛擬瓦片區，以便該範圍查詢被嚴格覆蓋。這裡，「嚴格覆蓋」的意思是整個查詢區域被一個或者多個虛擬瓦片區完全覆蓋，並且這些覆蓋瓦片區中沒有一個在該查詢的邊界之外。
圖4圖解了「嚴格覆蓋」401與「鬆散覆蓋」402的概念400。差別在於是否有覆蓋瓦片區超出查詢邊界。也就是，在示於圖中上部401的嚴格覆蓋的情況下，覆蓋瓦片區404、405完全覆蓋查詢邊界並且仍然在查詢區域內，在圖中，查詢區域就是斜線覆蓋的區域403。相反，在鬆散覆蓋的情況下，如圖中下部402所示，對於覆蓋區域403的瓦片區406和407來說，至少有一個瓦片區(例如407)超出查詢邊界(例如區域408)。
嚴格覆蓋有一個重要特性，那就是，被瓦片區覆蓋的任何點保證被該查詢所覆蓋。如果不是嚴格覆蓋，則不存在該特性。例如，在圖4中，被瓦片區407覆蓋的區域408中的點就不一定被該查詢覆蓋。但是，任何被瓦片區404或者405覆蓋的點都在查詢的範圍內。
有許多種可能的方式實現用虛擬瓦片區嚴格覆蓋一個查詢。在這裡的實施例中，一種可能的簡單而又系統的方法如圖5和圖6所示。
這兩個附圖500和600圖示了用一個或者多個虛擬瓦片區覆蓋一個範圍查詢501的一個例子，其中，某些瓦片區可以相互重疊。對於該優選實施例的描述，假設虛擬瓦片區是大小都是k×k(例如4×4)的方形。顯然，虛擬瓦片區可以有不同於圖示的各種大小和形狀，比如矩形。
另外，假設這樣選擇k，使得其小於或者等於最小的範圍查詢的大小。也就是，所有的範圍查詢可以由一個或者多個虛擬瓦片區完全覆蓋。這樣，在圖5和圖6中，作為例子，k被選擇為4。
首先，為了覆蓋一個給定的範圍查詢501(例如斜線所覆蓋的區域)，如圖5所示，從該查詢矩形501的左下角開始生成高度等於虛擬瓦片區(例如瓦片區503)的高度的矩形條502。該矩形條502可以被標識為(3，3，11，4)，其中，矩形條的符號標識(a，b，c，d)的含義如下(a，b)是該矩形條的左下角的坐標，c是該矩形條的長，d是該矩形條的高。
然後，如圖6所示，矩形條的生成向上移動，成為矩形條601，它的標識應當是(3，5，11，4)。對於最後一個矩形條(在本例子中就是矩形條601)，該矩形條601的底部可以與前一個矩形條502重疊。顯然，矩形條的重疊實現了對範圍查詢501的嚴格覆蓋。
接下來，對於每一個矩形條502、601，用虛擬瓦片區(例如503-505以及602-604)來覆蓋所述矩形條，例如從左側開始向右側移動。對於每一個矩形條中的最後一個瓦片區(例如瓦片區505、604)，矩形條和瓦片區的右緣對齊，因此允許最後一個瓦片區的左側與前一個覆蓋瓦片區重疊，從而實現對矩形條的嚴格覆蓋。
這樣，在圖5中，用三個虛擬瓦片區503-505來覆蓋畫在範圍查詢501的下部的第一矩形條502。類似地，在圖6中，用三個虛擬瓦片區602-604來覆蓋畫在查詢501的上部的第二矩形條601。本領域的普通技術人員知道，有許多種其它的方法來用一個或者多個瓦片區完全覆蓋一個範圍查詢。顯然，矩形條502、601的重疊和最終瓦片區505、604的重疊實現了對範圍查詢501的嚴格覆蓋。
在找到所有的覆蓋瓦片區之後，將一個查詢ID插入與所有覆蓋瓦片區相關的ID列表中。圖7圖示了一種可能的基於瓦片區的查詢索引方案700。主要地，查詢索引維護一個從每一個虛擬瓦片區sk到查詢qi的ID的一個列表702的映射。也就是，列表702是一個到查詢703、704的指針陣列。令QL(s)表示與虛擬瓦片區s相關的查詢ID的集合。它包含s覆蓋的所有查詢。因此，如果一個虛擬瓦片區沒有用來覆蓋任何範圍查詢，則相應的ID列表為空。例如，在圖7中，查詢q1-q4被各種虛擬瓦片區完全覆蓋。部分瓦片區相互重疊。查詢ID被保存在相應的ID列表中，從而，例如，指針703、704分別指向瓦片區Si的查詢q2和瓦片區Sj的查詢q3。
為了搜索覆蓋一個對象位置的所有查詢，首先必須找到所有虛擬覆蓋瓦片區。令CSV(o)表示對象o(例如圖7中的對象O1、O2)的虛擬覆蓋瓦片區的集合。從這些虛擬覆蓋瓦片區，對於每一個s∈CSV(o)必須找到保存在相應QL(s)(例如703、704)中的所有查詢。
圖8圖示了對於位置在(x，y)的對象尋找所有覆蓋瓦片區的舉例的方法800，其中a＜x＜a+1，b＜y＜b+1。從圖8可以系統地如下列舉所有覆蓋瓦片區它們的左下角位於陰影區801中。該陰影區801由右上角分別在(a，b)和(a+1，b+1)的兩個瓦片區802、803的交限定。如圖8所示，總共有16個這樣的可能覆蓋瓦片區(例如，如果陰影區801中的每一個點有一個相關瓦片區的話)。這些覆蓋瓦片區的最小ID為s(a+1-k，b+1-k)，其在圖8中被標記為瓦片區803。最大的ID是s(a，b)，其在圖8中被標記為瓦片區804。
圖9是對於位置在(x，y)(其中，a＜x＜a+1，b＜y＜b+1)的對象o系統地列舉覆蓋瓦片區的集合CSV(o)的舉例的流程圖900。首先，在步驟901，覆蓋瓦片區集合被初始化為空集，J被初始化為b+1-k。然後，在步驟902，檢查(J＞b)是否為真。如果是，則在步驟909，例程結束，返回CSV(o)。
如果不是，則在步驟903，還檢查(J＞＝0)是否為真。如果不是，則在步驟910將J增一。否則在步驟904，I被初始化為a+1-k。在步驟905，檢查(I＞a)是否為真。如果是，則在步驟910對J加1。如果不是，則在步驟906進一步檢查(I＞＝0)是否為真。如果是，則在步驟907，將瓦片區s(I，J)加到CSV(o)。在步驟908，對I加1。在步驟906，如果(I＜0)，例程跳到步驟908。在I在步驟908增一以後，例程返回步驟905。
本領域的普通技術人員可以理解，只要對象位置不在邊界區域中，任何對象位置的覆蓋瓦片區集合的大小是恆定的。邊界區域由0≤x＜k，Rx-k≤x＜Rx，0≤y＜k，或者Ry-k≤x＜Ry限定。在圖8中四處移動對象就很容易驗證這一點。覆蓋瓦片區的相對位置可以變化，但是陰影區801的大小保持不變。
圖8中陰影區801圖解的概念可以用於確定當移動對象時涉及哪些瓦片區。也就是，給出了對於一個對象位置列舉所有覆蓋瓦片區的舉例的過程，圖10圖解了舉例的增量式查詢重新評估。該示了當一個對象從一個位置移到另一個位置(圖中的例子是從位置L1到位置L2)時，節省某些查詢評估的例子。一般，當對象移動時，新位置CSVnew(o)的覆蓋瓦片區的集合和舊位置CSVold(o)的覆蓋瓦片區集合可能重疊。也就是，有一些瓦片區同時屬於兩個集合。
對於那些同時屬於兩個集合的覆蓋瓦片區，不需要進行計算。這是因為運動對象沒有運動到這些覆蓋瓦片區的邊界的外部。但是，對於那些屬於CSVnew(o)但是不屬於CSVold(o)的瓦片區，對象ID需要插入到這些瓦片區所覆蓋的相關查詢中。另一方面，對於那些屬於CSVold(o)但是不屬於CSVnew(o)的瓦片區，對象ID需要從這些瓦片區所覆蓋的相應查詢中刪除。
圖10圖示了在圖8所示的環境下，當對象從位置L1到L2時的相關區域。也就是，在圖10中，位置L1對應於圖8中的位置(x，y)。圖10中的新位置L2大致離開了一個單元。
因此，可以直觀地看到，圖8中的4×4陰影區801現在會按照新位置L2移動。該4×4陰影區的該位置移動圖示於圖10中，只不過該4×4區域現在可能被分解為三個區域。
在第一區域1001中，3×3方塊由圖8所示的4×4區域801和對應於新位置L2的新的4×4區域共用。在該3×3方塊1001中，表示了對於對象標識列表不需要進行操作的所有覆蓋瓦片區。
區域1002是4×4陰影區801的已經因為位置移到L2而騰空的部分。該區域1001表示需要對對象標識列表進行刪除操作的那些覆蓋瓦片區。
最後，圖10中的區域1003標識該4×4方塊中的新加入的部分。也就是，在區域1003中，表示了需要在對象標識列表中進行插入的那些覆蓋瓦片區。
因此，基於圖10所示的概念，在圖11中圖示了一個舉例的例程的流程圖1100，該例程用於通過過濾出某些計算來進行查詢的增量式重新評估。對於作為所有運動對象的集合的O中的每一個對象，進行查詢重新評估。當每一個對象都被檢查過(例如步驟1101、1102和1107)之後，例程在步驟1103停止。
首先，對於每一個對象，在步驟1104，首先計算新位置和舊位置的覆蓋瓦片區的集合CSVnew(o)和CSVold(o)。然後，在步驟1105，o的一個實例，sk∈CSVnew(o)-CSVold(o)，被插入OL(q)，q∈QL(Sk)。之後，在步驟1106，o的一個實例，sj∈CSVnew(o)-CSVold(o)，從OL(q)中被刪除，q∈QL(Sj)。注意，對於s∈CSVnew(o)∩CSVold(o)，不需要採取動作。
本領域的普通技術人員可以理解，類似於對象，範圍查詢可以到處移動。在這種情況下，首先，舊的範圍查詢從查詢索引中被移除，然後插入新的範圍查詢。然後，類似地使用對象來尋找所有覆蓋範圍查詢，以定期地重新評估查詢結果。
顯然，基於在本發明中所公開的系統和方法，可以提供各種服務。作為第一個例子，可以為計程車公司提供服務，向請求租車服務的乘客分配計程車。服務提供商將計程車作為運動對象來加以監測，將它們的位置定期報告給服務提供商。
一個或者多個計程車站，比如賓館或者飯店，以及圍繞這些車站的範圍，都可以代表本發明的範圍查詢。服務提供商可以使用本發明公開的系統方法反覆地維護當前在所述範圍查詢內的計程車。這樣的查詢結果可以被提供給計程車公司，以便合適地向從一個所述車站呼叫計程車的乘客分派計程車。
作為另一個例子，可以向一個或者多個商店提供基於本發明的系統和方法的一種服務，以便允許這些商店能夠向當前正在走近這些商店的帶有行動電話或者PDA的顧客動態地發送電子優惠券。在這個例子中，商店以及它們所希望的範圍是所述查詢。帶有行動電話或者PDA的顧客是運動對象。服務提供商可以相對於所述商店及其範圍查詢監測這些運動對象。希望向當前在商店周圍的顧客發送電子優惠券的商店店主可以利用這樣的服務。
但是，顯然，上述例子指示本發明的兩種可能的應用，不能用於從任何方面來限制本發明。本發明提供了一種監測運動對象的計算技術，並且，回到圖1的框圖，示於圖1的任何層次的用戶和設施都可能對之感興趣。這樣，本發明的用戶可以被視為被表示為用本發明的技術被跟蹤的運動對象120-128的最終用戶，或者使用查詢結果的服務(例如計程車公司)或者商店(例如進行電子優惠券分發的商店)的運營者，或者直接執行本發明(或者為了自己使用或者為了轉發給客戶比如計程車公司)的服務提供商150、151。在某些條件下，對象跟蹤系統(例如，被圖示為衛星101)的擁有者/運營者、無線接收設施130、131甚至計算機網絡140可以被視為本發明的用戶。
舉例的硬體實施方式圖12圖示了根據本發明的信息處理/計算機系統1200的典型硬體配置，它最好具有至少一個處理器或者中央處理器(CPU)1211。
CPU1211通過系統總線1212被互連到隨機存取存儲器(RAM)1214、只讀存儲器(ROM)1216、輸入輸出(I/O)適配器1218(用於將外圍設備比如磁碟單元1221和磁帶設備1240連接到總線1212)、用戶接口適配器1222(用於將鍵盤1224、滑鼠1226、揚聲器1228、麥克風1232以及/或者其它用戶接口設備連接到總線1212)、用於將信息處理系統連接到數據處理網絡、網際網路、內聯網、個人區域網絡(PAN，personal area network)等的通信適配器1234以及用於將總線1212連接到顯示設備1238和/或印表機1239(例如數字印表機等)的顯示適配器1236。
除了上述硬體/軟體環境之外，本發明的另外的方面包括用於實現上述方法的計算機實現的方法。例如，該方法可以在上述特定環境中實現。
例如，這樣的方法可以通過操作一臺計算機來實現，該計算機被實現為一個數字數據處理設備來執行一個機器可讀指令序列。這些指令可以駐留於各種類型的信號承載介質中。
因此，本發明的這一方面是一種被編程的產品，它由信號承載介質構成，其中有形地實現可由包括CPU1211和上述硬體的數字數據處理器執行的機器可讀指令的程序，以執行本發明的方法。
所述信號承載介質例如可以包括被包含在所述CPU1211中的RAM，例如可以快速存取存儲器為代表。或者，所述指令可以被包含在另一種信號承載介質中，比如可由CPU1211直接或者間接訪問的磁數據存儲盤1300(圖13)。
無論是在磁碟1300中、計算機/CPU1211中或者別處，指令都可以被存儲在各種機器可讀數據存儲介質上，比如DASD存儲器(例如傳統的硬碟驅動器或者RAID陣列)、磁帶、電子只讀存儲器(例如ROM、EPROM或者EEPROM)、光存儲設備(例如CD-ROM，WORM，DVD，數字光碟等)、紙質穿孔卡，或者其它合適的信號承載介質，包括傳輸介質，比如數字或者模擬通信鏈路和無線鏈路。在本發明的一個說明性實施例中，所述機器可讀指令可以包括軟體目標代碼。
儘管前面針對一個優選實施例對本發明進行了描述，本領域的普通技術人員知道，可以在所附權利要求的實質範圍內稍加修改來實現本發明。
另外還應注意，申請人的意圖是將所有權利要求要素的等效方案包括進來，即使在以後的申請過程中權利要求可能被修改。
權利要求
1.一種監測對運動對象的連續查詢的方法，包括標識一個數字格式的查詢區域；以及用至少一個瓦片區嚴格覆蓋所述查詢區域，使得所述查詢區域被所述至少一個瓦片區完全覆蓋，任何所述至少一個瓦片區沒有任何部分在所述查詢區域之外。
2.如權利要求1所述的方法，其中，當嚴格覆蓋一個查詢區域的所述至少一個瓦片區包括多個瓦片區時，所述多個瓦片區中的瓦片區允許交迭。
3.如權利要求1所述的方法，還包括對每一個被監測的對象建立一個對象標識列表，所述對象標識列表指明哪些瓦片區覆蓋一個對象以及哪些查詢區域包括這些瓦片區。
4.如權利要求1所述的方法，其中，每一個所述瓦片區具有一個預定的形狀。
5.如權利要求1所述的方法，其中，多個查詢區域包括地球表面的預定地理區域，所述瓦片區包括多個二維形狀和多個三維形狀中的至少一個。
6.如權利要求1所述的方法，還包括對於一個查詢區域，確定用於該查詢區域的最佳瓦片區大小。
7.如權利要求6所述的方法，其中，嚴格覆蓋所述查詢區域的步驟包括基於所述最佳瓦片區大小形成第一矩形條，所述第一矩形條在第一維度沿著所述查詢區域的一個邊緣。
8.如權利要求7所述的方法，其中，所述第一矩形條不嚴格覆蓋所述查詢區域，該方法還包括對於第二維度，基於所述最佳瓦片區大小形成第二矩形條。
9.如權利要求8所述的方法，其中，所述最佳瓦片區大小允許所述第二矩形條嚴格覆蓋所述查詢區域。
10.如權利要求9所述的方法，其中，所述第一矩形條和所述第二矩形條相互重疊以實現所述嚴格覆蓋。
11.如權利要求8所述的方法，其中，所述最佳瓦片區大小不允許所述第二矩形條嚴格覆蓋所述查詢區域，該方法還包括在所述第二維度，基於所述最佳瓦片區大小反覆形成一個矩形條，直到所述查詢區域被多個矩形條完全覆蓋，其中，最後的矩形條允許與前一個矩形條重疊，以實現所述嚴格覆蓋。
12.如權利要求7所述的方法，還包括在所述第一矩形條中形成多個瓦片區，每個所述瓦片區基於所述最佳瓦片區大小，從而嚴格覆蓋所述第一矩形條。
13.如權利要求12所述的方法，其中，嚴格覆蓋所述第一矩形條是這樣實現的允許所述第一矩形條中的最後瓦片區與前一個設置的瓦片區重疊。
14.如權利要求8所述的方法，還包括對於形成的每一個矩形條，以嚴格覆蓋所述矩形條的方式在所述矩形條中形成多個瓦片區。
15.如權利要求3所述的方法，還包括識別哪些瓦片區覆蓋每一個相關對象；以及根據哪些瓦片區覆蓋相關對象，維護一個位於每一個查詢區域中的對象的查詢索引。
16.如權利要求15所述的方法，其中，通過將所述相關對象的沒有從先前覆蓋對象的瓦片區移動的一個子集過濾出來，來跳過特定的查詢評估。
17.一種監測對運動對象的連續查詢的系統，包括用至少一個覆蓋瓦片區嚴格覆蓋每一個查詢的模塊，每一個所述查詢是用數字格式表示的一個區域，其中，所述嚴格覆蓋功能包括用至少一個所述覆蓋瓦片區完全覆蓋一個查詢，其中，嚴格覆蓋所述查詢的所述瓦片區中沒有任何瓦片區延伸到所述查詢之外，嚴格覆蓋所述查詢的每一個所述瓦片區允許與嚴格覆蓋所述查詢的另一個瓦片區重疊。
18.如權利要求17所述的系統，還包括通過使用所述嚴格覆蓋瓦片區過濾出所述運動對象的一個子集來跳過特定查詢評估的計算器。
19.如權利要求18所述的系統，其中，所述計算機還基於所述覆蓋瓦片區構建一個查詢索引，運動對象的子集的所述過濾基於所述查詢索引。
20.如權利要求18所述的系統，其中，所述運動對象的子集的所述過濾基於對相對於瓦片區邊界自上一個位置以來的相對運動的確定。
21.如權利要求19所述的系統，其中，運動對象的子集的所述過濾基於構建一個查詢索引，所述計算器還預定義一組瓦片區；用一個或者多個所述瓦片區覆蓋一個範圍查詢；並且用所述多個覆蓋瓦片區維護所述範圍查詢的ID。
22.如權利要求18所述的系統，其中，對所述運動對象的子集的所述過濾還包括計算老對象位置的覆蓋瓦片區；計算新對象位置的覆蓋瓦片區；從與被老位置的覆蓋瓦片區覆蓋但是不被新位置的覆蓋瓦片區覆蓋的查詢相關的對象列表中刪除對象ID實例；以及向與被所述新位置的覆蓋瓦片區覆蓋但是不被新位置的覆蓋瓦片區覆蓋的查詢相關的對象列表中插入對象ID實例。
23.如權利要求18所述的系統，其中，對運動圖像的一個子集的所述過濾還包括計算老對象位置的覆蓋瓦片區；計算新對象位置的覆蓋瓦片區；以及對於同時被新位置和老位置的覆蓋瓦片區覆蓋的查詢，不採取任何動作。
24.一種基於監測對運動對象的連續查詢的服務，包括至少下述之一針對連續查詢提供對運動對象的監測，每一個所述查詢是用數字格式表示的一個區域，該監測使用包括用至少一個瓦片區嚴格覆蓋每一個所述查詢區域的方法，其中，所述嚴格覆蓋功能包括用所述至少一個所述覆蓋瓦片區完全覆蓋一個查詢區域，任何所述至少一個瓦片區中沒有任何部分在所述查詢區域之外；提供使用所述方法的所述監測的結果；以及利用使用所述方法的所述監測的結果。
25.一種信號承載介質，其有形地實現可由數字處理設備執行的機器可讀指令的程序，該程序執行一個監測對運動對象的連續查詢的方法，該方法包括用至少一個瓦片區嚴格覆蓋每一個查詢區域，其中，所述嚴格覆蓋功能包括用至少一個瓦片區完全覆蓋所述查詢區域，任何所述至少一個瓦片區沒有任何部分在所述查詢區域之外。
全文摘要
本發明涉及監測運動對象的方法和結構，具體地是監測對運動對象的連續查詢的方法和結構，包括標識一個數字格式的查詢區域；用至少一個瓦片區嚴格覆蓋每一個查詢區域，使得每一個查詢區域被所述至少一個瓦片區完全覆蓋，任何所述至少一個瓦片區沒有任何部分在所述查詢區域之外。
文檔編號G06Q30/00GK1603749SQ200410011830
公開日2005年4月6日 申請日期2004年9月22日 優先權日2003年9月29日
發明者陳世魁, 吳坤龍, 俞士綸 申請人:國際商業機器公司