Qwlsh: Cache-conscious Indexing For Processing Similarity Search Query Workloads In High-dimensional Spaces

Abstract

Similarity search queries in high-dimensional spaces are an important type of queries in many domains such as image processing, machine learning, etc. Since exact similarity search indexing techniques suffer from the well-known curse of dimensionality in high-dimensional spaces, approximate search techniques are often utilized instead. Locality Sensitive Hashing (LSH) has been shown to be an effective approximate search method for solving similarity search queries in high-dimensional spaces. Often times, queries in real-world settings arrive as part of a query workload. LSH and its variants are particularly designed to solve single queries effectively. They suffer from one major drawback while executing query workloads: they do not take into consideration important data characteristics for effective cache utilization while designing the index structures. In this paper, we present qwLSH, an index structure for efficiently processing similarity search query workloads in high-dimensional

Stats

• citations3
• S2 citations—
• github stars0
• HF likes0
• heat score4.52
• arxiv keyjafari2019qwlsh

Related papers

• Experimental Analysis Of Locality Sensitive Hashing Techniques For High-dimensional Approximate Nearest Neighbor Searches (2020)6.34
• Improving Locality Sensitive Hashing By Efficiently Finding Projected Nearest Neighbors (2020)6.77
• Efficient Bitmap-based Indexing And Retrieval Of Similarity Search Image Queries (2019)0.00
• Improving Similarity Search With High-dimensional Locality-sensitive Hashing (2018)0.00
• Locality Sensitive Hashing For Set-queries, Motivated By Group Recommendations (2020)0.00
• Experimental Analysis Of Machine Learning Techniques For Finding Search Radius In Locality Sensitive Hashing (2022)0.00
• Drawbacks And Proposed Solutions For Real-time Processing On Existing State-of-the-art Locality Sensitive Hashing Techniques (2019)0.00
• Mmlsh: A Practical And Efficient Technique For Processing Approximate Nearest Neighbor Queries On Multimedia Data (2020)4.52