在廣播環境下提供針對位置相關的天際線查詢協定

近年來，利用資料廣播方式提供服務備受關注。目前已經有許多利用資料廣播環境提供適地性服務的研究，包括點查詢，區域查詢，和最近鄰居搜索。在本文中，用戶和物件之間的距離是決定天際線重要的因素之一。例如，用戶希望找到離自己最近且最便宜的飯店。在這樣的查詢中，資料本身有兩種類型的資料屬性，空間和非空間屬性。非空間屬性值對於所有用戶是不變的，但空間屬性值會因為用戶位置不同而產生不同的值。因此，位於不同地點的用戶，所求出的答案也有所不同。為了提供使用者在任何時間及任何地點執行位置相關的天際線查詢，我們提出兩種索引結構，分別是AR*樹和R *樹；這兩種索引架構是基於傳統的R*樹。R*樹會直接將所有的屬性值索引起來，而AR*樹會先把空間屬性值索引完後，每個節點再額外附帶非空間的屬性值。在伺服器端，我們提供兩種最常見的廣播排程；使用者端則是提出有效的查詢演算法方法，讓使用者在任何時間及任何地點可以執行位置相關的天際線查詢。我們也研究在廣播頻道上，使用不同的方式排程R*樹。最後，我們提供實驗數據，比較查詢時間，聆聽時間，記憶體使用量。

關鍵字

資料廣播；天際線查詢；延遲時間；聆聽時間；記憶體使用量

並列摘要

Using data broadcasting to provide services has attracted much attention for years. Many types of location based services using data broadcasting have been studied, including point query, range query, and nearest neighbors search. In this paper, we consider the skyline query [4] where the location is an importation factor. For example, a user may want to find the nearest hotel having the lowest price. In such a query, there are two kinds of attributes, spatial and non-spatial attributes. The values of non-spatial attributes are static to all the users but the values of the spatial attributes sometimes are different to different users due to the locations of users. The results thus are different for different uses at different places. We consider two indexing structures based on R*-trees, named R*-tree and AR*-tree, for broadcasting data and propose effective approaches that allow the users to execute the location-dependent skyline query any time at any location. R*-tree indexes spatial and non-spatial attributes direct, and AR*-tree indexes spatial attributes and each node has additional non-spatial attributes. Different broadcast schedules on the broadcast index structures are considered. We last evaluate the proposed broadcasting protocols by performing the experiments and compare the performance in terms of the latency, tuning time, and memory usage when executing a query.

並列關鍵字

Data Broadcasting ； Skyline Query ； Latency ； Tuning Time ； Memory Usage

參考文獻

[2] S. Hambrusch, C.-M. Liu and S. Prabhakar, "Broadcasting and Querying Mul-ti-dimensional Index Trees in a Multi-channel Environment", To appear in Information Systems, vol. 31, Issue 8, pp. 870-886, 2006

[5] Dimitris Papadias, Yufei Tao, Greg Fu, and Bernhard Seeger, “Progressive Skyline Computation in Database Systems”, ACM Trans. Database Syst, vol. 30, issue 1, pp. 41-82, 2005

[8] N. Beckmann, H.-P. Kriegel, R. Schneider and B. Seeger, "The R*-tree: An Efficient and Robust Access Method for Points and Rectangles", 1990 ACM SIGMOD Interna-tional Conference on Management of Data, pp. 322-331, 1990.

[9] Chih-Jye Wang, Wei-Shinn Ku, “Efficient Evaluation of Skyline Queries in Wireless Data Broadcast Environments”, ACM SIGSPATIAL GIS 2012

[10] HaRim Jung, Yon Dohn Chung, Ling Liu, “Processing generalized k-nearest neighbor queries on a wireless broadcast stream”, Information Sciences, Volume 188, 1 April 2012, Pages 64-79

國際替代計量

在廣播環境下提供針對位置相關的天際線查詢協定

全文下載

主題瀏覽