An Iterative Approach to Multi-Criteria Optimal Location Query

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：53

、訪客IP：3.147.72.11

姓名

韓伯維(Po-wei Harn) 查詢紙本館藏

畢業系所

資訊工程學系

論文名稱

(An Iterative Approach to Multi-Criteria Optimal Location Query)

相關論文

★ Dynamic Overlay Construction for Mobile Target Detection in Wireless Sensor Networks	★ 車輛導航的簡易繞路策略
★ 使用傳送端電壓改善定位	★ 利用車輛分類建構車載網路上的虛擬骨幹
★ Why Topology-based Broadcast Algorithms Do Not Work Well in Heterogeneous Wireless Networks?	★ 針對移動性目標物的有效率無線感測網路
★ 適用於無線隨意網路中以關節點為基礎的分散式拓樸控制方法	★ A Review of Existing Web Frameworks
★ 將感測網路切割成貪婪區塊的分散式演算法	★ 無線網路上Range-free的距離測量
★ Inferring Floor Plan from Trajectories	★ An Indoor Collaborative Pedestrian Dead Reckoning System
★ Dynamic Content Adjustment In Mobile Ad Hoc Networks	★ 以影像為基礎的定位系統
★ 大範圍無線感測網路下分散式資料壓縮收集演算法	★ 車用WiFi網路中的碰撞分析

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

[檢視]

[下載]

本電子論文使用權限為同意立即開放。
已達開放權限電子全文僅授權使用者為學術研究之目的，進行個人非營利性質之檢索、閱讀、列印。
請遵守中華民國著作權法之相關規定，切勿任意重製、散佈、改作、轉貼、播送，以免觸法。

摘要(中)

空間數據查詢像是最近鄰居與最佳位置查詢在文獻當中已被廣泛研究。在這篇論文中，我們提出一個多標準最佳位置查詢的迭代方法，這個迭代方法能應用在最佳位置選擇的更新問題。在提供關於更新問題的正式定義之後，我們提出一個增量更新的方法。這個方法以Minimum Overlapped Voronoi Diagram (MOVD) 新增刪除物件為基礎。除此之外，我們以數學來分析增量更新方法的複雜度。在效率評估上，我們的演算法是透過大量實驗數據來衡量。由結論可知，我們提出的演算法與最先進的解決方法相較之下，在點集合數量與物件種類少的時候，我們的演算法發揮較好執行效率。

摘要(英)

Spatial queries such as nearest neighbor and optimal location queries have been extensively studied in the literature. In this thesis, we present an iterative approach to Multi-Criteria Optimal Location Queries which can be applied on the updating problem of the optimal location selection. After providing a formal definition of the updating problem, we propose an incremental updating approach based on insertion and deletion of an object to the Minimum Overlapped Voronoi Diagram (MOVD). In addition, we analyze the the complexity of our solution for the updating problem. The performance of our algorithm is evaluated through extensive experiments. The results show that our algorithm runs efficiently compared with the state-of-the-art solution when the size of the point sets and the number of types are small.

關鍵字(中)

★ 多標準最佳位置查詢
★ 最佳位置選擇的更新問題
★ 多標準最佳位置查詢的迭代方法

關鍵字(英)

★ Multi-Criteria Optimal Location Query
★ Voronoi Diagram
★ Overlapped Voronoi Diagram
★ Minimum Overlapped Voronoi Diagram
★ Incremental Algorithm of Voronoi Diagram
★ Multi-criteria Optimal Location Query Updating Problem
★ MOVD Incremental Updating Approach
★ Incremental Updating Framework
★ Insertion Algorithm
★ Deletion Algorithm
★ Framework of the MOVD-based Solution
★ Fermat-Weber Point

論文目次

1 Introduction 1
2 Related Work 4
2.1 Optimal Location Queries . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.2 Skyline Queries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
3 Preliminaries 7
3.1 Voronoi Diagram . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
3.1.1 Ordinary Voronoi Diagram . . . . . . . . . . . . . . . . . . . . . . . 7
3.1.2 Weighted Voronoi Diagram . . . . . . . . . . . . . . . . . . . . . . . 8
3.2 Incremental Algorithm of Voronoi Diagram . . . . . . . . . . . . . . . . . . 9
3.3 Fermat-Weber Point . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
4 Problem Denition 11
4.1 Weighted Distance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
4.1.1 Weighted Distance of Two Points . . . . . . . . . . . . . . . . . . . 12
4.1.2 Weighted Distance from a Query Point to an Object Group . . . . 13
4.1.3 Minimum Weighted Distance from a Query Point to Object Groups 13
4.1.4 Multi-criteria Optimal Location Queries (MOLQ) . . . . . . . . . . 13
4.2 Update of Objects . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
4.2.1 Adding an Object . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
4.2.2 Deleting an Object . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
4.2.3 Changing the Weight of an Object . . . . . . . . . . . . . . . . . . 15
4.2.4 Multi-criteria Optimal Location Query Updating Problem . . . . . 15
4.3 Overlapped Voronoi Diagram and Minimum Overlapped Voronoi Diagram 15
iii
4.3.1 Overlapped Voronoi Diagram (OVD) . . . . . . . . . . . . . . . . . 15
4.3.2 Minimum Overlapped Voronoi Diagram (MOVD) . . . . . . . . . . 16
5 Incremental Updating Approach 17
5.1 Framework of the MOVD-based Solution . . . . . . . . . . . . . . . . . . . 17
5.2 A Method to the Multi-criteria Updating Problem . . . . . . . . . . . . . . 18
5.3 MOVD Incremental Updating Approach . . . . . . . . . . . . . . . . . . . 19
5.3.1 Incremental Updating Framework . . . . . . . . . . . . . . . . . . . 19
5.3.2 Insertion Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
5.3.3 Deletion Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
6 Performance Evaluation 29
6.1 Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
6.2 Simulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
6.2.1 Simulation Conguration . . . . . . . . . . . . . . . . . . . . . . . . 38
6.2.2 Simulation Results . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
7 Conclusions 42
Reference 43

參考文獻

[1] Mikhail J. Atallah and Yinian Qi. Computing all skyline probabilities for uncertain
data. In Proceedings of the Twenty-eighth ACM SIGMOD-SIGACT-SIGART Sym-
posium on Principles of Database Systems, PODS ′09, pages 279{287, New York,
NY, USA, 2009. ACM.
[2] Jean-Daniel Boissonnat and Christophe Delage. Convex hull and voronoi diagram of
additively weighted points. In Proceedings of the 13th Annual European Conference
on Algorithms, ESA′05, pages 367{378, Berlin, Heidelberg, 2005. Springer-Verlag.
[3] S. Borzsony, D. Kossmann, and K. Stocker. The skyline operator. In Data Engineer-
ing, 2001. Proceedings. 17th International Conference on, pages 421{430, 2001.
[4] Chee-Yong Chan, H. V. Jagadish, Kian-Lee Tan, Anthony K. H. Tung, and Zhenjie
Zhang. Finding k-dominant skylines in high dimensional space. In Proceedings of the
2006 ACM SIGMOD International Conference on Management of Data, SIGMOD
′06, pages 503{514, New York, NY, USA, 2006. ACM.
[5] R. Chandrasekaran and A. Tamir. Algebraic optimization: The fermat-weber location
problem. Mathematical Programming, 46(1-3):219{224, 1990.
[6] Haxe Community. Haxe language http://www.haxe.org/.
[7] Evangelos Dellis and Bernhard Seeger. Ecient computation of reverse skyline
queries. In Proceedings of the 33rd International Conference on Very Large Data
Bases, VLDB ′07, pages 291{302. VLDB Endowment, 2007.
[8] Pinliang Dong. Generating and updating multiplicatively weighted voronoi diagrams
43
for point, line and polygon features in gis. Comput. Geosci., 34(4):411{421, April
2008.
[9] Yang Du, Donghui Zhang, and Tian Xia. The optimal-location query. In Proceedings
of the 9th International Conference on Advances in Spatial and Temporal Databases,
SSTD′05, pages 163{180, Berlin, Heidelberg, 2005. Springer-Verlag.
[10] Yunjun Gao, Baihua Zheng, Gencai Chen, and Qing Li. Optimal-location-selection
query processing in spatial databases. Knowledge and Data Engineering, IEEE
Transactions on, 21(8):1162{1177, Aug 2009.
[11] Jin Huang, Bin Jiang, Jian Pei, Jian Chen, and Yong Tang. Skyline distance:
a measure of multidimensional competence. Knowledge and Information Systems,
34(2):373{396, 2013.
[12] Galina Jalal and Jakob Krarup. Geometrical solution to the fermat problem with
arbitrary weights. Annals of Operations Research, 123(1-4):67{104, 2003.
[13] Menelaos I. Karavelas and Mariette Yvinec. Dynamic additively weighted voronoi di-
agrams in 2d. In Proceedings of the 10th Annual European Symposium on Algorithms,
ESA ′02, pages 586{598, London, UK, UK, 2002. Springer-Verlag.
[14] Donald Kossmann, Frank Ramsak, and Steen Rost. Shooting stars in the sky: An
online algorithm for skyline queries. In Proceedings of the 28th International Con-
ference on Very Large Data Bases, VLDB ′02, pages 275{286. VLDB Endowment,
2002.
[15] Ken C. Lee, Wang-Chien Lee, Baihua Zheng, Huajing Li, and Yuan Tian. Z-sky: An
44
ecient skyline query processing framework based on z-order. The VLDB Journal,
19(3):333{362, June 2010.
[16] Xiang Lian and Lei Chen. Monochromatic and bichromatic reverse skyline search
over uncertain databases. In Proceedings of the 2008 ACM SIGMOD International
Conference on Management of Data, SIGMOD ′08, pages 213{226, New York, NY,
USA, 2008. ACM.
[17] Xingjie Liu, De-Nian Yang, Mao Ye, and Wang-Chien Lee. U-skyline: A new skyline
query for uncertain databases. Knowledge and Data Engineering, IEEE Transactions
on, 25(4):945{960, April 2013.
[18] Hua Lu and Christian S. Jensen. Upgrading uncompetitive products economically.
In Data Engineering (ICDE), 2012 IEEE 28th International Conference on, pages
977{988, April 2012.
[19] Lan Mu. Polygon characterization with the multiplicatively weighted voronoi dia-
gram*. The Professional Geographer, 56(2):223{239, 2004.
[20] Kasper Mullesgaard, Jens Laurits Pederseny, Hua Lu, and Yongluan Zhou. Ecient
Skyline Computation in MapReduce, pages 37{48. EDBT, 2014.
[21] Atsuyuki Okabe, Barry Boots, and Kokichi Sugihara. Spatial Tessellations: Concepts
and Applications of Voronoi Diagrams. John Wiley & Sons, Inc., New York, NY,
USA, 1992.
[22] Dimitris Papadias, Yufei Tao, Greg Fu, and Bernhard Seeger. An optimal and pro-
gressive algorithm for skyline queries. In Proceedings of the 2003 ACM SIGMOD
45
International Conference on Management of Data, SIGMOD ′03, pages 467{478,
New York, NY, USA, 2003. ACM.
[23] Dimitris Papadias, Yufei Tao, Greg Fu, and Bernhard Seeger. Progressive skyline
computation in database systems. ACM Trans. Database Syst., 30(1):41{82, March
2005.
[24] Jian Pei, Bin Jiang, Xuemin Lin, and Yidong Yuan. Probabilistic skylines on uncer-
tain data. In Proceedings of the 33rd International Conference on Very Large Data
Bases, VLDB ′07, pages 15{26. VLDB Endowment, 2007.
[25] Jianzhong Qi, Rui Zhang, L. Kulik, D. Lin, and Yuan Xue. The min-dist location
selection query. In Data Engineering (ICDE), 2012 IEEE 28th International Con-
ference on, pages 366{377, April 2012.
[26] Kian-Lee Tan, Pin-Kwang Eng, and Beng Chin Ooi. Ecient progressive skyline
computation. In Proceedings of the 27th International Conference on Very Large
Data Bases, VLDB ′01, pages 301{310, San Francisco, CA, USA, 2001. Morgan
Kaufmann Publishers Inc.
[27] Yufei Tao, Xiaokui Xiao, and Jian Pei. Subsky: Ecient computation of skylines in
subspaces. In Data Engineering, 2006. ICDE ′06. Proceedings of the 22nd Interna-
tional Conference on, pages 65{65, April 2006.
[28] Yehuda Vardi and Cun-Hui Zhang. A modied weiszfeld algorithm for the fermat-
weber location problem. Mathematical Programming, 90(3):559{566, 2001.
[29] E. Weiszfeld and Frank Plastria. On the point for which the sum of the distances to
n given points is minimum. Annals of Operations Research, 167(1):7{41, 2009.
46
[30] Tian Xia, Donghui Zhang, Evangelos Kanoulas, and Yang Du. On computing top-t
most in
uential spatial sites. In Proceedings of the 31st International Conference on
Very Large Data Bases, VLDB ′05, pages 946{957. VLDB Endowment, 2005.
[31] Xiaokui Xiao, Bin Yao, and Feifei Li. Optimal location queries in road network
databases. In Data Engineering (ICDE), 2011 IEEE 27th International Conference
on, pages 804{815, April 2011.
[32] Hyountaek Yong, Jin ha Kim, and Seung-Won Hwang. Skyline ranking for uncertain
data with maybe condence. In Data Engineering Workshop, 2008. ICDEW 2008.
IEEE 24th International Conference on, pages 572{579, April 2008.
[33] Donghui Zhang, Yang Du, Tian Xia, and Yufei Tao. Progressive computation of the
min-dist optimal-location query. In Proceedings of the 32Nd International Conference
on Very Large Data Bases, VLDB ′06, pages 643{654. VLDB Endowment, 2006.
[34] Ji Zhang, Wei-Shinn Ku, Min-Te Sun, Xiao Qin, and Hua Lu. Multi-Criteria Optimal
Location Query with Overlapping Voronoi Diagrams, pages 391{402. 2014.
[35] Wenjie Zhang, Xuemin Lin, Ying Zhang, Wei Wang, and J.X. Yu. Probabilistic
skyline operator over sliding windows. In Data Engineering, 2009. ICDE ′09. IEEE
25th International Conference on, pages 1060{1071, March 2009.

指導教授

孫敏德(Min-Te Sun)

審核日期

2015-8-6

推文