Computer Science

Computer Science ›› 2018, Vol. 45 ›› Issue (9): 213-219.doi: 10.11896／j.issn.1002-137X.2018.09.035

• Software & Database Technology • Previous Articles     Next Articles

Spatial Index of 3D Point Cloud Data Based on Spark

ZHAO Er-ping1, MENG Xiao-feng2   

  1. School of Information Engineering,Xizang Minzu University,Xianyang,Shaanxi 712082,China1
    School of Information,Renmin University of China,Beijing 100872,China2
  • Received:2017-08-04 Online:2018-09-20 Published:2018-10-10

PDF (PC)

1107

Abstract: Two level spatial index based on R tree was presented according to the problem that spark engine doesn’t support multi-dimensional spatial query,that is,the R subtree is created on each worker node,and these subtrees are used as children to create the R tree on the master node.Memory replacement granularity of LRU algorithm is coarse,and the result is not accurate enough.For this reason,the method of memory replacement based on data usage weight was proposed.The ratio of actual used amount of data and its total amount is used as replacement weight.The method stores the hot scene data in RDD form into memory and improves the query efficiency based on memory.According to the visual principle of far thick and near fine,the level of detail query was presented.The point cloud data that best represent the object characteristics are firstly transmitted or the simplified model data are only transmitted to the client,so as to solve the problem of insufficient network bandwidth and data loading delay.Experimental results show that the proposed method can effectively solve the problem of multi-dimensional spatial query on spark,and the query efficiency is improved obviously.

Key words: 3D point cloud data, Data usage weight, Level of detail, Multi-dimensional spatial index, Spark, Virtual tourism

CLC Number: 

  • TP392
[1]ELWIRA H,JERZY W,ROBERT S,et al.Color based Algo-rithm for Automatic Merging of Multiview 3D Point Clouds[J].ACM Journal on Computing and Cultural Heritage,2014,7(3):1-21.
[2]RUFAEL M,PABLO C.MP3DG-PCC Open Source Software
Framework for Implementation and Evaluation of Point Cloud Compression[C]∥Proceedings of the 2016 ACM Conference on Multimedia Conference.New York:ACM,2016:1222-1226.
[3]ROMULO G,TOMV T,KOSTIS K,et al.Aspatial column
store to triangulate the Netherlands on the fly[C]∥Proceedings of the 24th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems.NewYork:ACM,2016:1-4.
[4]ZHANG R,QI J Z,MARTIN S,et al.Towardsa Painless Index for Spatial Objects[J].ACM Transactions on Database Systems,2014,39(3):1-19.
[5]RIZKI P N M,PARK J S,OH S,et al.STR-Octree Indexing Method for Processing LiDAR Data[C]∥Proceedings of IEEE SENSORS.NewYork:IEEE Press,2015:1-4.
[6]YANG H,QI W T,GAO X F.Efficient R-Tree Based Indexing Scheme for Server-Centric Cloud Storage System[J].IEEE Transactions on Knowledge and Data Engineering,2016,28(6):1503-1571.
[7]DENG Y C,JACK C,CHENG P.Automatic Transformation of Different Levels of Detail in 3D GIS City Models in CityGML[J].International Journal of 3-D Information Modeling,2015,4(3):1-21.
[8]NICHOLAS F P,ANKIT S,PETER S,et al.A Novel Level-of-Detail Technique for Virtual City Environments[C]∥Procee-dings of the 21st International Conference on Web3D Technology.New York:ACM,2016:183-184.
[9]DENG H Y,WU F,ZHAI R J,et al.R-TreeIndex Structure for Multi-Scale Representation of Spatial Data[J].Chinese Journal of Computers,2009,32(1):177-184.(in Chinese)
邓红艳,武芳,翟仁健,等.一种用于空间数据多尺度表达的 R 树索引结构[J].计算机学报,2009,32(1):177-184.
[10]SONG B Y,WANG J L,WANG Y,et al.Optimized Storage Strategy Research of HDFS Based on Vandermonde Code [J].Chinese Journal of Computers,2015,38(9):1825-1837.(in Chinese)
宋宝燕,王俊陆,王妍,等.基于范德蒙码的HDFS优化存储策略研究[J].计算机学报,2015,38(9):1825-1837.
[11]VINITHA R G,NIKHIL T.Indexing HDFS Data in PDW:Splitting the data from the index[C]∥Proceedings of the 40th International Conference on Very Large Database.NewYork:PVLDB,2014:1520-1528.
[12]JAMES G,SHA N H,LIANGD.Large Scale Distributed Data Science from Scratch using Apache Spark 2.0[C]∥Proceedings of the 26th International Conference on World Wide Web Companion.New York:ACM,2017:955-957.
[13]RANDALL T W,MICHAEL B P,SARA M A,et al.Spatial indexing and analytics on Hadoop[C]∥Proceedings of the 22nd ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems.NewYork:ACM,2014:73-82.
[14]ZHONG Y Q,ZHU X M,FANG J Y.Elastic and Effective Spatio-Temporal Query Processing Scheme on Hadoop[C]∥Proceedings of the 1st ACM SIGSPATIAL International Workshop on Analyticsfor Big GeospatialData.NewYork:ACM,2012:33-42.
[15]AHMED E,MOHAMED F M.A Demonstration of SpatialHadoop:AnEfficientMapReduce Framework for Spatial Data[J].PVLDB Endowment,2013,6(12):1230-1233.
[16]WAIL Y A,SATTAM A,MICHAEL J C.Largescale Complex Analytics on Semi-structured Datasets using AsterixDB and Spark[J].Proceedings of the Vidb Endowment,2016,9(13):1585-1588.
[17]GU J P,WU Z B,LI Y L,et al.Parallel Optimization of Pixel Purity Index Algorithm for Hyperspectral Unmixing Based on Spark[C]∥Proceedings of Third International Conference on Advanced Cloud and Big Data.New York:IEEE Press,2015:159-166.
[18]WANG F Y,WANG X Z,CUI W J,et al.Distributed retrieval for massive remote sensing image metadata on spark[C]∥Proceedings of 2016 IEEE International Geoscience and Remote Sensing Symposium.New York:IEEE Press,2016:5909-5912.
[19]ZHANG R,QI J Z,MARTIN S,et al.Towards a Painless Index for Spatial Objects[J].ACM Transactions on Database Systems,2014,39(3):1-41.
[20]PARTH P,DEEPAK G.Perfect Hashing Base R-tree for Multiple Queries[C]∥Proceedings of 2014 IEEE International Advance Computing Conference.NewYork:IEEE Press,2014:636-640.
[21]BIAN C,YU J,YING C T,et al.Self-Adaptive Strategy for
Cache Management in Spark[J].Acta Electronica Sinica,2017,45(2):278-284.(in Chinese)
卞琛,于炯,英昌甜,等.并行计算框架Spark的自适应缓存管理策略[J].电子学报,2017,45(2):278-284.
[22]SHI J W,QIU Y J,UMAR F M,et al.Clash of the Titans:Map-Reduce vs.Spark for Large Scale Data Analytics [C]∥Procee-dings of the 41st International Conference on Very Large Database.New York:PVLDB,2015:2110-2121.
[1] DAI Hong-liang, ZHONG Guo-jin, YOU Zhi-ming , DAI Hong-ming. Public Opinion Sentiment Big Data Analysis Ensemble Method Based on Spark [J]. Computer Science, 2021, 48(9): 118-124.
[2] YU Jian-ye, QI Yong, WANG Bao-zhuo. Distributed Combination Deep Learning Intrusion Detection Method for Internet of Vehicles Based on Spark [J]. Computer Science, 2021, 48(6A): 518-523.
[3] YANG Zong-lin, LI Tian-rui, LIU Sheng-jiu, YIN Cheng-feng, JIA Zhen, ZHU Jie. Streaming Parallel Text Proofreading Based on Spark Streaming [J]. Computer Science, 2020, 47(4): 36-41.
[4] ZHU An-qing, LI Shuai, TANG Xiao-dong. Parallel FP_growth Association Rules Mining Method on Spark Platform [J]. Computer Science, 2020, 47(12): 139-143.
[5] YU Xin-yi, SHI Tian-feng, TANG Quan-rui, YIN Hui-wu, OU Lin-lin. Industrial Equipment Management System for Predictive Maintenance [J]. Computer Science, 2020, 47(11A): 667-672.
[6] DENG Ding-sheng. Application of Improved DBSCAN Algorithm on Spark Platform [J]. Computer Science, 2020, 47(11A): 425-429.
[7] JIA Ning, LI Ying-da. Construction of Personalized Health Monitoring Platform Based on Intelligent Wearable Device [J]. Computer Science, 2019, 46(6A): 566-570.
[8] ZHAO Jun-xian, YU Jian. Optimization of Spark RDD Based on Non-serialization Native Storage [J]. Computer Science, 2019, 46(5): 143-149.
[9] WEI Liang, LIN Zi-yu, LAI Yong-xuan. DFTS:A Top-k Skyline Query for Large Datasets [J]. Computer Science, 2019, 46(5): 150-156.
[10] CUI Guang-fan, XU Li-jie, LIU Jie, YE Dan, ZHONG Hua. Design and Implementation of Distributed Full-text Search Framework Based on Spark SQL [J]. Computer Science, 2018, 45(9): 104-112.
[11] LIAO Hu-sheng, HUANG Shan-shan, XU Jun-gang, LIU Ren-feng. Survey on Performance Optimization Technologies for Spark [J]. Computer Science, 2018, 45(7): 7-15.
[12] SHI Jin-ping,LI Jin,HE Feng-zhen. Diversity Recommendation Approach Based on Social Relationship and User Preference [J]. Computer Science, 2018, 45(6A): 423-427.
[13] SHI Jing-qi, YANG Geng, SUN Yan-jun, BAI Shuang-jie and MIN Zhao-e. Efficient Parallel Algorithm of Fully Homomorphic Encryption Supporting Operation of Floating-point Number [J]. Computer Science, 2018, 45(5): 116-122.
[14] PENG Zheng, WANG Ling-jiao, GUO Hua. Parallel Text Categorization of Random Forest [J]. Computer Science, 2018, 45(12): 148-152.
[15] FENG Gui-lan, ZHOU Wen-gang. Spark-based Parallel Outlier Detection Algorithm of K-nearest Neighbor [J]. Computer Science, 2018, 45(11A): 349-352.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
渝ICP备16013121号-4
Add:18# Honghu West Rd., Yubei ,Chongqing,China    Post Code: 401121
Tel: 023-63500828/023-67039612/023-67039623
E-mail: jsjkx12@163.com
Powered by Beijing Magtech Co., Ltd.