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

Paul J, Stechele W, Kroehnert M, Asfour T, Oechslein B, Erhardt C, Schedel J, Lohmann D, Schröder-Preikschat W (2013)

Publication Type: Conference contribution

Publication year: 2013

Edited Volumes: Conference on Design and Architectures for Signal and Image Processing, DASIP

Pages Range: 80-87

Conference Proceedings Title: Proceedings of the 2013 Conference on Design & Architectures for Signal & Image Processing

Event location: Cagliari, Italy

ISBN: 979-10-92279-01-6

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.

Authors with CRIS profile

Involved external institutions

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

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). 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: Download