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
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - 31 מאי 2015
אירוע11th International Workshop on Data Management on New Hardware, DaMoN 2015 - Melbourne, אוסטרליה
משך הזמן: 1 יוני 2015 → …

סדרות פרסומים

שם11th International Workshop on Data Management on New Hardware, DaMoN 2015 - In conjunction with the ACM SIGMOD/PODS Conference

כנס

כנס11th International Workshop on Data Management on New Hardware, DaMoN 2015
מדינה/אזוראוסטרליה
עירMelbourne
תקופה1/06/15 → …

ASJC Scopus subject areas

  • ???subjectarea.asjc.1700.1705???
  • ???subjectarea.asjc.1700.1708???
  • ???subjectarea.asjc.1700.1712???

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'Ultra-fast similarity search using ternary content addressable memory'. יחד הם יוצרים טביעת אצבע ייחודית.

פורמט ציטוט ביבליוגרפי