於空間資料庫考量雙資料型態的反向最近點Top-N查詢處理

Top-N Query Processing on Spatial Databases Considering Bi-chromatic Reverse k-Nearest Neighbors

李嘉倫(Cha-Lun Li)

指導教授 ： 陳良弼

國立清華大學/電機資訊學院/資訊工程學系/碩士(2010年)

https://doi.org/10.6843/NTHU.2010.00466

摘要

一個反向最近點(RkNN)查詢找出把查詢點當成前k個近的資料點。而雙資料型態反向最近點(BRkNN)查詢是RkNN的變形，考量兩種資料型態。給予兩個不同型態資料集G和C，G中的一個BRkNN查詢點會找出C中那些把查詢點在G中為前k個近的資料點。不同於傳統BRkNN，我們提出了一個基於BRkNN的Top-n查詢，會找出G中具有最多BRkNN結果的N個點。我們利用了Voronoi Diagram索引G資料集，並可輕易的計算出各個G中的點的最大限BRkNN結果。然後對於每個查詢我們套用並改良現存的方法去找出屬於此查詢點的搜尋區域，最後輔以三角不等式
對落在區域中屬於C的資料點做精算而得到答案。我們和目前最佳的BRkNN方法比較，把它套用於我們的問題中，實驗顯示出不論是Top-N的查詢抑或是單一個BRkNN查詢我們效能都明顯的比較好。

關鍵字

反向最近點查詢 ； 空間資料庫 ； 前N解查詢處理 ； 雙資料型態反向最近點查詢

並列摘要

A reverse k-nearest neighbor (RkNN) query retrieves the data points regarding the query point as
one of their corresponding k nearest neighbors. A bi-chromatic reverse k-nearest neighbor (BRkNN)
query is a variant of the RkNN query, considering two types of data. Given two types of data G and
C, a BRkNN query regarding a data point q in G retrieves the data points from C that regard q as one
of their corresponding k-nearest neighbors on G. Many existing approaches answer either the RkNN
query or the BRkNN query. However, different from these approaches, we make the first attempt to
propose a novel top-n query based on the concept of BRkNN queries in this thesis, which ranks the
data points in G and retrieves the top-n ones according to the cardinalities of the corresponding
BRkNN answer sets. For efficiently answering this top-n query, we construct the Voronoi Diagram
of G to index the data points in G and C. The information related to the Voronoi Diagram of G can
help to quickly compute the upper bounds of the cardinalities, thus efficiently pruning some
candidate results. Moreover, based on an existing approach to answering the RkNN query and the
characteristics of the Voronoi Diagram of G, we propose another method to find the candidate
region regarding a BRkNN query, which tightens the corresponding search space. Finally, based on
the triangle inequality, we also propose an efficient refinement algorithm for finding the exact
BRkNN answer sets from the candidate regions. To evaluate our whole approach to answering the
novel top-n query, it is compared with a naïve approach which applies a state-of-the-art algorithm
for answering the BRkNN query to each data point in G. The experiment results reveal that our
approach outperforms the naïve approach. Moreover, our approach to answering a single BRkNN
query also outperforms this existing algorithm.dI

並列關鍵字

RkNN ； Spatial database ； Top-N ； BRkNN

參考文獻

Efficient Reverse k-Nearest Neighbor Search in Arbitrary Metric Spaces. In

Neighbor Search in Dynamic and General Metric Databases. In Proceedings of

[3] R. Benetis, C. S. Jensen, G. Karciauskas, and S. Saltenis. Nearest Neighbor and

Reverse Nearest Neighbor Queries for Moving Objects. In proceeding of the 6th

International Database Engineering & Applications Symposium, IDEAS2002,