https://ashvardanian.com/posts/abusing-vector-search/ [apple-touc]Ash's Blog * Archive * Tags * Search * Unum * Subscribe Home >> Posts Abusing Vector Search for Texts, Maps, and Chess [?] May 9, 2023 * 10 min * 2077 words * Ashot Vardanian Table of Contents * Geo-Spatial Indexing * Sto(n)ks * Chess?! * Text Search + Tokens + Hashes * Multi-Index Lookups + Fused Embeddings + JIT-ed User Defined Functions Vector Search is hot! Everyone is pouring resources into a seemingly new and AI-related topic. But are there any non-AI-related use cases? Are there features you want from your vector search engine, but are too afraid to ask? Last week was for vector search. Weaviate raised $50M, and Pinecone raised $100M... That's a lot and makes you believe that vector search is hard. But it's not. I have spent the last few days implementing a single-file vector search engine... 1/7 https://t.co/NBvKufNYTz -- Ashot Vardanian (@ashvardanian) May 2, 2023 A few days ago, I built a new Vector Search engine - USearch. Entirely open-source, Apache 2.0, free for commercial use. It implements HNSW - "Hierarchical Navigable Small World" graphs, the most commonly used data-structure for Vector Search. * It's short - just 1000 lines of C++11. * It's fast - assuming high memory-locality and SIMD tricks. * It's compatible with Python, JavaScript, Java, Rust, [DEL:GoLang :DEL], and Wolfram. Most importantly, USearch supports non-equidimensional vectors and custom similarity measures! It's a general-purpose data structure, limited only by your imagination and applicable to more than AI. Let's highlight some weird use cases and under-the-radar features. Geo-Spatial Indexing# When working with geospatial data, the most common representation is a combination of latitude and longitude. One would use the Haversine distance to compute the distance between two points on a sphere. USearch natively supports it. So without further to do, I took a CSV with geo-locations of 140 thousand towns and districts from Kaggle and tried to find all the closest cities. 1 from usearch import Index 2 3 import pandas as pd 4 import numpy as np 5 import geocoder 6 7 my_coordinates = np.array(geocoder.ip('me').latlng, dtype=np.float32) 8 9 df = pd.read_csv('cities.csv') 10 coordinates = np.zeros((df.shape[0], 2), dtype=np.float32) 11 coordinates[:, 0] = df['latitude'].to_numpy(dtype=np.float32) 12 coordinates[:, 1] = df['longitude'].to_numpy(dtype=np.float32) 13 labels = np.array(range(df.shape[0]), dtype=np.longlong) 14 15 index = Index(metric='haversine') 16 index.add(labels, coordinates) 17 18 matches, _, _ = index.search(my_coordinates, 10) 19 print(df.iloc[matches]) Sitting in a cafe in San Francisco, I received this. 1 id name state_id state_code state_name country_id country_code country_name latitude longitude wikiDataId 2 128666 125809 San Francisco 1416 CA California 233 US United States 37.77493 -122.41942 Q62 3 128430 121985 Mission District 1416 CA California 233 US United States 37.75993 -122.41914 Q7469 4 127999 114046 City and County of San Francisco 1416 CA California 233 US United States 37.77823 -122.44250 Q13188841 5 127991 113964 Chinatown 1416 CA California 233 US United States 37.79660 -122.40858 Q2720635 6 128483 122925 Noe Valley 1416 CA California 233 US United States 37.75018 -122.43369 Q3342640 7 128864 128294 Visitacion Valley 1416 CA California 233 US United States 37.71715 -122.40433 Q495373 8 128049 115006 Daly City 1416 CA California 233 US United States 37.70577 -122.46192 Q370925 9 127926 112800 Brisbane 1416 CA California 233 US United States 37.68077 -122.39997 Q917671 10 128712 125970 Sausalito 1416 CA California 233 US United States 37.85909 -122.48525 Q828729 11 127927 112825 Broadmoor 1416 CA California 233 US United States 37.68660 -122.48275 Q2944590 Dataset. Source. Sto(n)ks# We got lucky. We were working with GIS data, and USearch has the Haversine metric bundled. What if your metric of choice isn't present? Let's imagine you are analyzing the stock market or the price change of a particular asset. The first thing to do is to investigate which other assets follow the same trend. In other words, which assets are covariant? Covariance isn't included. Covariance Formula for USearch But once you check the formula, you realize it resembles the "Inner Product" metric. If you have used FAISS, you know it doesn't ship the angular distance, as it expects you to normalize vectors. Same here. We can pre-process the vectors, subtracting the np.mean, before passing to usearch.Index, and things will work. 1 import os 2 import time 3 from statistics import covariance 4 5 from usearch import Index 6 import pandas as pd 7 import numpy as np 8 9 directory: str = 'stocks' 10 last_days: int = 30 11 tickets: list[str] = [] 12 ticket_to_prices: dict[str, np.array] = {} 13 index = Index(ndim=last_days) 14 15 for filename in os.listdir(directory): 16 path = os.path.join(directory, filename) 17 ticket = filename.split('.')[0] 18 df = pd.read_csv(path) 19 20 prices_list = df['Close'][-last_days:].to_list() 21 prices = np.zeros(last_days, dtype=np.float32) 22 prices[-len(prices_list):] = prices_list 23 24 tickets.append(ticket) 25 index.add(len(index), prices - np.mean(prices)) 26 ticket_to_prices[ticket] = prices 27 28 selected_ticker = 'AAPL' 29 30 tic = time.perf_counter() 31 selected_prices = ticket_to_prices[selected_ticker] 32 approx_matches, _, _ = index.search( 33 selected_prices - np.mean(selected_prices), 10) 34 approx_tickets = [tickets[match] for match in approx_matches] 35 toc = time.perf_counter() 36 print('Approximate matches:', ','.join(approx_tickets)) 37 print(f'- Measurement took {toc - tic:0.4f} seconds') 38 39 40 tic = time.perf_counter() 41 covariances = [ 42 (ticket, covariance(selected_prices, prices)) 43 for ticket, prices in ticket_to_prices.items()] 44 covariances = sorted(covariances, key=lambda x: x[1], reverse=True) 45 exact_tickets = [ticket for ticket, _ in covariances[:10]] 46 toc = time.perf_counter() 47 print('Exact matches:', ','.join(exact_tickets)) 48 print(f'- Measurement took {toc - tic:0.4f} seconds') Running the script, we get a 2'000x performance improvement over the naive Python approach for a small collection of 5'884 entries covering a month of closing prices. The benefits would be more significant with more extensive collections and longer ranges. 1 Approximate matches: ELC, NVR, SEB, BKNG, MKL, TPL, CABO, TSLA, GOOGL, GOOG 2 - Measurement took 0.0001 seconds 3 4 Exact matches: ELC, NVR, MKL, TPL, CABO, AZO, BA, ISRG, FLGE, AMZN 5 - Measurement took 0.2396 seconds Dataset. Source. Chess?!# Imagine having to search through a database of chess positions. There are specialized methods, often based on Zobrist hashing. But there is also a more straightforward way. A chess board can be easily encoded with 64 bytes, where each byte encodes a particular piece. 1 enum piece_t { 2 w_king_k, w_queen_k, b_king_k, b_queen_k, 3 w_pawn_k, w_rook_k, b_pawn_k, b_rook_k, 4 w_bishop_k, w_knight_k, b_bishop_k, b_knight_k, 5 }; You can compare two boards with a Hamming distance - index_gt >. Alternatively, you can design a custom scheme to weigh pieces differently, assuming pawns' positions affect the game less than those of queens. 1 unsigned weight(piece_t piece) { 2 switch (piece) { 3 case w_king_k: w_queen_k: b_king_k: b_queen_k: return 5u; 4 case w_rook_k: w_bishop_k: w_knight_k: b_rook_k: b_bishop_k: b_knight_k: return 3u; 5 default: return 1u; 6 } 7 } 8 9 struct position_distance_t { 10 unsigned operator () (piece_t const *board_a, piece_t const *board_b, std::size_t, std::size_t) const { 11 return std::transform_reduce(board_a, board_a + 64, board_b, 0u, std::plus {}, &weight); 12 } 13 }; This should also work for any other board or card game with discrete states, like Chess, Shogi, or Poker. Text Search# With LLMs and Socratic Models, Natural Language Processing is on the rise. The go-to way of searching through texts is now embedding them with BERT, or something specialized, like ColBERT, and then putting outputs into a Vector Search engine: a modern representation and a modern index structure. What if we combine an ancient representation with a modern index, retro-futuristically? Tokens# Typically, one would tokenize the text, pass it to the transformer, and then put the embedding into a Vector Search engine. Still, one can compare the two texts by avoiding the intermediate step and intersecting the sets of present tokens to compute Jaccard similarity. For that USearch has SetsIndex. 1 from usearch import SetsIndex 2 from transformers import BertTokenizer 3 4 sets_index = SetsIndex() 5 tokenizer = BertTokenizer.from_pretrained('bert-base-uncased') 6 7 def text2set(sample: str) -> np.array: 8 encoding = tokenizer.encode(sample, truncation=True) 9 encoding = encoding[1:-1] 10 encoding = sorted(set(encoding)) 11 encoding = np.array(encoding, dtype=np.int32) 12 return encoding 13 14 sets_index.add(42, text2set('The answer to all your questions')) Taking the HackerNews dataset and ~85K of its first entries, I've constructed an index and searched for theoretical physics. 1 Results: 2 - 1. A science podcast you can try is Physics Frontiers. It gets pretty technical. 3 https://news.ycombinator.com/item?id=23588415 4 - 2. I wonder why exponentials are so common in nature/physics but tetration is not 5 https://news.ycombinator.com/item?id=32285985 6 - 3. Which is why of course physics departments pay you ~50% to do a PhD, whereas in Computer Science... 7 https://news.ycombinator.com/item?id=21440764 Probably not ideal, but it works! Hashes# Variable length representations aren't always fast to work with. If you know that the text will be having similar size, a common approach is to generate hash-like fingerprints. For that USearch has HashIndex. 1 from usearch import HashIndex 2 3 hash_index = HashIndex(bits=1024) 4 5 def text2hashes(sample: str) -> np.array: 6 words = sample.lower().split() 7 return np.array([hash(word) for word in words], dtype=np.int64) 8 9 hash_index.add(42, text2hashes('The answer to all your questions')) This won't give you high-quality search results. Still, some companies would use a variation of that approach in complex multi-stage search pipelines. Dataset. Source. Multi-Index Lookups# Most Search systems operate on more than one embedding. Imagine an online marketplace like Airbnb or Booking. Once you open a listing, the platform will suggest a few alternatives. It will search for nearby locations with similar pictures and textual descriptions. Typically, geospatial indexing will be handled by a specialized system, but we can now put everything together. 1 from usearch import Index 2 from uform import get_model 3 from ucall.rich_posix import Server 4 5 server = Server() 6 7 index_images = Index(ndim=256) 8 index_texts = Index(ndim=256) 9 index_coordinates = Index(metric='haversine') 10 11 model = get_model('unum-cloud/uform-vl-english') 12 13 @server 14 def recommend(text: str, image: Image, latitude: float, longitude: float) -> list[int]: 15 16 vector_image = model.encode_image(model.preprocess_image(image)).numpy() 17 vector_text = model.encode_text(model.preprocess_text(text)).numpy() 18 vector_coordinate = np.array([latitude, longitude], dtype=np.float32) 19 20 similar_images, _, _ = index_images.search(vector_image, 30) 21 similar_texts, _, _ = index_texts.search(vector_text, 30) 22 similar_coordinates, _, _ = index_coordinates.search(vector_coordinate, 100) 23 24 # If a listing is physically close and matches text or image, it must be first. 25 similar_contents = set(similar_images) + set(similar_texts) 26 return [label for label in similar_coordinates if label in similar_contents] 27 28 server.run() Fused Embeddings# When using mid-fusion models like UForm, you can get a multi-modal embedding out of the box. Thus you can save one index lookup and still get more relevant results. 1 index_contents = Index(ndim=384) 2 index_coordinates = Index(metric='haversine') 3 4 model = get_model('unum-cloud/uform-vl-english') 5 6 @server 7 def recommend(text: str, image: Image, latitude: float, longitude: float) -> list[int]: 8 9 vector_content = model.encode_multimodal( 10 image=model.preprocess_image(image), 11 text=model.preprocess_text(text)).numpy() 12 vector_coordinate = np.array([latitude, longitude], dtype=np.float32) 13 14 similar_contents, _, _ = index_contents.search(vector_content, 60) 15 similar_coordinates, _, _ = index_coordinates.search(vector_coordinate, 100) 16 17 # If a listing is physically close and matches contents, it must be first. 18 return [label for label in similar_coordinates if label in similar_contents] JIT-ed User Defined Functions# If you use a less specialized model, don't worry. You can concatenate the textual and image vector and customize the index to take your alternative similarity function. In C++, it's as easy as passing a custom template argument. With Numba, however, you can get to the C++ layer without getting to the C++ layer. Once you JIT-compile your function, you can pass it's address to the C++ library like this: 1 from numba import cfunc, types, carray 2 3 signature = types.float32( 4 types.CPointer(types.float32), 5 types.CPointer(types.float32), 6 types.size_t, types.size_t) 7 8 9 @cfunc(signature) 10 def metric(a, b, _, _): 11 a_array = carray(a, 512) 12 b_array = carray(b, 512) 13 text_similarity = 0.0 14 image_similarity = 0.0 15 for i in range(256): 16 image_similarity += a_array[i] * b_array[i] 17 text_similarity += a_array[i + 256] * b_array[i + 256] 18 return 2 - image_similarity - text_similarity 19 20 index_contents = Index(ndim=512, metric_pointer=metric.address) 21 22 @server 23 def recommend(text: str, image: Image, latitude: float, longitude: float) -> list[int]: 24 25 vector_image = model.encode_image(model.preprocess_image(image)).numpy() 26 vector_text = model.encode_text(model.preprocess_text(text)).numpy() 27 vector_content = np.concatenate((vector_image, vector_text)) 28 similar_contents, _, _ = index_contents.search(vector_content, 60) 29 ... We have just built a composite recommendation system with zero microservices or dollars spent on private APIs. The only thing left is to choose an excellent neural network tuned for your domain! Which may not even be needed with the upcoming snapshots of UForm, promising better generalization across domains. --------------------------------------------------------------------- USearch Vector Search Approaches Not bad, right? HNSW is a simple data structure, but unlike many older approaches, it has many applications. That's why we aren't keen on quantization. It takes away too many excellent properties. That being said, we know that the core algorithm has space for improvement! So feel free to fork it and try it yourself! * USearch in-memory vector search * UStore up to 10x faster multi-modal database * UForm tiny efficient multi-modal transformers * UCall up to 100x faster networking [?] Don't forget to star on GitHub and reach out on Discord if you have any questions. * tech Next >> How Junior and Senior C++ Devs Locate Unique Strings (c) 2023 Ash's Blog Powered by Hugo & PaperMod