A Caltech Library Service

Distributed Kd-Trees for Ultra Large Scale Object Recognition

Aly, Mohamed and Munich, Mario and Perona, Pietro (2011) Distributed Kd-Trees for Ultra Large Scale Object Recognition. In: Proceedings of the British Machine Vision Conference 2011. BMVA Press , Durham, UK, Art. No. 40. ISBN 190172543X.

[img] PDF - Published Version
See Usage Policy.


Use this Persistent URL to link to this item:


Distributed Kd-Trees is a method for building image retrieval systems that can handle hundreds of millions of images. It is based on dividing the Kd-Tree into a “root subtree” that resides on a root machine, and several “leaf subtrees”, each residing on a leaf machine. The root machine handles incoming queries and farms out feature matching to an appropriate small subset of the leaf machines. Our implementation employs the MapReduce architecture to efficiently build and distribute the Kd-Tree for millions of images. It can run on thousands of machines, and provides orders of magnitude more throughput than the state-of-the-art, with better recognition performance. We show experiments with up to 100 million images running on 2048 machines, with run time of a fraction of a second for each query image.

Item Type:Book Section
Related URLs:
URLURL TypeDescription
Munich, Mario0000-0002-6665-7473
Perona, Pietro0000-0002-7583-5809
Additional Information:© 2011. The copyright of this document resides with its authors. It may be distributed unchanged freely in print or electronic forms. This work was supported by ONR grant #N00173-09-C-4005 and was implemented during an internship at Google Inc. The implementation of distributed Kd-Trees is pending a US patent GP-2478-00-US [4]. We would like to thank Ulrich Buddemeier and Alessandro Bissacco for allowing us to use their implementation. We would also like to thank James Philbin, Hartwig Adam, and Hartmut Neven for their valuable help.
Funding AgencyGrant Number
Office of Naval Research (ONR)N00173-09-C-4005
Record Number:CaltechAUTHORS:20190328-144424122
Persistent URL:
Official Citation:Mohamed Aly, Mario Munich and Pietro Perona. Distributed Kd-Trees for Ultra Large Scale Object Recognition. In Jesse Hoey, Stephen McKenna and Emanuele Trucco, Proceedings of the British Machine Vision Conference, pages 40.1-40.11. BMVA Press, September 2011.
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:94252
Deposited By: George Porter
Deposited On:28 Mar 2019 22:38
Last Modified:03 Oct 2019 21:02

Repository Staff Only: item control page