Ultra-fast similarity search using ternary content addressable memory

Anat Bremler-Barr, Yotam Harchol, David Hay, Yacov Hel-Or

نتاج البحث: فصل من :كتاب / تقرير / مؤتمرمنشور من مؤتمرمراجعة النظراء

ملخص

Similarity search, and specifically the nearest-neighbor search (NN) problem is widely used in many fields of computer science such as machine learning, computer vision and databases. However, in many settings such searches are known to suffer from the notorious curse of dimensionality, where running time grows exponentially with d. This causes severe performance degradation when working in high-dimensional spaces. Approximate techniques such as locality-sensitive hashing [2] improve the performance of the search, but are still computationally intensive. In this paper we propose a new way to solve this problem using a special hardware device called ternary content addressable memory (TCAM). TCAM is an associative memory, which is a special type of computer memory that is widely used in switches and routers for very high speed search applications. We show that the TCAM computational model can be leveraged and adjusted to solve NN search problems in a single TCAM lookup cycle, and with linear space. This concept does not suffer from the curse of dimensionality and is shown to improve the best known approaches for NN by more than four orders of magnitude. Simulation results demonstrate dramatic improvement over the best known approaches for NN, and suggest that TCAM devices may play a critical role in future large-scale databases and cloud applications.

اللغة الأصليةالإنجليزيّة
عنوان منشور المضيف11th International Workshop on Data Management on New Hardware, DaMoN 2015 - In conjunction with the ACM SIGMOD/PODS Conference
المحررونMartin Kersten, Ippokratis Pandis
رقم المعيار الدولي للكتب (الإلكتروني)9781450336383
المعرِّفات الرقمية للأشياء
حالة النشرنُشِر - 31 مايو 2015
الحدث11th International Workshop on Data Management on New Hardware, DaMoN 2015 - Melbourne, أستراليا
المدة: ١ يونيو ٢٠١٥ → …

سلسلة المنشورات

الاسم11th International Workshop on Data Management on New Hardware, DaMoN 2015 - In conjunction with the ACM SIGMOD/PODS Conference

!!Conference

!!Conference11th International Workshop on Data Management on New Hardware, DaMoN 2015
الدولة/الإقليمأستراليا
المدينةMelbourne
المدة١/٠٦/١٥ → …

All Science Journal Classification (ASJC) codes

  • !!Computer Networks and Communications
  • !!Hardware and Architecture
  • !!Software

بصمة

أدرس بدقة موضوعات البحث “Ultra-fast similarity search using ternary content addressable memory'. فهما يشكلان معًا بصمة فريدة.

قم بذكر هذا