Algorithms for Characterization and Trend Detection in Spatial Databases

論文篇名:Algorithms for Characterization and Trend Detection in Spatial Databases

摘要:

在空間特徵化(spatial characterization)中如何去決定每個類別所隸屬的資料庫物件是很重要的，因為非是只有不是空間的特性而且還要考慮鄰近點的資訊。在空間方位的分析上，一些在資料庫物件中的鄰近節點其非空間性的屬性的位元變化也會決定其資料。我們提出許多演算法在這個目的上。

緒論:

SDBS(Spatial Database System)式資料庫系統用來處理,控管空間資料的。是爲了找出隱含的規則，或是隱藏在大量資料中的法則或模式。在位置行銷，流量管制或是環境考察中，spatial data algorithm is very importment.
在這篇論文中，我們提出一個新的演算法在特徵化還有方位的偵測在空間資料庫中。一個簡單的方法在空間方位偵測，根據一般化群集演算法，在(Ester et al, 1996)中提出。
在1993年，以屬性為導向的歸納法被設計完成，使用空間和非空間的階層式去搜尋空間和非空間屬性之間的關係。這些資料根據階層式觀念來一般化。他們提出依個演算法去找尋空間資料的規則從X->Y(c%)，X and Y are sets of spatial or non-spatial predicates and c is the confidence of the rule.

我們的演算法在空間特徵化和方位偵測上是以一個簡單方法來呈現。一般
得spatial data mining都是使用詳盡的或是固有的相鄰的關係。但是我們質疑這種方式，因為在一堆資料中要詳盡的去找尋不會有效率。因此，一個延伸至SDBS的資料架構和運算，在有效率的找尋鄰近點的關係上的研究被提出(Ester et al, 1997a)

Database Primitives for Spatial Data Mining:
我們的架構的概念是根據鄰近節點的圖像和相鄰的路徑是由鄰近物件的關係來決定。
這裡有三個空間關係的基本模型:位相幾何學(topological)，距離，方向的相關性而這是由結合邏輯運算子去表達更複雜的鄰近節點的關係。我們只關心二度空間中方向的關係因為這在我們的濾波器中是被要求詳盡的以便於判斷。
文中提到，顯然地，兩個物件中的方位不會為唯一且輪廓分明的，再論文的例子中的圖一就顯示，兩個物件會有許多方位，就譬如兩個物件來作為說明，B在A南方，B也在A東方。爲了找到一個唯一的區域，作者說兩個物件一定有一個方位的相關性是最小的，稱為exact direction relation of A and B，是uniquely determined，在圖中則是B northeast A的區域最小，所以此區域即為exact direction relation of A and B。

定義一:
以下訂一幾項變數
neighbor :neighborhood relation
DB :Database of spatial objects
neighborhood graph :G(DB/neighbor) = (N,E)
graph with nodes :N=DB
edges :E包含於N*N
edge :e=(n1,n2)
a neighborhood path of length :k
k is defined as a sequence of nodes[n1,n2,...,nk]
neighbor(ni,ni+1) holds for all ni屬於N,1 小於等於 i 小於 k
我們假設在關係代數(relational algebra)標準的運算，就像是selection,union,intersection和difference是可獲得的在此物件的集合中和鄰近路徑的集合(e.g.運算選擇(set, predicate)returns the set of all elements of a set satisfying the predicate predicate)。只有接著的重要運算是明白的描述的。

• neighbors: Graphs*Objects*Predicates-->

Sets_of_objects

• paths: Sets_of_objects-->Sets_of_paths
• extentions:Graphs*Sets_of_paths*Integer*Predicates*Sets_of_paths

運算子的鄰近點(graph,object,predicate)回傳全部物件的那個集合，連結到圖像的物件，滿足predicate predicate所要的條件。

運算的路徑(objects)產出長度1的所有路徑，是由一個單一的元素所形成，而且運算子副檔名(graph,paths,max,predicate)回傳此集合中的所有路徑並延伸其中一個路徑到圖上最長的節點。這延伸的路徑必須滿足宣稱的屬性。如此路徑不會保持到最後，即暗示沒有路徑可被延伸。

因為鄰近點數目可能會很多，這證明論述在鄰近作用和延展的動作過程，被當作濾波器去限制鄰近點的數目和路徑去找到他要的形式的鄰近點和路徑。
...

此篇論文是在找尋與某點有相關的特性與值，且鄰近點也會是拿來判斷的依據，並在找到之後不斷延伸直到找不到有相關性的點為止。

討論

此篇論文與走失偵測所需的要件不同:

(1)此篇論文主要在解釋概念性，閱讀之後無法了解該如何實用到我們的系統之上。

(2)如何判斷某個座標為此座標的鄰近點，此篇論文並無提及。

(3)此系統將所有點以一固定距離分配好，系統運行時開始往下去尋找，用線性迴歸下去運算。但是我們使用GPS訊號會有時間的這個參數，此系統並無考慮，因此我覺得還需要再多加尋找其他資料或是文章，才可讓思緒更加清楚。