This paper is focused on the analysis and comparison of different data structures for 3D space representation in autonomous exploration of large marine structures with UAS. The classical and widely used frontier exploration approach is applied: the frontier cells, which are the locations in the world representation map that are explored and unoccupied but has unexplored space in its vicinity, are of particular interest as they yield the highest information gain. Thus, the data structures have been compared from the point of view of their performance to be applied in the frontier exploration approach. The same algorithm has been run for the different data structures under different scenarios, both with synthetic and real datasets gathered with an UAS. The results are analyzed in detail taking into account the amount of iterations required and the number of computed frontier cells.