计算机科学 ›› 2017, Vol. 44 ›› Issue (10): 171-176.doi: 10.11896/j.issn.1002-137X.2017.10.032
赵尔平,党红恩,刘炜
ZHAO Er-ping, DANG Hong-en and LIU Wei
摘要: 虚拟旅游中的3D点云数据特别庞大,批量索引成为了当今的研究热点。许多索引树存在兄弟结点空间区域重叠、不能实现细节层次索引、索引效率低等问题。为此,将点数据反射强度和细节层次技术引入R树,在改进R树的基础上提出LODR树。建树前,将点云数据进行排序、分组、去除空间重叠等预处理。树的每层设有不同反射强度阈值,把叶结点中满足阈值条件的索引记录沿父-祖父-曾祖父的家谱关系上移,并插入对应的非叶结点,利用该方法创建细节层次索引树。利用反射强度控制数据冗余,棱锥裁剪技术实现查询优化。实验结果表明,LODR树在细节层次索引、查询效率等方面具有明显优势。
[1] MERRY B,GAIN,MARAIS P.Fast in-place binning of laser range-scanned point sets[J].ACM Journal on Computing and Cultural Heritage,2013,6(3):1-19. [2] LIN J H,NOOSHABADI S,AHMADI M.Parallel Randomized KD-tree Forest on GPU Cluster for Image Descriptor Matching[C]∥ Proceedings of 2016 IEEE International Symposium on Circuits and Systems.New York:IEEE Press,2016:582-585. [3] RIZKI P N M,PARK J,OH S,et al.STR-Octree IndexingMethod for Processing LiDAR Data[C]∥ Proceedings of IEEE SENSORS 2015.New York:IEEE Press,2015:1-4. [4] 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,8(6):1503-1571. [5] HE Z W,WU C L,WANG C.Clustered Sorting R-tree:An Index for Multi-Dimensional Spatial Objects[C]∥ Proceedings of 2008 Fourth International Conference on Natural Computation.New York:IEEE Press,2008:348-351. [6] SUN W B,WANG Z P,LIU X L,et al.The Method for Indexing Global-scale 3D Vector Data with R-tree Based on Approxi-mate Prism[C]∥ Proceedings of The 18th International Confe-rence on Geoinformatics:GI-Science in Change.New York:IEEE Press,2010:1-4. [7] SHARIFZADEH M,SHAHABI C.VoR-Tree:Rtrees with Vo-ronoi Diagrams for Efficient Processing of Spatial Nearest Neighbor Queries[J].VLDB Journal,2010,3(1):1231-1242. [8] OSMANKOVIC D,SUPIC H,VELAGIC J.Performance andquality assessment of R-tree based nearest neighbour search in the scalar field mapping technique[C]∥Proceedings of the 2013 39th Annual Conference of the IEEE Industrial Electronics So-ciety.New York:IEEE Press,2013:2455-2459. [9] ACHAKEEV D,SEEGER B,WIDMAYER P.Sortbased Query-adaptive Loading of R-trees[C]∥ Proceedings of 2012 the 21st ACM International Conference on Information and Knowledge Management.New York:ACM,2012:2080-2084. [10] ZHANG J,PAN H,YUAN Z M.A Novel Spatial Index for Case based Geographic Retrieval[C]∥Proceedings of 2009 International Conference on Interaction Sciences.New York:ACM,2009:342-347. [11] PATEL P,GARG D.Perfect Hashing Base R-tree for Multiple Queries[C]∥ Proceedings of 2014 IEEE International Advance Computing Conference.New York:IEEE Press,2014:636-640. [12] GONG J,ZHANG H W.A Method for LOD Generation of 3D City Model Based on Extended 3D RTree Index[C]∥ Procee-dings of 2011 Eighth International Conference on Fuzzy Systems and Knowledge Discovery.New York:IEEE Press,2011:2004-2008. [13] LI J,JING N,SUN M Y.A Mechanism of Implementing Visuali-zation with Level of Detail at Multiscale[J].Journal of Software,2002,3(10):2037-2043.(in Chinese) 李军,景宁,孙茂印.多比例尺下细节层次可视化的实现机制[J].软件学报,2002,3(10):2037-2043. [14] DENG H Y,WU F,ZHAI R J,et al.R-Tree Index Structure for Multi-Scale Representation of Spatial Data[J].Chinese Journal of Computers,2009,2(1):177-184.(in Chinese) 邓红艳,武芳,翟仁健,等.一种用于空间数据多尺度表达的 R 树索引结构[J].计算机学报,2009,2(1):177-184. [15] ACHAKEEV D,SEIDEMANN M,SCHMIDT M,et al.Sort-based Parallel Loading of R-trees[C]∥ Proceedings of the 1st ACM SIGSPATIAL International Workshop on Analytics for Big Geospatial Data.New York:ACM,2012:62-70. [16] YOU S M,ZHANG J T,GRUENWALD L.Parallel SpatialQuery Processing on GPUs Using R-Trees [C]∥Proceedings of the 2nd ACM Sigspatial International Workshop on Analytics for Big Geospatial Data.New York:ACM,2013:23-31. [17] TAO Y F,YANG Y,HU X C,et al.Instance level worst-case query bounds on R-trees[J].The VLDB Journal,2014,3(4):591-607. [18] YIN K X,HUANG H,ZHANG H,et al.Morfit:InteractiveSurface Reconstruction from Incomplete Point Clouds with Curve-Driven Topology and Geometry Control[J].ACM Transa-ctions on Graphics,2014,33(6):1-12. [19] SONG J,LI T T,ZHU Z L.Research on I/O Cost of MapReduce Join[J].Journal of Software,2015,6(6):1438-1456.(in Chinese) 宋杰,李甜甜,朱志良.MapReduce连接查询的I/O代价研究[J].软件学报,2015,6(6):1438-1456. [20] WANG C K,MENG X F.Relational Query Techniques for Distributed Data Stream:A Survey[J].Chinese Journal of Compu-ters,2016,39(1):80-96.(in Chinese) 王春凯,孟小峰.分布式数据流关系查询技术研究[J].计算机学报,2016,39(1):80-96. |
No related articles found! |
|