Not logged in.
Quick Search - Contribution
Contribution Details
| Type | Other Publication |
| Scope | Discipline-based scholarship |
| Title | Spatial data structures benchmarking framework |
| Organization Unit | |
| Authors |
|
| How Published | |
| Date | 2010 |
| Abstract Text | This paper is a documentation to a `Facharbeit' at the Visualization and Multimedia Lab at the University of Zürich. The task was to implement a framework in C++ to benchmark the performance of different spatial data structures for three dimensional point data. A focus was kept on a direct representation of the theory with clean object orientation and a clear separation of concerns, good maintainability and extensibility of the resulting code. Data is read in from vertices stored in a ply file and loaded into a structure as configured by the user. Various manipulation of this data is performed, such as accessing and moving points or finding neighbours. For benchmarking, the time these operations take is measured. This paper begins with a short introduction into the theoretical background of selected data structures, then the implementation is described by explaining the general approach and specific problems and their solutions. Finally, some initial benchmarking results are shown, that lead to the conclusion that there is no one best data structure among those tested (grid, bucket point region kd-tree and bucket sliding midpoint kd-tree), but the sliding midpoint kd-tree performs more predictably than the point region version. For actual use, the data structures would possibly have to be re-implemented, as their implementations for the benchmark framework is intended for relative performance comparison only, not for absolute efficiency. |
| PDF File |
Download
|
| Export |
BibTeX
|