Boundary Restricted Non-Overlapping Sphere Tree for Unified Multidimensional Solid Object Index
Author:
Affiliation:

Clc Number:

Fund Project:

  • Article
  • |
  • Figures
  • |
  • Metrics
  • |
  • Reference
  • |
  • Related
  • |
  • Cited by
  • |
  • Materials
  • |
  • Comments
    Abstract:

    To solve leakages as complex subdivision structures, high nodes overlap probability and poorsupporting on multi-dimensional entity object retrievals and the computation of existing spatial indexes. This paperpresents a boundary restricted non-overlapping sphere tree for a unified multidimensional solid object index. Byusing the outer product expression of a sphere in Geometric Algebra, an approach is explored for intersectionjudgments and point extractions between lines and planes and lines and spherical surfaces based on meet operators.The element subdivision of multi-dimensional object voxelization and the boundary restricted non-overlappingsphere-filling algorithm is developed to balance the conditions (e.g. granularity, non-overlapping subdivision ofobject voxelization), the duplication and approximate degrees of approaching objects. Furthermore, generating andupdating minimum boundary sphere and batch Neural Gas hierarchical clustering algorithm is also presented, andcontains a volume adjusted, index level system steady with the balance of each branch of a sphere tree. Next, withthe advantage of a clear geometric meaning, simple geometric relations calculation among spheres and dynamicalupdateable parameters, index structure can be dynamically generated and updated. Finally, the unifiedmultidimensional solid object index, a query mechanism of any location and range on and in the solid objects isproposed. The updated minimum boundary sphere construction, algorithm, and the volume adjusted adaptive batchNeural Gas hierarchical cluster algorithm are defined to quickly, robustly, relatively, and uniformly classify thefilling sphere. The simulation of different physical objects and performance comparison with a commonly usedsphere tree indexes suggest that the proposed index can effectively query any position or regions on and in the solidobjects, and support the nearest linkage distance and dynamical overlapping query under limited time restrictionswith high precision.

    Reference
    Related
    Cited by
Get Citation

俞肇元,袁林旺,罗文,胡勇,闾国年.边界约束的非相交球树实体对象多维统一索引.软件学报,2012,23(10):2746-2759

Copy
Share
Article Metrics
  • Abstract:
  • PDF:
  • HTML:
  • Cited by:
History
  • Received:August 23,2011
  • Revised:March 27,2012
  • Adopted:
  • Online: September 30,2012
  • Published:
You are the firstVisitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
Address:4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code:100190
Phone:010-62562563 Fax:010-62562533 Email:jos@iscas.ac.cn
Technical Support:Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063