我們實作了一套專為地理研究人員使用的地理資訊系統，其主要管理的資料為LiDAR資料，統稱為點雲資料 (point cloud)，而且其資料量相當的龐大，這也使得我們在設計系統上有很大的挑戰。過去的研究都採單機環境管理，其運算資源和儲存空間都有限，實在不適合用來管理點雲資料，因此我們改採用master/slave分散式架構。在系統上的設計，主要有三個重要原件，第一，使用者介面，我們提供了使用者下達查詢的使用介面，方便使用者操作。第二，資料索引的設計，我們提出兩層式的索引架構，能讓查詢的處理加快。第三，我們採用資料庫的形式來儲存資料，因為相較於檔案系統，沒有檔案大小的限制，和支援多人同時查詢的好處。查詢處理的部份，我們主要處理的是range query和surface NN的查詢。其中較為困難的是surface NN的處理，我們是第一篇work探討在分散式環境下處理surface NN的問題。由於資料處理量相當龐大，礙於有限的記憶體和運算資源，我們提出了heuristic surface NN的solution。另外針對跨機器的表面距離計算，我們也提出了較為rough的heuristic surface distance的計算方法。而且在後面的實驗中也顯示了我們提出的heuristic solution的準確度可以高達80%以上。

We design a geographic information system (GIS) for those professional researchers in Geography. This system is implemented to manage the LiDAR data called point clouds, and the data size is huge. Therefore, it makes our system design more challenge. However, lots of the past works adapt the one-machine system to manage the point clouds. Due to its limited computation resources and limited storage, it is not appropriate for managing such huge data. So, we adapt the distributed system which is master/slave architecture. In our system design, there are three components. First, it’s the user interface. We design the interface for users to apply the query request easily. Second, it’s the indexing design. We propose the two level indexing to manage the data and make the query processing more efficient. Third, we use the database to store the huge data. Compared with the FileSystem, it doesn’t have the limitation of the storage size and support multiple queries concurrently. For the query processing, we mainly work on the range query processing and surface NN query processing. Among these two queries, the surface NN is more difficult. Moreover we are the first one to propose the algorithm of surface NN query in distributed system. Due to the huge size, limited memory space, and complex computation, we propose the solution of heuristic surface NN, and we also propose the rough method to do the heuristic surface distance computation when the two points are on the different machines. In addition, the experiments show that the accuracy of our heuristic solution can be more than 80%.

[1] Carter, J., Keil, S., Kirk, W., Lindy, B., Brian, H., Rebecca, M., and Jennifer, H. (2012). Lidar 101:
An introduction to lidar technology, data, and applications.
[2] Chen, J. and Han, Y. (1990). Shortest paths on a polyhedron. In Proceedings of the sixth annual
symposium on Computational geometry, pages 360-369. ACM.
[3] Deng, K., Shen, H. T., Xu, K., and Lin, X. (2006). Surface k-nn query processing. In 22nd Interna-
tional Conference on Data Engineering (ICDE'06), pages 78-78. IEEE.
[4] DeWitt, D. and Stonebraker, M. (2008). Mapreduce: A major step backwards. The Database Column,
1:23.
[5] DTM. http:==ngis:moea:gov:tw=moeaweb=Rinfo=KMSubItem:aspx?ID=20.
[6] Du Mouza, C., Litwin, W., and Rigaux, P. (2009). Large-scale indexing of spatial data in distributed
repositories: the sd-rtree. The VLDB Journal-The International Journal on Very Large Data Bases,
18(4):933-958.
[7] Elseberg, J., Borrmann, D., and Nuchter, A. (2013). One billion points in the cloud-an octree for
e cient processing of 3d laser scans. ISPRS Journal of Photogrammetry and Remote Sensing, 76:76-88.
[8] GeoHash. https:==en:wikipedia:org=wiki=Geohash.
[9] GIS. https:==en:wikipedia:org=wiki=Geographicn informationn system.
[10] Hinks, T., Carr, H., and Laefer, D. F. (2009). Flight optimization algorithms for aerial lidar capture
for urban infrastructure model generation. Journal of Computing in Civil Engineering, 23(6):330-339.
[11] Hsieh, Y.-C. Introduction to DTM. http:==twgeoref:moeacgs:gov:tw=GipOpenWeb=wSite=ct?
xItem=140861&ctNode=1233&mp=105.
[12] Koudas, N., Ooi, B. C., Tan, K.-L., and Zhang, R. (2004). Approximate nn queries on streams
with guaranteed error/performance bounds. In Proceedings of the Thirtieth international conference
on Very large data bases-Volume 30, pages 804-815. VLDB Endowment.
[13] Laefer, D. F. and Pradhan, A. R. (2006). Evacuation route selection based on tree-based hazards
using light detection and ranging and gis. Journal of transportation engineering, 132(4):312-320.
[14] MpichCluster. https:==help:ubuntu:com=community=MpichCluster.
[15] Otepka, J., Mandlburger, G., and Karel, W. (2012). The opals data manager-e cient data management
for processing large airborne laser scanning projects. Proceedings of the ISPRS Annals of the
Photogrammetry, Melbourne, Australia, 25:153-159.
[16] RAID. https:==zh:wikipedia:org=wiki=RAID.
[17] Sabo, N., Beaulieu, A., B elanger, D., Belzile, Y., and Pich e, B. (2014). The geohashtree: a multiresolution
data structure for the management of point clouds. Technical notes, 4.
[18] SchoN, B., Mosa, A. S. M., Laefer, D. F., and Bertolotto, M. (2013). Octree-based indexing for 3d
pointclouds within an oracle spatial dbms. Computers & Geosciences, 51:430-438.
[19] Shahabi, C., Tang, L.-A., and Xing, S. (2008). Indexing land surface for e cient knn query. Pro-
ceedings of the VLDB Endowment, 1(1):1020-1031.
[20] Sulebak, J. (2000). Applications of digital elevation models. DYNAMAP Project, page 11.
[21] Tsatsanifos, G., Sacharidis, D., and Sellis, T. (2013). Index-based query processing on distributed
multidimensional data. GeoInformatica, 17(3):489-519.
[22] Xing, S., Shahabi, C., and Pan, B. (2009). Continuous monitoring of nearest neighbors on land
surface. Proceedings of the VLDB Endowment, 2(1):1114-1125.
[23] Xu, K., Zhou, X., and Lin, X. (2004). Direct mesh: a multiresolution approach to terrain visualization.
In Data Engineering, 2004. Proceedings. 20th International Conference on, pages 766-776.
IEEE.
[24] Zhu, Q., Gong, J., and Zhang, Y. (2007). An e cient 3d r-tree spatial index method for virtual
geographic environments. ISPRS Journal of Photogrammetry and Remote Sensing, 62(3):217-224.