Vector Database ও ANN Search
- ●Embedding হলো টেক্সট/ছবিকে সংখ্যার vector-এ রূপান্তর, যেখানে কাছাকাছি অর্থের জিনিস কাছাকাছি বসে।
- ●Brute-force similarity search প্রতিটি vector-এর সাথে তুলনা করে, যা কোটি কোটি vector-এ অসম্ভব ধীর।
- ●ANN অ্যালগরিদম (HNSW, IVF) সামান্য accuracy ছেড়ে দিয়ে কয়েক হাজার গুণ দ্রুত search দেয়।
সমস্যাটা কী?
ধরো তুমি একটা সার্চ সিস্টেম বানাচ্ছো যেখানে ইউজার লিখবে "সস্তা দামে ভালো ইয়ারফোন" আর তুমি দেখাবে মিলে যাওয়া প্রোডাক্ট। পুরোনো দিনের keyword search হলে শুধু যেসব প্রোডাক্টে হুবহু "সস্তা", "ইয়ারফোন" শব্দ আছে সেগুলোই আসত। কিন্তু "বাজেট হেডফোন" লেখা একটা দারুণ প্রোডাক্ট বাদ পড়ে যাবে, কারণ শব্দ মেলেনি যদিও অর্থ এক।
আধুনিক ML সিস্টেম এই সমস্যা সমাধান করে Embedding দিয়ে—প্রতিটি জিনিসকে অর্থ অনুযায়ী একটা সংখ্যার তালিকায় (vector) পরিণত করে। কিন্তু তখন নতুন সমস্যা: তোমার কাছে যদি ১০ কোটি প্রোডাক্টের vector থাকে, প্রতিটি search-এ কীভাবে সবচেয়ে কাছের vector খুঁজে বের করবে—তাও milliseconds-এর মধ্যে? এটাই Vector Database আর ANN search-এর মূল চ্যালেঞ্জ।
মূল ধারণা
Embedding হলো এমন একটি vector (যেমন ৭৬৮টি সংখ্যার তালিকা) যা কোনো টেক্সট, ছবি বা অডিওর অর্থকে এমনভাবে উপস্থাপন করে যে অর্থে কাছাকাছি জিনিসগুলো গণিতগতভাবেও কাছাকাছি অবস্থান করে।
একটা ML মডেল (যেমন sentence-transformer) "ভালো ইয়ারফোন" বাক্যটিকে নিয়ে আউটপুট দেয় ধরো [0.21, -0.05, 0.88, ...]—মোট ৭৬৮ বা ১৫৩৬টি সংখ্যা। এই সংখ্যাগুলো একটা উচ্চ-মাত্রার (high-dimensional) স্পেসে একটা বিন্দু নির্দেশ করে। "বাজেট হেডফোন"-এর vector এই বিন্দুর খুব কাছে বসবে, কিন্তু "ফ্রিজের দাম"-এর vector অনেক দূরে।
কতটা কাছাকাছি, তা মাপা হয় similarity metric দিয়ে—সবচেয়ে কমন হলো cosine similarity (দুটি vector-এর মধ্যবর্তী কোণ) বা dot product। দুটি vector যত বেশি একই দিকে নির্দেশ করবে, তাদের অর্থ তত কাছাকাছি।
তাহলে search মানে দাঁড়াচ্ছে: query-র vector নাও, আর dataset-এর মধ্যে সবচেয়ে কাছের kটি vector (top-k nearest neighbors) খুঁজে বের করো।
কীভাবে কাজ করে
Brute-force কেন যথেষ্ট নয়
সবচেয়ে সহজ পদ্ধতি: query vector-কে dataset-এর প্রতিটি vector-এর সাথে তুলনা করো, similarity হিসাব করো, তারপর সাজাও। একে বলে exact nearest neighbor বা brute-force।
সমস্যা হলো এর খরচ। ১ কোটি vector আর প্রতিটি ১৫৩৬ মাত্রার হলে, একটি মাত্র query-তে প্রায় ১.৫ বিলিয়ন গুণফল-যোগ লাগে। হাজার হাজার ইউজার একসাথে query করলে সার্ভার গলে যাবে।
| পদ্ধতি | সময় জটিলতা | ১ কোটি vector-এ latency (আনুমানিক) | নির্ভুলতা |
|---|---|---|---|
| Brute-force (exact) | O(N·d) | কয়েকশ ms – সেকেন্ড | ১০০% |
| ANN (HNSW) | O(log N) মতো | ১–১০ ms | ৯৫–৯৯% |
| ANN (IVF) | O(N/clusters) | ৫–২০ ms | ৯০–৯৮% |
এখানেই ANN (Approximate Nearest Neighbor) আসে—আমরা সামান্য নির্ভুলতা ছেড়ে দিয়ে বিশাল গতি কিনি।
HNSW: graph দিয়ে navigation
HNSW (Hierarchical Navigable Small World) আজকের সবচেয়ে জনপ্রিয় ANN অ্যালগরিদম। এটি vector-গুলোকে একটা বহু-স্তরের graph-এ সাজায়:
- উপরের স্তরে খুব কম node থাকে, কিন্তু লম্বা "highway" connection—দ্রুত একদিক থেকে আরেকদিকে যাওয়া যায়।
- নিচের স্তরে সব node থাকে, ঘন connection—সূক্ষ্মভাবে কাছের প্রতিবেশী খুঁজে পাওয়া যায়।
Search শুরু হয় উপরের স্তরে এক বিন্দু থেকে, query-র দিকে "হাঁটতে" থাকে। কাছাকাছি পৌঁছে নিচের স্তরে নেমে আরও সূক্ষ্ম search করে। এতে পুরো dataset স্ক্যান না করেই log-সময়ে ভালো প্রতিবেশী পাওয়া যায়।
IVF: আগে cluster, পরে search
IVF (Inverted File Index) ভিন্ন কৌশল নেয়—প্রথমে পুরো dataset-কে কয়েক হাজার cluster-এ ভাগ করে (k-means দিয়ে)। প্রতিটি cluster-এর একটা প্রতিনিধি বিন্দু (centroid) থাকে। Query এলে শুধু কাছের কয়েকটি cluster-এর ভেতরে search করা হয়, বাকি সব এড়িয়ে যাওয়া হয়। কতগুলো cluster খুঁজবে (nprobe) তা বাড়ালে recall বাড়ে কিন্তু latency-ও বাড়ে।
প্রায়ই IVF-এর সাথে PQ (Product Quantization) যোগ করা হয়, যা vector-কে কমপ্রেস করে memory বাঁচায়—বিলিয়ন-স্কেল dataset-এ জরুরি।
ঢাকা শহরে কারও বাসা খুঁজছো। Brute-force মানে প্রতিটি বাড়িতে গিয়ে দরজায় কড়া নাড়া—অসম্ভব। IVF হলো: আগে ঠিক করো কোন এলাকা (ধানমন্ডি/উত্তরা/মিরপুর), তারপর শুধু সেই এলাকার ভেতর খোঁজো। HNSW হলো: বড় রাস্তা ধরে এলাকার কাছে পৌঁছে, তারপর গলি ধরে, শেষে নির্দিষ্ট বাড়িতে—প্রতি ধাপে আরও সূক্ষ্ম।
কৌশল
কয়েকটি গুরুত্বপূর্ণ tuning বিষয়:
- Recall vs Latency: এটাই কেন্দ্রীয় trade-off। HNSW-তে
ef_searchপ্যারামিটার বাড়ালে index আরও বেশি node explore করে—Recall বাড়ে (true neighbor কম মিস হয়), কিন্তু latency বাড়ে। তোমার product-এ ৯৫% recall যথেষ্ট নাকি ৯৯% দরকার, সেটা ব্যবসায়িক সিদ্ধান্ত। - Index build time vs query time: HNSW build করতে সময় ও memory বেশি লাগে, কিন্তু query দ্রুত। নতুন vector যোগ করা সহজ, মুছে ফেলা কঠিন।
- Distance metric মিলিয়ে নেওয়া: যে metric দিয়ে embedding ট্রেইন হয়েছে (cosine নাকি L2), index-এও সেটাই ব্যবহার করতে হবে—নয়তো ভুল ফল।
- Filtering: শুধু similar নয়, "stock-এ আছে এমন similar প্রোডাক্ট" দরকার হলে metadata filtering লাগে, যা ANN-এর সাথে combine করা জটিল।
কখন ব্যবহার করবে / করবে না
ব্যবহার করবে যখন—semantic search, recommendation, RAG-এর retrieval, ছবি/গান মেলানো, duplicate detection, anomaly detection। অর্থাৎ যেখানে "কাছাকাছি অর্থ/বৈশিষ্ট্য" খুঁজতে হয়।
করবে না যখন—তোমার ডেটা ছোট (কয়েক হাজার vector হলে brute-force-ই যথেষ্ট, in-memory NumPy দিয়েই হবে), অথবা তোমার search-এ ঠিক keyword/ID ম্যাচ দরকার (সেখানে সাধারণ B-tree বা inverted index ভালো)।
ANN approximate—এটি কখনো ১০০% নিশ্চয়তা দেয় না যে সবচেয়ে কাছের vector পাওয়া গেছে। ব্যাংকের fraud-blocking বা মেডিকেল ডায়াগনোসিসের মতো জায়গায় যেখানে একটা মিস হওয়া প্রতিবেশী বিপজ্জনক, সেখানে recall খুব উঁচুতে রাখো অথবা critical subset-এ exact search চালাও।
বাস্তব উদাহরণ
- Spotify / YouTube: তোমার পছন্দের গান বা ভিডিওর embedding বের করে কাছের embedding-গুলো খুঁজে "তোমার জন্য রেকমেন্ডেশন" বানায়—কোটি কোটি আইটেম থেকে ANN দিয়ে রিয়েল-টাইমে।
- ChatGPT-এর মতো RAG সিস্টেম: ইউজারের প্রশ্নকে embed করে কোম্পানির ডকুমেন্ট থেকে relevant অংশ retrieve করে—এর পেছনে vector DB।
- Google / e-commerce search: semantic search-এ "মেলানো অর্থ" খুঁজতে embedding + ANN।
জনপ্রিয় টুল:
| টুল | ধরন | বিশেষত্ব |
|---|---|---|
| pgvector | PostgreSQL extension | আগে থেকে Postgres থাকলে সহজ, ছোট-মাঝারি স্কেল |
| Milvus | Open-source vector DB | বিলিয়ন-স্কেল, distributed |
| Pinecone | Managed cloud | সার্ভার ঝামেলা নেই, দ্রুত শুরু |
| FAISS | Library (Meta) | লাইব্রেরি, নিজে infra সামলাতে হয় |
ইন্টারভিউতে বলো: "প্রথমে scale জিজ্ঞেস করব—কয়েক হাজার vector হলে brute-force যথেষ্ট, vector DB-র দরকার নেই। মিলিয়ন/বিলিয়ন স্কেলে HNSW বা IVF-PQ বেছে নেব, আর recall vs latency-র টার্গেট ব্যবসায়িক প্রয়োজন থেকে ঠিক করব।" এই trade-off সচেতনতাই দেখায় তুমি সিস্টেম বোঝো, শুধু টুলের নাম মুখস্থ করোনি।
মিনি কুইজ
1. Brute-force similarity search-এর মূল সমস্যা কী?
2. ANN-এ recall vs latency trade-off বলতে কী বোঝায়?
3. HNSW-এর মূল ডেটা স্ট্রাকচার কোনটি?