Nội dung được dịch bởi AI, chỉ mang tính chất tham khảo
Thuật toán toàn diện dựa trên GPU xử lý truy vấn kNN
Tóm tắt
Truy vấn kNN (k-láng giềng gần nhất) hiệu quả rất hữu ích, trong số các lĩnh vực khác, trong việc truy xuất thông tin đa phương tiện, khai thác dữ liệu và các vấn đề nhận dạng mẫu. Một hàm khoảng cách xác định độ tương đồng giữa các đối tượng với một đối tượng truy vấn kNN cho trước. Do việc xác định khoảng cách giữa bất kỳ cặp đối tượng nào (tức là, các vectơ trong không gian nhiều chiều) được biết là một phép toán đắt đỏ về mặt tính toán, việc sử dụng các kỹ thuật tính toán song song là một cách hiệu quả để giảm thời gian xử lý đến các giá trị chấp nhận được trong các cơ sở dữ liệu lớn. Trong công trình hiện tại, chúng tôi đề xuất các phương pháp mới sử dụng GPU để giải quyết các truy vấn kNN bằng cách sử dụng các thuật toán toàn diện dựa trên Sắp xếp Chọn, Sắp xếp Nhanh và các thuật toán tiên tiến nhất. Chúng tôi cho thấy rằng phương pháp tốt nhất phụ thuộc vào giá trị k của truy vấn kNN và đạt được tốc độ xử lý nhanh hơn tới 86.4 lần so với đối tác tuần tự. Chúng tôi cũng đề xuất một thuật toán đa lõi để làm tham chiếu cho các thí nghiệm và một thuật toán lai kết hợp các thuật toán đã đề xuất với một phương pháp dựa trên heap hiện đại, trong đó hiệu suất tốt nhất được đạt được với các giá trị k cao. Chúng tôi cũng mở rộng các thuật toán của mình để có thể xử lý các cơ sở dữ liệu lớn không thể chứa trong bộ nhớ GPU và hiệu suất không bị suy giảm khi kích thước cơ sở dữ liệu tăng lên.
Từ khóa
#kNN #GPU #thuật toán toàn diện #Sắp xếp Chọn #Sắp xếp Nhanh #hiệu suấtTài liệu tham khảo
Cover T, Hart P (1967) Nearest neighbor pattern classification. IEEE Trans Inf Theory 13(1):21–27
Deng Z, Zhu X, Cheng D, Zong M, Zhang S (2016) Efficient knn classification algorithm for big data. Neurocomputing 195:143–148
Mic V, Novak D, Zezula P (2016) Speeding up similarity search by sketches. Springer, Cham. doi:10.1007/978-3-319-46759-7_19
Navarro G, Uribe-Paredes R (2011) Fully dynamic metric access methods based on hyperplane partitioning. Inf Syst 36(4):734–747. doi:10.1016/j.is.2011.01.002
Novak D, Batko M, Zezula P (2011) Metric index: an efficient and scalable solution for precise and approximate similarity search. Inf Syst 36(4):721–733
Keogh E, Mueen A (2010) Curse of dimensionality. In: Encyclopedia of Machine Learning. Springer US, pp 257–258. doi:10.1007/978-0-387-30164-8_192
GPU computing. http://www.nvidia.com/object/what-is-gpu-computing.html
Cai Y, See S (eds) (2016) GPU computing and applications. Springer, Berlin
Diouri MEM, Dolz MF, Glück O, Lefèvre L, Alonso P, Catalán S, Mayo R, Quintana-Ortí ES (2014) Assessing power monitoring approaches for energy and power analysis of computers. Sustain Comput Inf Syst 4(2):68–82
Mittal S, Vetter JS (2014) A survey of methods for analyzing and improving gpu energy efficiency. ACM Comput Surv 47(2):19:1–19:23. doi:10.1145/2636342
NVIDIA: Nvidia’s next generation cuda compute architecture: Fermi. Tech. rep. (2010)
CUDA: compute unified device architecture. 2007 NVIDIA Corporation. http://developer.nvidia.com/object/cuda.html
NVIDIA corporation: CUDA C best practices guide, 7.5 edn (2015)
Knuth DE (1997) The art of computer programming, vol 3, 3rd edn. Addison-Wesley, Reading
Hoare CA (1962) Quicksort. Comput J 5(1):10–16
Aha DW, Kibler D, Albert M (1991) Instance-based learning algorithms. Mach Learn 6(1):37–66
Barrientos R, Gómez J, Tenllado C, Prieto M, Marin M (2011) knn query processing in metric spaces using gpus. In: 17th International European Conference on Parallel and Distributed Computing (Euro-Par 2011), pp 380–392
Cayton L (2012) Accelerating nearest neighbor search on manycore systems. In: Parallel Distributed Processing Symposium (IPDPS), 2012 IEEE 26th International, pp 402–413. doi:10.1109/IPDPS.2012.45
Pan J, Manocha D (2011) Fast gpu-based locality sensitive hashing for k-nearest neighbor computation. In: Proceedings of the 19th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, GIS ’11. ACM, New York, NY, USA, pp 211–220. doi:10.1145/2093973.2094002
Samet H (2005) Foundations of multidimensional and metric data structures. Morgan Kaufmann Publishers Inc., San Francisco
Brisaboa NR, Fariña A, Pedreira O, Reyes N (2006) Similarity search using sparse pivots for efficient multimedia information retrieval. In: ISM, pp 881–888
Chávez E, Navarro G (2005) A compact space decomposition for effective metric indexing. Pattern Recognit Lett 26(9):1363–1376
Garcia V, Debreuve E, Barlaud M (2008) Fast k nearest neighbor search using gpu. In: Computer Vision and Pattern Recognition Workshop 0, pp 1–6. doi:10.1109/CVPRW.2008.4563100
Kuang Q, Zhao L (2009) A practical gpu based knn algorithm. Huangshan, China, pp 151–155
Cederman D, Tsigas P (2009) Gpu-quicksort: A practical quicksort algorithm for graphics processors. J Exp Algorithmics 14:14–124. doi:10.1145/1498698.1564500
Beliakov G, Li G (2012) Improving the speed and stability of the k-nearest neighbors method. Pattern Recognit Lett 33(10):1296–1301. doi:10.1016/j.patrec.2012.02.016
Beliakov G, Johnstone M, Nahavandi S (2012) Computing of high breakdown regression estimators without sorting on graphics processing units. Computing 94(5):433–447. doi:10.1007/s00607-011-0183-7
CUB library v1.7.0. http://nvlabs.github.io/cub/index.html
Barrientos RJ, Gómez JI, Tenllado C, Matias MP, Marin M (2013) Range query processing on single and multi GPU environments. Comput Electr Eng 39(8):2656–2668. doi:10.1016/j.compeleceng.2013.05.012
Levenshtein V (1966) Binary codes capable of correcting deletions, insertions, and reversals. Sov Phys Dokl 10:707–710
Bolettieri P, Esuli A, Falchi F, Lucchese C, Perego R, Piccioli T, Rabitti F (2009) Cophir: a test collection for content-based image retrieval. CoRR arXiv:0905.4627. http://cophir.isti.cnr.it
MUFIN web site: multi-feature indexing network. http://mufin.fi.muni.cz/imgsearch/similar
Novak, D., Batko, M., Zezula, P.: Generic similarity search engine demonstrated by an image retrieval application. In: 32nd ACM SIGIR Conference on Research and Development in Information Retrieval. ACM, Boston, MA, USA, p 840 (2009)
Barrientos R, Gómez J, Tenllado C, Prieto M, Zezula P (2013) Multi-level clustering on metric spaces using a multi-gpu platform. In: 19th International European Conference on Parallel and Distributed Computing (Euro-Par 2013), LNCS, vol 8097. Springer, Aachen, Germany, pp 216–228. doi:10.1007/978-3-642-40047-6_24
Real query log from the similarity search engine mufin. http://www.drago-hpc.cl/research.html
Stupar A, Michel S, Schenkel R (2010) Rankreduce processing k-nearest neighbor queries on top of mapreduce. In: Proceedings of the 8th Workshop on Large-Scale Distributed Systems for Information Retrieval, pp 13–18
Uribe-Paredes R, Valero-Lara P, Arias E, Sánchez JL, Cazorla D (2011) A gpu-based implementation for range queries on spaghettis data structure. In: Computational Science and Its Applications (ICCSA 2011), vol 6782. Lecture Notes in Computer Science. Springer, Santander, Spain, pp 615–629
Gil-Costa V, Barrientos RJ, Marin M, Bonacic C (2010) Scheduling metric-space queries processing on multi-core processors. In: 18th Euromicro Conference on Parallel. Distributed and Network-based Processing (PDP 2010). IEEE Computer Society, Pisa, Italy, pp 187–194
Uribe-Paredes R, Arias E, Sánchez JL, Cazorla D, Valero-Lara P (2012) Improving the performance for the range search on metric spaces using a multi-gpu platform. In: 23rd International Conference on Database and Expert Systems Applications (DEXA 2012), LNCS, vol 7447. Springer, pp 442–449
Tesla C2050/C2070 GPU computing processor. http://www.nvidia.co.uk/object/product_tesla_C2050_C2070_uk.html
Tesla M2050/M2070 GPU computing processor. http://www.nvidia.co.uk/object/product_tesla_M2050_M2070_uk.html
Lichman M (2013) UCI machine learning repository. http://archive.ics.uci.edu/ml
Watts up? .net meter. http://www.wattsupmeters.com/secure/products.php?pn=0&wai=0&spec=2