A Resource-Aware Nearest Neighbor Search Algorithm for K-Dimensional Trees
Author(s): Paul J, Stechele W, Kroehnert M, Asfour T, Oechslein B, Erhardt C, Schedel J, Lohmann D, Schröder-Preikschat W
Title edited volumes: Conference on Design and Architectures for Signal and Image Processing, DASIP
Publication year: 2013
Conference Proceedings Title: Proceedings of the 2013 Conference on Design & Architectures for Signal & Image Processing
Pages range: 80-87
Event: DASIP 2013
Event location: Cagliari, Italy
Start date of the event: 08/10/2013
End date of the event: 10/10/2013
Kd-tree search is widely used today in computer vision - for example in object recognition to process a large set of features and identify the objects in a scene. However, the search times vary widely based on the size of the data set to be processed, the number of objects present in the frame, the size and shape of the kd-tree, etc. Constraining the search interval is extremely critical for real-time applications in order to avoid frame drops and to achieve a good response time. The inherent parallelism in the algorithm can be exploited by using massively parallel architectures like many-core processors. However, the variation in execution time is more pronounced on such hardware (HW) due to the presence of shared resources and dynamically varying load situations created by applications running concurrently. In this work, we propose a new resource-aware nearest-neighbor search algorithm for kd-trees on many-core processors. The novel algorithm can adapt itself to the dynamically varying load on a many-core processor and can achieve a good response time and avoid frame drops. The results show significant improvements in performance and detection rate compared to the conventional approach while the simplicity of the conventional algorithm is retained in the new model.
FAU Authors / FAU Editors How to cite
APA: Paul, J., Stechele, W., Kroehnert, M., Asfour, T., Oechslein, B., Erhardt, C.,... Schröder-Preikschat, W. (2013). A Resource-Aware Nearest Neighbor Search Algorithm for K-Dimensional Trees. In Proceedings of the 2013 Conference on Design & Architectures for Signal & Image Processing (pp. 80-87).
MLA: Paul, Johny, et al. "A Resource-Aware Nearest Neighbor Search Algorithm for K-Dimensional Trees." Proceedings of the DASIP 2013, Cagliari, Italy 2013. 80-87.