A Resource-Aware Nearest Neighbor Search Algorithm for K-Dimensional Trees

Conference contribution


Publication Details

Author(s): Paul J, Stechele W, Kroehnert M, Asfour T, Oechslein B, Erhardt CP, 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
ISBN: 979-10-92279-01-6
ISSN: 2164-9766


Abstract


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

Erhardt, Christoph Paul
Lehrstuhl für Informatik 4 (Verteilte Systeme und Betriebssysteme)
Lohmann, Daniel PD Dr.
Lehrstuhl für Informatik 4 (Verteilte Systeme und Betriebssysteme)
Oechslein, Benjamin
Lehrstuhl für Informatik 4 (Verteilte Systeme und Betriebssysteme)
Schedel, Jens Dr.
Lehrstuhl für Informatik 4 (Verteilte Systeme und Betriebssysteme)
Schröder-Preikschat, Wolfgang Prof. Dr.-Ing.
Lehrstuhl für Informatik 4 (Verteilte Systeme und Betriebssysteme)


External institutions with authors

Karlsruhe Institute of Technology (KIT)
Technische Universität München (TUM)


How to cite

APA:
Paul, J., Stechele, W., Kroehnert, M., Asfour, T., Oechslein, B., Erhardt, C.P.,... 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). Cagliari, Italy, IT.

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.

BibTeX: 

Last updated on 2019-25-08 at 07:10