最快二进制数据比较方案：如何获取Top100最相似条目索引？

Hey folks, let's break down how to solve this problem efficiently—you've got 10 million binary vectors (each 1000 elements, either 0/1 or True/False), and every time a new vector comes in, you need the top 100 existing vectors that share the most 1s (True values) with it.

First off, let's be clear: brute-forcing this (comparing the new vector to every single one in your dataset) is going to be way too slow. 10 million × 1000 operations per query adds up to 10 billion calculations—no way that's going to work for any real-time use case. So let's jump into the practical, optimized approaches:

1. In-Memory Vectorization with NumPy (Best for Speed, If You Have RAM) #

If you can fit your entire dataset in memory, this is the fastest way to go. NumPy's vectorized operations are optimized under the hood, so you can compute all overlap counts in one go instead of looping through each vector.

• Quick Setup: Convert all your vectors into a 2D NumPy array using uint8 (each element takes 1 byte—saves a ton of space). For a 10M × 1000 dataset, that's 10GB total, which is manageable on modern servers.
• Example Code:

  import numpy as np
  import heapq
  
  # Preprocess: Convert your dataset to a numpy array
  # Replace your_list_of_vectors with your actual data (list of lists/arrays)
  dataset = np.array(your_list_of_vectors, dtype=np.uint8)
  
  def get_top_100_matches(new_vector):
      # Convert new vector to numpy array
      new_vec = np.array(new_vector, dtype=np.uint8)
      # Compute dot product (this gives the count of overlapping 1s for every vector)
      overlap_counts = dataset @ new_vec.T
      # Use heapq to get top 100 indices without sorting the entire array (saves memory)
      top_indices = heapq.nlargest(100, range(len(overlap_counts)), key=lambda i: overlap_counts[i])
      return top_indices
  

• Why This Works: The dot product between two binary vectors is exactly the number of positions where both have a 1—perfect for your use case.

2. Inverted Index (Great for Sparse Vectors) #

If your vectors are sparse (most elements are 0/False), an inverted index will save you both time and memory. Think of it like how search engines track which documents contain each keyword.

• How to Build It: Create a dictionary where each key is a position in the vector (0 to 999), and the value is a list of indices of vectors that have a 1 in that position.
• Querying: For the new vector, grab all positions where it has a 1, then count how many times each existing vector index appears across those positions. The count is exactly the number of overlapping 1s.
• Example Code:

  from collections import defaultdict, Counter
  
  # Preprocess: Build the inverted index
  inverted_index = defaultdict(list)
  for vec_idx, vector in enumerate(your_dataset):
      for pos, val in enumerate(vector):
          if val in (1, True):
              inverted_index[pos].append(vec_idx)
  
  def get_top_100_matches(new_vector):
      # Get all positions where the new vector has a 1/True
      active_positions = [pos for pos, val in enumerate(new_vector) if val in (1, True)]
      # Count how many times each vector index appears in these positions
      overlap_counter = Counter()
      for pos in active_positions:
          overlap_counter.update(inverted_index[pos])
      # Grab the top 100 indices with the highest counts
      return [idx for idx, _ in overlap_counter.most_common(100)]
  

• Bonus: If your vectors are super sparse (like <100 1s per vector), this will be way faster than even the NumPy approach because you're only checking relevant vectors.

3. Locality-Sensitive Hashing (LSH) for Approximate Results #

If you can't fit the dataset in memory and need fast queries, LSH is a solid approximate option. It hashes vectors so that similar ones end up in the same buckets, so you only need to compare vectors in those buckets instead of the whole dataset.

• Quick Implementation:
  1. Split your 1000-dimensional vector into smaller chunks (e.g., 20 chunks of 50 elements each).
  2. For each chunk, compute a simple hash (like summing the elements or using a random projection).
  3. Store vectors in a dictionary where keys are tuples of chunk hashes, and values are lists of vector indices.
  4. When querying, compute the new vector's hash tuple, pull all vectors from those buckets, calculate exact overlap counts, and pick the top 100.
• Tradeoff: You might miss some highly similar vectors, but you can adjust the number of chunks to balance speed and accuracy. More chunks mean more accurate results but slower queries.

4. Database-Powered Vector Search (For Persistent, Large-Scale Data) #

If your dataset is too big for memory and you need persistent storage, use a database optimized for vector search:

• PostgreSQL + pgvector: Store your binary vectors as bit or vector types, then use the top_k function with dot product similarity to get the top matches.
• Elasticsearch: Use the dense_vector field with cosine similarity—for binary vectors, cosine similarity is directly proportional to the overlap count, so top cosine scores will be your top overlap matches.

Final Tips #

• Check Sparsity: If most of your vector elements are 0, go with the inverted index. If dense, NumPy is your best bet.
• Exact vs Approximate: If you need perfect top 100 results, stick to NumPy or inverted index. If "close enough" works, LSH will give you way faster queries.
• Memory Optimization: Using uint8 in NumPy cuts memory usage by 75% compared to 32-bit integers—always use the smallest dtype possible.

内容的提问来源于stack exchange，提问作者user1406177