Article

Very Fast All k-Nearest Neighbors in Metric and Non Metric Spaces without Indexing

Authors:

Natalia Miranda,

María Fabiana Piccoli,

Nora ReyesAuthors Info & Claims

SISAP 2013: Proceedings of the 6th International Conference on Similarity Search and Applications - Volume 8199

Pages 300 - 311

https://doi.org/10.1007/978-3-642-41062-8_30

Published: 02 October 2013 Publication History

Abstract

Proximity queries consists in retrieving objects near a given query. To avoid a brute force scan over a large database, an index can be used. However, for some problems, indexes are mostly useless their running times are worst than sequential scan.

On the other hand, researchers have tried massively parallel hardware as GPGPU in the quest of faster query times. The results have been modest because current algorithms are cumbersome, while GPGPU architectures favor simple kernels, have a clear memory hierarchy and need close to zero cross-talk between processing units. We have engineered very fast algorithms for proximity queries taking into account this principles, all of them are presented in this paper.

In our approach no index is built, the cross-talk between threads is eliminated, and the higher faster levels of memory hierarchy are consistently used. The absence of data structures allows to use all the available memory for the database, and furthermore makes possible to do stream processing on very large data collections.

References

[1]

Zezula, P., Amato, G., Dohnal, V., Batko, M.: Similarity Search: The Metric Space Approach. Advances in Database Systems, vol. 32. Springer 2006

Digital Library

[2]

Samet, H.: Foundations of Multidimensional and Metric Data Structures. The Morgan Kaufmann Series in Computer Graphics and Geometric Modeling. Morgan Kaufmann Publishers Inc., San Francisco 2005

Digital Library

[3]

Chávez, E., Navarro, G., Baeza-Yates, R., Marroquín, J.: Searching in metric spaces. ACM Comput. Surv. 333, 273---321 2001

Digital Library

[4]

Benjamin, B., Navarro, G.: Probabilistic proximity searching algorithms based on compact partitions. Discrete Algorithms 21, 115---134 2004

Digital Library

[5]

Kirk, D., Hwu, W.: Programming Massively Parallel Processors, A Hands on Approach. Elsevier, Morgan Kaufmann 2010

Digital Library

[6]

Owens, J., Houston, M., Luebke, D., Green, S., Stone, J., Phillips, J.: GPU Computing, pp. 879---899. IEEE 2008

[7]

NVIDIA. Nvidia cuda compute unified device architecture, programming guide version 4.2. In: NVIDIA 2012

[8]

Barrientos, R., Gomez, J., Tenllado, C., Prieto, M.: Heap based k-nearest neighbor search on gpus. In: XXI Jornadas de Paralelismo, pp. 559---566 September 2010

[9]

Garcia, V., Debreuve, E., Barlaud, M.: Fast k nearest neighbor search using GPU. In: CVPR Workshop on Computer Vision on GPU CVGPU, Anchorage, Alaska, USA June 2008

[10]

Garcia, V., Debreuve, E., Nielsen, F., Barlaud, M.: k-nearest neighbor search: fast GPU-based implementations and application to high-dimensional feature matching. In: IEEE International Conference on Image Processing, Hong Kong September 2010

[11]

Kato, K., Hosino, T.: Solving k-nearest neighbor problem on multiple graphics processors. In: ACM ed. 2010 10th IEEE/ACM International Conference on Cluster, Cloud and Grid Computing, CCGRID, pp. 769---773 2010

Digital Library

[12]

Kuang, Q., Zhao, L.: A practical gpu based knn algorithm. In: International Symposium on Computer Science and Computational Technology ISC-SCT, pp. 151---155 2009

[13]

Liang, S., Liu, Y., Wang, C., Jian, L.: Design and evaluation of a parallel k-nearest neighbor algorithm on CUDA-enabled GPU. In: IEEE 2nd Symposium on Web Society SWS, p. 53 2010

[14]

Rozen, T., Boryczko, K., Alda, W.: Gpu bucket sort algorithm with applications to nearest-neighbour search. Journal of WSCG 161-3, 161---167 2008

[15]

Barrientos, R., Gomez, J., Tenllado, C., Prieto, M.: Query processing in metric spaces using gpus. In: XXII Jornadas de Paralelismo 2011

[16]

Barrientos, R.J., Gómez, J.I., Tenllado, C., Matias, M.P., Marin, M.: kNN Query Processing in Metric Spaces Using GPUs. In: Jeannot, E., Namyst, R., Roman, J. eds. Euro-Par 2011, Part I. LNCS, vol. 6852, pp. 380---392. Springer, Heidelberg 2011

Digital Library

[17]

Zhou, K., Hou, Q., Wang, R., Guo, B.: Real-time kd-tree construction on graphics hardware. In: ACM SIGGRAPH Asia, Papers, SIGGRAPH Asia 2008, pp. 126:1---126:11. ACM, New York 2008

Digital Library

[18]

Brown, S., Snoeyink, J.: Gpu nearest neighbors using a minimal kd-tree. In: Second Workshop on Massive Data Algorithmics MASSIVE 2010, Snowbird, Utah, USA June 2010

[19]

Qiu, D., May, S., Nüchter, A.: Gpu-accelerated nearest neighbor search for 3d registration. In: Fritz, M., Schiele, B., Piater, J.H. eds. ICVS 2009. LNCS, vol. 5815, pp. 194---203. Springer, Heidelberg 2009

Digital Library

[20]

Djinevski, S.R.L., Gusev, M.: Superlinear speedup for matrix multiplication in gpu devices. In: ICT Innovations 2012, pp. 285---294 2013

[21]

Navarro, G.: Searching in metric spaces by spatial approximation. The Very Large Databases Journal VLDBJ 111, 28---46 2002

Digital Library

[22]

Chavez, E., Ludueña, V., Reyes, N., Roggero, P.: Faster proximity searching with the distal sat 2012 submitted, draft

Cited By

Fort MSellarès J(2016)Efficient multiple bichromatic mutual nearest neighbor query processingInformation Systems10.1016/j.is.2016.07.00362:C(136-154)Online publication date: 1-Dec-2016
https://dl.acm.org/doi/10.1016/j.is.2016.07.003
Li SAmenta N(2015)Brute-Force k-Nearest Neighbors Search on the GPUProceedings of the 8th International Conference on Similarity Search and Applications - Volume 937110.1007/978-3-319-25087-8_25(259-270)Online publication date: 12-Oct-2015
https://dl.acm.org/doi/10.1007/978-3-319-25087-8_25
Canuto SSalles TGonçalves MRocha LRamos GGonçalves LRosa TMartins WLi JWang XGarofalakis MSoboroff ISuel TWang M(2014)On Efficient Meta-Level Features for Effective Text ClassificationProceedings of the 23rd ACM International Conference on Conference on Information and Knowledge Management10.1145/2661829.2662060(1709-1718)Online publication date: 3-Nov-2014
https://dl.acm.org/doi/10.1145/2661829.2662060

Recommendations

On indexing metric spaces using cut-regions
Abstract
After two decades of research, the techniques for efficient similarity search in metric spaces have combined virtually all the available tricks resulting in many structural index designs. As the representative state-of-the-art metric ...
Highlights
- The new cut-region formalism that is suitable for simplified description of compact metric regions.
On locality-sensitive indexing in generic metric spaces
SISAP '10: Proceedings of the Third International Conference on SImilarity Search and APplications

The concept of Locality-sensitive Hashing (LSH) has been successfully used for searching in high-dimensional data and a number of locality-preserving hash functions have been introduced. In order to extend the applicability of the LSH approach to a ...
Effective nearest neighbor indexing with the euclidean metric
CIKM '01: Proceedings of the tenth international conference on Information and knowledge management

The nearest neighbor search is an important operation widely-used in multimedia databases. In higher dimensions, most of previous methods for nearest neighbor search become inefficient and require to compute nearest neighbor distances to a large ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

SISAP 2013: Proceedings of the 6th International Conference on Similarity Search and Applications - Volume 8199

October 2013

330 pages

ISBN:9783642410611

Editors:
Nieves Brisaboa
Database Laboratory, Universidade da Coruña, Spain
,
Oscar Pedreira
Database Laboratory, Universidade da Coruña, Spain
,
Pavel Zezula
Faculty of Informatics, Masaryk University, Brno, Czech Republic

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 02 October 2013

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 13 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Fort MSellarès J(2016)Efficient multiple bichromatic mutual nearest neighbor query processingInformation Systems10.1016/j.is.2016.07.00362:C(136-154)Online publication date: 1-Dec-2016
https://dl.acm.org/doi/10.1016/j.is.2016.07.003
Li SAmenta N(2015)Brute-Force k-Nearest Neighbors Search on the GPUProceedings of the 8th International Conference on Similarity Search and Applications - Volume 937110.1007/978-3-319-25087-8_25(259-270)Online publication date: 12-Oct-2015
https://dl.acm.org/doi/10.1007/978-3-319-25087-8_25
Canuto SSalles TGonçalves MRocha LRamos GGonçalves LRosa TMartins WLi JWang XGarofalakis MSoboroff ISuel TWang M(2014)On Efficient Meta-Level Features for Effective Text ClassificationProceedings of the 23rd ACM International Conference on Conference on Information and Knowledge Management10.1145/2661829.2662060(1709-1718)Online publication date: 3-Nov-2014
https://dl.acm.org/doi/10.1145/2661829.2662060

View Options

View options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents