臺灣博碩士論文加值系統

在無線行動裝置環境下，資料廣播是個有效服務大量行動裝置的方法，而再處理多查詢需求的服務時，天際線查詢扮演著重要的角色。但是單純的天際線查詢在行動裝置上提供所在地相關的服務是可能回傳沒有幫助的結果，如果該結果距離使用者過遠，即便是天際線查詢的結果卻無法實質上幫助使用者。為避免此種情形，我們結合天際線查詢與範圍查詢來回傳在該範圍內的天際線結果。同時考慮廣播環境上不同的資料排序方式對查詢的影響，並以延遲時間(latency)和收聽時間(tuning time)討論之間的效能差異。在研究中我們也去探討如何結合範圍查詢和天際線查詢的方法能得到較好的效能。

Data broadcasting is an effective way to disseminate information to a large amount of mobile clients in wireless mobile environment. The skyline search is one practical query in multi-criterion local based services. But skyline search may return some useless result which location is far away from query point. Although the data is skyline, it helpless for user. So our protocol not only consider the dominate relation-ship but also consider the distance between skyline result and query point. Our protocol combines range query and skyline query to reach the objective and return the skyline result which is also the range query result. This paper consider the influence of scheduling in data broadcasting cycle and discuss the latency and tuning time among different scheduling approaches. This paper also discuss how to combine range query and skyline query lead to better performance, and explain the correctness of our protocol.

第一章 前言 1
第二章 相關背景 5
2.1 無線廣播環境 5
2.2 Voronoi Diagram 6
2.3 Space-Filling Curves 7
2.4 Schedules of Data Broadcast 9
2.4.1 R-Schedule 9
2.4.2 Z-Schedule 9
2.4.3 Y-Schedule 10
2.4.4 Hilbert-Schedule 10
2.4.5 G-Schedule 11
2.5 Query Type 11
2.5.1 Range Query 12
2.5.2 Skyline Query 13
2.5.3 Range-Skyline Query 14
第三章 Broadcasting Range and Skyline Query Protocol 16
3.1 伺服器端 16
3.2 用戶端 16
3.2.1 範圍查詢 18
3.2.2 天際線查詢 19
3.2.3 範圍天際線查詢 21
第四章 實驗 23
4.1 實驗環境 23
4.2 不同資料量的影響 24
4.3 不同維度的影響 28
4.4 不同查詢半徑的影響 31
第五章 結論 35
參考文獻 36

[1]Dimitris Papadias, Yufei Tao, Greg Fu, and Bernhard Seeger. Progressive Skyline Computation in Database Systems. ACM Transactions on Database Systems (TODS), Volume 30, pp. 41-82, 2005.
[2]SeokJin Im, MoonBae Song, Jongwan Kim, Sang-Won Kang, Chong-Sun Hwang, and SeongHoon Lee. Cell-Based Distributed Index for Range Query Processing in Wireless Data Broadcast Systems. Knowledge-Based Intelligent In-formation and Engineering Systems Lecture Notes in Computer Science, Volume 4251, pp. 1139-1146, 2006.
[3]Jianting Zhang and Le Gruenwald. Optimizing Data Placement Over Wireless Broadcast Channel For Multi-Dimensional Range Query Processing. In Proceed-ings of 2004 IEEE International Mobile Data Management, 2004.
[4]Kai-An Yu and Chuan-Ming Liu. Effective Data Broadcasting Protocol for Loca-tion-Dependent Skyline Query. NTUT, 2013.
[5]Che-Lun Mak and Chuan-Ming Liu. A Study on KNN and RNN Searches in Mul-ti-channel Broadcast Environment. NTUT, 2012.
[6]k-nearest neighbors. http://en.wikipedia.org/wiki/K-nearest_neighbors_algorithm, 2014.
[7]James M. Kang, Mohamed F. Mokbel, Shashi Shekhar, Tian Xia and Donghui Zhang. Continuous Evaluation of Monochromatic and Bichromatic Reverse Nearest Neighbors. In Proceedings of 23rd IEEE International Conference on Data Engineering (ICDE 2007), 2007.
[8]Flip Korn and S. Muthukrishnan. Influence sets based on reverse nearest neigh-bor queries. In Proceedings of 2000 ACM SIGMOD international conference on Management of data, 2000.
[9]Wei-Chi Yeh, Chuan-Ming Liu and Kai-Yun Ho. A kNN Search Protocol Using a Voronoi Diagram in Wireless Broadcast Environments. In Proceedings of 6th IEEE International Conference on Mobile Adhoc and Sensor Systems (MASS 2009), 2009.
[10]Che-Lun Mak, Chuan-Ming Liu and Wei-Chi Yeh. Reverse Nearest Neighbors Search in Wireless Broadcast Environments. In Proceedings of 9th International Conference on Ubiquitous Intelligence & Computing and Autonomic & Trusted Computing (UIC/ATC 2012), 2012.
[11]Location-based service. http://en.wikipedia.org/wiki/Location-based_service, 2014.
[12]YouBike. http://www.youbike.com.tw/, 2014.
[13]Susanne Hambrusch, Chuan-Ming Liu and Sunil Prabhakar. Broadcasting and query multi-dimensional index trees in a multi-channel environment. Information Systems, Volume 32, Issue 8, pp. 870-886, 2006.
[14]Chuan-Ming Liu and Shu-Yu Fu. Effective protocols for kNN search on broad-cast multi-dimensional index trees. Information Systems, Volume 33, Issue 1, pp. 18-35, 2008.
[15]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 Very Large Data Bases Journal (VLDB Journal), Volume 15, Issue 1, pp. 21-39, 2006.