考慮移動物體上與位置無關屬性之異質k近鄰監測

Monitoring Heterogeneous Nearest Neighbors for Moving Objects by Considering Location-independent Attributes

蘇郁琪(Yu-Chi Su)

指導教授 ： 陳良弼

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

摘要

當今的空間查詢系統其空間資料(spatial data)含有幾個與位置無關之屬性。例如， 以一個工作搜尋系統為例 ，此系統中的每一個工作(可視為一個物件) 皆含有與空間有關之屬性，例如 ：工作地點；亦含有與空間無關之屬性，例如：薪水。 利用此工作搜尋系統，使用者可尋得一個離住所不遠、同時薪水又高的工作。 因此 ，一個既可以同時考慮距離及薪水的查詢即可以滿足使用者的需求。在本篇論文中，為了區別傳統上只考慮與空間相關之屬性的k近鄰查詢，我們稱此查詢為 「異質k近鄰查詢 」。就我們目前所認知 ，此篇論文為第一篇於動態環境之下，針對異質k近鄰查詢所設計之全面解決方案。 而先前針對傳統k近鄰的方法並不能延用於解決異質k近鄰問題。有鑑於此，本篇論文提出一個利用邊界性質來解決異質k近鄰問題的有效方法。 我們更進一步提出了一個更新機制以動態監測連續性的異質k近鄰查詢。我們的實驗結果亦證明我們提出的方法十分有效率。

關鍵字

異質k近鄰 ； 移動物體

並列摘要

In some advanced applications, spatial data may have several location-independent attributes. For example, in a job finding database, each job opportunity (object) can be associated with both location-dependent attributes, e.g., the work location, and location-independent ones, e.g., the salary. A person who uses this database to find a job may prefer not only a shorter distance between his/her house and the work place but also a higher salary. Therefore, a query with both concepts of “shorter distance” and “higher salary” should be considered to meet the user’s needs. We call it the heterogeneous k-nearest neighbor (HkNN) query in distinction from the traditional k-nearest neighbor (kNN) query on spatial domain, which only concerns location-dependent attributes. To our knowledge, this thesis is the first work proposing a generic framework for solving the HkNN query in a dynamic environment in which the values of both the location-dependent attributes and the location-independent attributes of an object may change with time. Previous works on the traditional kNN problem cannot be applied to processing the HkNN query. In this thesis, we propose an efficient approach based on the bounding proprieties for the HkNN query evaluation. Furthermore, we provide an update mechanism for continuously monitoring the HkNN queries in a dynamic environment. Experimental results verify that the proposed framework is both efficient and scalable.

參考文獻

[1] R. Benetis, C. S. Jensen, G. Karciauskas, and S. Saltenis. Nearest neighbor and reverse nearest neighbor queries for moving objects. In Proc. IDEAS, pages 44-53, 2002.

[2] T. Brinkhoff. A Framework for Generating Network-Based Moving Objects. GeoInformatica, 6(2), 2002.

[3] R. Cheng, Y. Xia, S. Prabhakar, and R. Shah, “Change Tolerant Indexing for Constantly Evolving Data,” Proc. ICDE Conf., pp. 391-402, 2005.

[4] A. Guttman. R-trees: A dynamic index structure for spatial searching. In Proc. SIGMOD, 1984.

[5] G. S. Iwerks, H. Samet, and K. Smith. Continuous k-nearest neighbor queries for continuously moving points with updates. In Proc. VLDB, 2003.