---
tags: DBMS
---
# [2019 ICDE] An efficient framework for correctness-aware knn queries on road networks
## Abstract
$KNN\ query$ = 在一路網上有 $o$ 的物件集合以及 $q$ 點 ($q$ 點 不等於 $vertex$)，$KNN\ query$ 意思為離 $q$ 點最近的 $k$ 個物件($\in o$)。
這篇論文提出一個 $GLAD$ 框架來解決 $KNN$ 的正確性以及提升效能。在此框架下執行的 $KNN$ 任務能夠消耗較少的運算資源($Enhance\ efficient$)且有效率的來獲得正確答案($Enhance\ throughput$)。
## Introduction
* $KNN$ 能夠用在叫計程車，路邊意外處理或警察派遣，解決實際路況的情況。作者提到現有許多試圖解決路網問題的架構，但都無法在效能與答案間取得平衡。而問題的癥結點多發生在 $KNN\ Correctness$。而 $correctness$ 是由兩大因素去決定。
1. $Update\ Moving\ Object$
系統更新移動物件的頻率通常比更新物件的 $index$ 還要快。若一個路網中有許多追蹤中的移動物件，那所需的時間比更新單一物件的所在位置還花時間。這就導致了系統上物件與實際上的位置不同。e.g. $Uber\ EAT$
2. $Query\ Conflict$
兩個並行的 $KNN\ Query$ 獲得相同的 $Object$。e.g 在兩個不同的點$q_{1}, q_{2}$ 的 $3NN$ 拿到 $q_{1} = (o_{1}, o_{3}, o_{4})$，$q_{2} = (o_{1}, o_{2}, o_{5})$。在 $o_{1}$ 被重複獲得的情況下，$q_{2}$ 的時間就會被 $Delay$ 或是 $Abort$
* 這篇論文提出一個框架 $GLAD$ 提供 $High\ throughput$ 兼顧 $Correctness$。
1. $light-weighted\ grid\ index\ structure$，透過本論文的索引架構能夠快速更新 $index$ 並獲取 $query$，解決第一個問題。
2. $formally\ define\ the\ conflict\ and\ serializability\ of\ KNN$，透過本論文的排程演算法能夠有效解決 $query\ conflict$ 進一步提升系統整體的輸出。
## Problem Defination

digraph linkedlist {
	node[shape = circle]
	v
    u
    o
    q
    rankdir=LR
    {
        u->v[label="e(u, v)"]
        u->o
        o->v
        u->q
        q->v 
    }
}

這篇論文假設 $Object\ o$ 與 $Query\ q$ 都在 $Vertex$ 上，忽略掉上面的誤差。
* KNN query
KNN query returns a set $R \subseteq M$ of k moving objects sucj that for all ....
* KNN Conflict
* Update query conflict
* Serializable kNN

我們應該要盡量避免 $query\ conflict$ 還有 $query\ update\ conflict$，這樣才要有效增加系統輸出。
以下簡介我們系統模型，分為$task\ arrival\ ,\ task\ handling$ 兩部分。

* Task arrival
假設 $queries$ 進入系統的過程是柏松分布(也就是一段時間區間內互相獨立不影響。)系統會每 $T$ 更新所有 $object$ 一次。假設 $Object$ 的 GPS 更新週期為 $T_{0}$，則因為更新成本以及處理時間的考量，假設處理時間為 $T_{u}$，若 $T_{u} > T$ 則系統不會有輸出，因為處理趕不上更新。$T > T_{0}$ 通常為成本的考量。
* Task Handling
一個系統中應存在多個處理單元，由 $Task\ queue$ 來做分配，達成平行的執行條件。透過 $Response\ time\ T_{r}$ 的限制，提高舊 $query$ 的優先度。因為是平行處理 $query$ 所以有可能發生 $conflict$ 一旦發生則把該 $query$ 丟棄並重新計算，因為處理的時間是在下次更新前的間隔，所以不會更新 $query$ 內容。
透過此公式，可以知道系統的總體輸出能夠靠減少 $query\ processing\ time\ t_{q}$ 以及 $update\ time\ t_{u}$ 來增加。
## GLAD Index structure
$GLAD$ 的物件索引架構是基於網格($Grid-based$)來記錄的。以下簡述其作法
* 將路網切分成不同網格並記錄觀察進入網格的物件
* 在網格中的節點彼此距離固定
* 因此在計算 $KNN\ query$ 時能夠透過獲取節點間的距離來快速得到物件與 $query$ 的距離

將路網切成 $2^{x} * 2^{x}$ 的正方形，並透過 $Hilbert\ curve$ 將每個網格標上編號。
並且記錄
* 每個網格上有哪些物件
* 每個物件落在哪些網格上

為了避免每隔 $T$ 時間全部更新一次造成的時間成本，論文採用不同的更新手段。
1. 優先更新要求更新的物件。
* 如果一物件移動到新的網格，則將該物件直接放入那網格儲存物件的 list 中。雖然會造成重複的資訊，但不會影響到整體的正確率。
* 並且在遍歷網格的途中也會將重複的刪除
2. 透過累積更新次數來避免大量更新
* 當有更新一物件的網格索引( $Grid\ index$ )後，總更新次數 $a_{u}$ 就會增加 1 。
* 當 $a_{u}\ =\ |M|$ 的時候就會從頭更新一次，這樣 $Update\ cost$ 最多 $O(|M|)$
舉例來說，Fig 3 上有五個物件 $o_{1}, o_{2}, o_{3}, o_{4}, o_{5}$，分布在 $v_{1}, v_{3}, v_{6}, v_{8}, v_{9}$ 五個頂點上。因此各網格的儲存資訊如下。
* $L_{4} = \{ o_{1}, o_{2} \}$
* $L_{10} = \{ o_{3} \}$
* $L_{40} = \{ o_{5} \}$
* $L_{52} = \{ o_{4} \}$
* 並且透過一陣列 $\{4, 4, 10, 52, 40\}$來表示對應物件所處的網格號碼。

因為現存大量的紀錄節點間距離的方式，此篇論文用 $D(u, v)$ 來表示節點間距離。
因為是要算 $K$ 個最近的物件，所以在此用基於網格($Grid-based$)的剪枝方式計算並挑選。
這個演算法的目的是利用歐式距離，以 $query$ 所在的點為中心，擴散出去來找到最近的 $K$ 個物件。e.g. $1*1,\ 3*3,\ 5*5$ 透過這種方式可以大幅減少計算所有物件與 $query$ 距離的時間。以 $query$ 為起點，第一輪是計算 $query$ 的鄰居網格有沒有物件存在，之後再尋找鄰居往隔的鄰居網格，一層一層迭代，直到找到 $K$ 個為止。
舉例來說，如上圖我們希望找到在 $Vertex\ 7$ 的 $2NN\ query$。一開始找 $Vertex\ 7$ 的 $grid$，裡面沒有物件。之後往外找 $3*3$，找到兩個候選物件 $\{o_{3}, o_{4}\}$。雖然找到兩個，但因為路網邊長不一定相同，較遠的網格有可能抵達 $Vertex\ 7$ 的距離比近的網格快。所以再往外找 $5*5$，發現 $o_{5}$ ，但其的距離比候選物件的第二短還長，所以不需要再往下找。
以下簡述
* 先找 $query\ grid$
* 以 $query\ grid$ 為中心擴大搜尋
* 若最小的距離大於第 $K$ 物件的距離則結束

**Question**
> 因為路網邊界的長度以例子來說有可能會不相同，為何在一次找不到後就停止?
> 可能跟計算距離的方式有關