無線廣播環境下k個最近鄰居搜尋方法的探討

在無線通訊網路環境下，以資料廣播(Data Broadcasting)的方式能有效的散播資料給大量的行動用戶端。很多種類的資訊都可利用這樣的技術來服務眾多行動用戶端，包括適地性服務(Location-Based Services, LBS)。適地性服務是一種提供與特定位置相關的資訊服務，其中包含k個最近鄰居(k-Nearest Neighbors, kNN)的搜尋，也就是支援行動用戶端查詢在他們目前位置附近所需的相關物件。以延遲時間(Latency) (從行動用戶端切入廣播頻道到結束接收所需資料的時間)與查詢時間(Tuning Time) (行動用戶端真正花費在收聽廣播頻道到的時間) 作為衡量的標準下，我們提出一個使用廣播方式來搜尋kNN的方法，其中k可支援為任意整數。在伺服端我們探討如何產生廣播排程(Broadcast Schedules)；而在行動用戶端則探討如何在此廣播排程下有效的執行查詢。為了有效節省查詢時間，我們所提出的方法是利用額外的附帶資訊來取代一般索引的方式，此外為了有效降低延遲時間，在排序一組廣播的資料時，我們使用不同的空間填充曲線(space-filling curves)來保持資料的方位性，從實驗結果發現，我們所提出的方法能有效的降低延遲時間與查詢時間。

關鍵字

適地性服務； k個最近鄰居；資料廣播；空間填充曲線； Voronoi 圖形

並列摘要

Data broadcasting is an effective way to disseminate information to a large amount of mobile clients in wireless mobile environments. Many information services can use such a technique to serve the clients, including Location-Based Services (LBS). The k nearest neighbors (kNN) search is one of the important location-based services. With such a search, the clients can get the points of interests (POI’s) around them. In this thesis, we propose kNN search protocols using data broadcasting in wireless mobile environments for an arbitrary k >1. We consider how the server generates the broadcast schedule and how the client can efficiently execute the query process. Without using an index node in the broadcast, the proposed protocol uses some addition information for each broadcast data in order to save the tuning time. To reduce the latency, when scheduling the data points, we consider different space-filling curves in order to keep the data locality. The experimental results indicate our protocols can explore fewer data points, thus leading to a less tuning time and latency.

並列關鍵字

Location-Based Services ； k Nearest Neighbors ； Data Broadcasting ； Space-filling Curves ； Voronoi Diagram

參考文獻

[1] Kian-Lee Tan and Beng Chin Ooi. DATA DISSEMINATION IN WIRELESS COMPUTING ENVIRONMENTS, 2000.

[4] Bugra Gedik, Aameek Singh, and Ling Liu. Energy efficient exact knn search in wireless broadcast environments. In Proceedings of the 12th annual ACM international workshop on geographic information systems, pages 137–146, 2004.

[5] Chuan-Ming Liu and Shu-Yu Fu. Effective protocols for knn search on broadcast multidimensional index trees. Information Systems, 33(1):18–35, 2008.

[6] Baihua Zheng, Jianliang Xu, Wang-Chien Lee, and Dik Lun Lee. Grid-partition index: a hybrid method for nearest-neighbor queries in wireless location-based services. The VLDB Journal, 15(1):21–39, 2006.

[7] Susanne Hambrusch, Chuan-Ming Liu, and Sunil Prabhakar. Broadcasting and querying multidimensional index trees in a multi-channel environment. Information Systems, 31(8):870–886, 2006.

國際替代計量

無線廣播環境下k個最近鄰居搜尋方法的探討

未授權

主題瀏覽