32:T4db,viewof targetId = { const container = d3.create("div"); const containerDiv = container.node(); containerDiv.value = -1; container.style("display", "flex").style("flex-wrap", "wrap"); const imgs = container .selectAll("div") .data(optionList) .join("div") .style("background-image", (id) => `url(${id2img(id)})`) .style("height", "128px") .style("width", "200px") .style("margin", "12px 16px") .style("background-size", "contain") .style("background-repeat", "no-repeat") .style("background-position", "center") .style("border-radius", "4px") .style("cursor", "pointer") .on("mouseover", function () { d3.select(this).style("box-shadow", `0 0 30px ${ZillizBlue}`); }) .on("mouseout", function () { d3.select(this).style("box-shadow", null); }); const update = (_, id) => { if (id === containerDiv.value) return; imgs .style("opacity", (d) => (d === id ? 1 : 0.9)) .style("outline", (d) => d === id ? `8px solid ${ZillizBlue}` : null ); setTimeout(() => { containerDiv.value = id; containerDiv.dispatchEvent(new CustomEvent("input")); }, 0); }; imgs.on("click", update); return containerDiv; }33:T5aa,{ const container = d3.create("div"); const containerDiv = container.node(); // const button = searchButton("Show research res"); // containerDiv.appendChild(button.node()); const topKImgsContainer = container.append("div"); await ivfflatFeder.initCoreAndViewPromise; const renderGetTopKRes = (targetId) => { if (!(targetId >= 0)) return d3.create("div").text(selectInfo).node(); const res = ivfflatFeder.core.search(ivfflatFeder.core.id2vector[targetId]); const imgs = res.fsResIds.map((id) => id2img(id)); const container = d3.create("div"); container.style("display", "flex").style("flex-wrap", "wrap"); container .selectAll("div") .data(imgs) .join("div") .style("background-image", (d) => `url(${d})`) .style("height", "128px") .style("width", "200px") .style("margin", "12px 16px") .style("background-size", "contain") .style("background-repeat", "no-repeat") .style("background-position", "center") .style("border-radius", "4px"); return container.node(); }; const content = renderGetTopKRes(targetId); topKImgsContainer.selectAll("*").remove(); topKImgsContainer.node().appendChild(content); // button.on("click", () => { // const content = renderGetTopKRes(targetId); // topKImgsContainer.selectAll("*").remove(); // topKImgsContainer.node().appendChild(content); // }); return container.node(); }34:T66a,customButton = (label) => { const container = d3 .create("div") .style("display", "flex") .style("flex-direction", "row") .style("margin-bottom", "20px"); const div = container.append("div"); div .style("color", "#000") .style("background-image", `url("data:image/svg+xml,%0A%3Csvg fill='%23000000' xmlns='http://www.w3.org/2000/svg' viewBox='0 0 30 30' width='30px' height='30px'%3E%3Cpath d='M 15 3 C 12.031398 3 9.3028202 4.0834384 7.2070312 5.875 A 1.0001 1.0001 0 1 0 8.5058594 7.3945312 C 10.25407 5.9000929 12.516602 5 15 5 C 20.19656 5 24.450989 8.9379267 24.951172 14 L 22 14 L 26 20 L 30 14 L 26.949219 14 C 26.437925 7.8516588 21.277839 3 15 3 z M 4 10 L 0 16 L 3.0507812 16 C 3.562075 22.148341 8.7221607 27 15 27 C 17.968602 27 20.69718 25.916562 22.792969 24.125 A 1.0001 1.0001 0 1 0 21.494141 22.605469 C 19.74593 24.099907 17.483398 25 15 25 C 9.80344 25 5.5490109 21.062074 5.0488281 16 L 8 16 L 4 10 z'/%3E%3C/svg%3E")`) .style("background-repeat", "no-repeat") .style("background-size", "24px") .style("background-position", "left center") .style("display", "flex") .style("align-items", "center") .style("padding", "6px 16px") .style("padding-left", "32px") .style("font-size", "20px") .style("border-radius", "6px") .style("cursor", "pointer") .on("mouseenter", function () { d3.select(this).style("opacity", 0.8); }) .on("mouseout", function () { d3.select(this).style("opacity", 1); }); div.text(label); container.clickHandler = () => {}; div.on("click", () => container.clickHandler()); return container; }35:T751,playButton = (label) => { const container = d3 .create("div") .style("display", "flex") .style("flex-direction", "row") .style("margin-bottom", "20px"); const div = container.append("div"); div .style("color", "#000") .style("background-image", `url("data:image/svg+xml,%3C%3Fxml version='1.0' encoding='iso-8859-1'%3F%3E%3C!-- Generator: Adobe Illustrator 19.0.0, SVG Export Plug-In . SVG Version: 6.00 Build 0) --%3E%3Csvg version='1.1' id='Layer_1' xmlns='http://www.w3.org/2000/svg' xmlns:xlink='http://www.w3.org/1999/xlink' x='0px' y='0px' viewBox='0 0 512.055 512.055' style='enable-background:new 0 0 512.055 512.055;' xml:space='preserve'%3E%3Cg%3E%3Cg%3E%3Cpath d='M500.235,236.946L30.901,2.28C16.717-4.813,0.028,5.502,0.028,21.361v469.333c0,15.859,16.689,26.173,30.874,19.081 l469.333-234.667C515.958,267.247,515.958,244.808,500.235,236.946z M42.694,456.176V55.879l400.297,200.149L42.694,456.176z'/%3E%3C/g%3E%3C/g%3E%3Cg%3E%3C/g%3E%3Cg%3E%3C/g%3E%3Cg%3E%3C/g%3E%3Cg%3E%3C/g%3E%3Cg%3E%3C/g%3E%3Cg%3E%3C/g%3E%3Cg%3E%3C/g%3E%3Cg%3E%3C/g%3E%3Cg%3E%3C/g%3E%3Cg%3E%3C/g%3E%3Cg%3E%3C/g%3E%3Cg%3E%3C/g%3E%3Cg%3E%3C/g%3E%3Cg%3E%3C/g%3E%3Cg%3E%3C/g%3E%3C/svg%3E%0A")`) .style("background-repeat", "no-repeat") .style("background-size", "24px") .style("background-position", "left center") .style("display", "flex") .style("align-items", "center") .style("padding", "6px 16px") .style("padding-left", "32px") .style("font-size", "20px") .style("border-radius", "6px") .style("cursor", "pointer") .on("mouseenter", function () { d3.select(this).style("opacity", 0.8); }) .on("mouseout", function () { d3.select(this).style("opacity", 1); }); div.text(label); container.clickHandler = () => {}; div.on("click", () => container.clickHandler()); return container; }36:T7e7,searchButton = (label) => { const container = d3 .create("div") .style("display", "flex") .style("flex-direction", "row") .style("margin-bottom", "20px"); const div = container.append("div"); div .style("color", "#000") .style("background-image", `url("data:image/svg+xml,%3C%3Fxml version='1.0' encoding='iso-8859-1'%3F%3E%3C!-- Generator: Adobe Illustrator 19.0.0, SVG Export Plug-In . SVG Version: 6.00 Build 0) --%3E%3Csvg version='1.1' id='Capa_1' xmlns='http://www.w3.org/2000/svg' xmlns:xlink='http://www.w3.org/1999/xlink' x='0px' y='0px' viewBox='0 0 53.627 53.627' style='enable-background:new 0 0 53.627 53.627;' xml:space='preserve'%3E%3Cpath d='M53.627,49.385L37.795,33.553C40.423,30.046,42,25.709,42,21C42,9.42,32.58,0,21,0S0,9.42,0,21s9.42,21,21,21 c4.709,0,9.046-1.577,12.553-4.205l15.832,15.832L53.627,49.385z M2,21C2,10.523,10.523,2,21,2s19,8.523,19,19s-8.523,19-19,19 S2,31.477,2,21z M35.567,36.093c0.178-0.172,0.353-0.347,0.525-0.525c0.146-0.151,0.304-0.29,0.445-0.445l14.262,14.262 l-1.415,1.415L35.123,36.537C35.278,36.396,35.416,36.238,35.567,36.093z'/%3E%3Cg%3E%3C/g%3E%3Cg%3E%3C/g%3E%3Cg%3E%3C/g%3E%3Cg%3E%3C/g%3E%3Cg%3E%3C/g%3E%3Cg%3E%3C/g%3E%3Cg%3E%3C/g%3E%3Cg%3E%3C/g%3E%3Cg%3E%3C/g%3E%3Cg%3E%3C/g%3E%3Cg%3E%3C/g%3E%3Cg%3E%3C/g%3E%3Cg%3E%3C/g%3E%3Cg%3E%3C/g%3E%3Cg%3E%3C/g%3E%3C/svg%3E%0A")`) .style("background-repeat", "no-repeat") .style("background-size", "24px") .style("background-position", "left center") .style("display", "flex") .style("align-items", "center") .style("padding", "6px 16px") .style("padding-left", "32px") .style("font-size", "20px") .style("border-radius", "6px") .style("cursor", "pointer") .on("mouseenter", function () { d3.select(this).style("opacity", 0.8); }) .on("mouseout", function () { d3.select(this).style("opacity", 1); }); div.text(label); container.clickHandler = () => {}; div.on("click", () => container.clickHandler()); return container; }37:[{"id":"8ffecc652a8dfa22ac176987bece82603b90d9067e2fa4ff2c05ca4647fc76ee02f51edc1ed86cad3ebe8e60e01d25af8a2bdd43910d9682fdec7ba5f1989eae","href":"https://static.observableusercontent.com/files/8ffecc652a8dfa22ac176987bece82603b90d9067e2fa4ff2c05ca4647fc76ee02f51edc1ed86cad3ebe8e60e01d25af8a2bdd43910d9682fdec7ba5f1989eae","name":"image.png","type":"image/png","lastModified":1656901945267.217,"size":142784}] 30:{"title":"Understanding vector embeddings with Feder by a reverse image search example (IVF_FLAT)!","cells":[{"id":0,"value":"# Understanding vector embeddings with [Feder](https://github.com/zilliztech/feder) by a reverse image search example (IVF_FLAT)!","pinned":false,"hidden":false,"mode":"md"},{"id":6,"value":"

In this example, we are using

VOC 2012 DataSet (17k+ images) as our dataset
Towhee to extract vector embeddings from images
Faiss to build search index from embeddings
Feder to do the similarity search and visualize how the search index works

","pinned":false,"hidden":false,"mode":"html"},{"id":977,"value":"

First, let's go through a reverse image search example

\n
\n

Click on an image below as the search target.

You can click on the refresh button to get new images to choose.

","pinned":false,"hidden":false,"mode":"html"},{"id":571,"value":"viewof optionList = {\n const container = d3.create(\"div\");\n const button = customButton(\"Refresh\");\n\n container.node().value = randomSelect(8, 10000);\n\n const update = () => {\n const optionList = randomSelect(7, 10000);\n container.node().value = optionList.concat([14383]);\n container.dispatch(\"input\");\n };\n\n button.clickHandler = update;\n\n container.node().appendChild(button.node());\n\n return container.node();\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":139,"value":"$32","pinned":false,"hidden":false,"mode":"ojs"},{"id":800,"value":"

Similarity image search results

","pinned":false,"hidden":false,"mode":"html"},{"id":562,"value":"$33","pinned":false,"hidden":false,"mode":"ojs"},{"id":83,"value":"#### You may be puzzled by how computers understand similarity.\n\n\nHumans have a natural sensitivity and unique processing channels for visual\ninformation, while for computers, it is not possible to understand the pictures\ndirectly, but rather to **embed** them into vector data. \n\n $\"image.png\"$ \n","pinned":false,"hidden":false,"mode":"md"},{"id":108,"value":"And what is an embedding vector? As an example, an apple, can be abstracted as [red, spherical, sweet, fragrant, grows on a tree, etc.] , and anything similar (not necessarily identical) to these features we can call an apple. If we use numbers to correspond to these concepts, it could be [1.324, 2.3434, 4.7619, etc.]. And the similarity between vectors is obviously something that computers can handle, such as Euclidean distance, cosine distance, etc. \n\nWe use [towhee](https://towhee.io/) to embed all images into vectors. towhee is a handy tool that integrates several frontier models and converts all images into vectors with just one line of code. ","pinned":false,"hidden":false,"mode":"md"},{"id":245,"value":"For example, the selected target image, which has been embedding into a 512-dimensional vector.","pinned":false,"hidden":false,"mode":"md"},{"id":647,"value":"{\n if (!(targetId >= 0)) return html`Please select a target image~`;\n return html`

The search target image

`;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":813,"value":"### The vector embeddings of the search target image","pinned":false,"hidden":false,"mode":"md"},{"id":269,"value":"{\n if (!(targetId >= 0)) return html`Please select a target image~`;\n await ivfflatFeder.initCoreAndViewPromise;\n return ivfflatFeder.core.id2vector[targetId];\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":47,"value":"

Then, Let's see how the search results came about!

\n\n

The straightforward algorithm is to traverse the entire database, calculate the distance between all vectors and the target vector, and pick the nearest top-k result from it. However, this is time-consuming when the data volume is large.

\n\n

To improve the query efficiency, data scientists have proposed methods to obtain approximate nearest neighbors by constructing indexes. Among them, Faiss ivf_flat is one of the most widely used indexing algorithms.

\n\n

Next, we will take you into the world of approximate nearest neighbors (ANN) and show how ivf_flat works.

\n","pinned":false,"hidden":false,"mode":"html"},{"id":49,"value":"

0. Before the search

At ivf_flat index construction, all vectors (17k+) are divided into 256 clusters according to k-means (set parameter nlist=256).

click on the overview button below to see the overview of ivf_flat, you can mouse on the cluster block to view the images included in the cluster

","pinned":false,"hidden":false,"mode":"html"},{"id":683,"value":"{\n targetId;\n \n const container = d3.create(\"div\");\n const containerEle = container.node();\n\n const button = playButton(\"Show overview of ivf_flat\");\n const buttonEle = button.node();\n containerEle.appendChild(buttonEle);\n\n const content = container.append(\"div\");\n const contentEle = content.node();\n button.clickHandler = () => {\n content.selectAll(\"*\").remove();\n contentEle.appendChild(ivfflatFeder.overview());\n };\n\n return containerEle;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":60,"value":"

Step 1. Coarse Search

\nWhen searching for the target vector, it is compared with the center vectors of 256 (nlist) clusters to find the nearest 8 vectors (set parameter nprobe=8). ivf_flat makes an approximation here that the final topk results are all in these nprobe clusters.","pinned":false,"hidden":false,"mode":"md"},{"id":690,"value":"{\n const container = d3.create(\"div\");\n const containerEle = container.node();\n\n const button = playButton(\"Show coarse-search of ivf_flat\");\n const buttonEle = button.node();\n containerEle.appendChild(buttonEle);\n\n const content = container.append(\"div\");\n const contentEle = content.node();\n button.clickHandler = () => {\n content.selectAll(\"*\").remove();\n contentEle.appendChild(\n targetId < 0\n ? d3.create(\"div\").text(selectInfo).node()\n : ivfflatFeder.searchById(targetId)\n );\n };\n\n return containerEle;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":63,"value":"

Step 2. Fine Search

\nIvf_flat will calculate the distance between the target vector and all the vectors in the nprobe cluster, and find the nearest 9 vectors (set the parameter k=9) as the final output.","pinned":false,"hidden":false,"mode":"md"},{"id":698,"value":"{\n const container = d3.create(\"div\");\n const containerEle = container.node();\n\n const button = playButton(\"Show fine-search of ivf_flat\");\n const buttonEle = button.node();\n containerEle.appendChild(buttonEle);\n\n const content = container.append(\"div\");\n const contentEle = content.node();\n button.clickHandler = () => {\n content.selectAll(\"*\").remove();\n if (targetId < 0)\n contentEle.appendChild(d3.create(\"div\").text(selectInfo).node());\n else {\n const view = ivfflatFeder.searchById(targetId);\n const viewContainer = d3.select(view);\n contentEle.appendChild(view);\n\n const timer = setInterval(() => {\n const loading = viewContainer.select(\"#feder-loading\");\n if (loading.empty()) {\n clearInterval(timer);\n const label = viewContainer\n .selectAll(\".panel-item-option\")\n .nodes()[1];\n d3.select(label).dispatch(\"click\");\n }\n }, 100);\n }\n };\n\n return containerEle;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":69,"value":"## Efficiency Analysis\n\nSince the dimensions of vectors are often large (e.g. 512, 1024, or more), the most time-consuming part of the vector search process is the computation of vector distances, so we only analyze the number of vector computations here.\n\nThe straightforward algorithm is to traverse the entire database, which requires at least **17,000** calculations, whereas with ivf_flat (with the current parameter settings), only about **1,000** calculations are performed (256 in coarse search + about 800 in fine search), which greatly speeds up the search process.\n\nBy adjusting nprobe, recall and search efficiency can be balanced. By increasing nprobe, more vectors can be searched and more error-tolerant space can be obtained, and by decreasing nprobe, less vectors can be searched and the computation time can be shortened.","pinned":false,"hidden":false,"mode":"md"},{"id":79,"value":"## What's more in Feder?\n\nMaybe you have noticed that Feder also supports **projection** layout when fine search, but after clicking it, you find it is a random layout. In fact, we have turned off the projection calculation in order to reduce the computing consumption. Want to know how to turn it on? \n\nJust find **viewParams** below and set **fineSearchWithProjection** to **true**~ \n
\nProjection is a widely used and effective method for analyzing high-dimensional data. If you have any findings, please feel free to share with us~\n\nIf you are interested in Feder's layout design, we also introduced the [data-driven voronoi layout based on ivf_flat](https://observablehq.com/@min-tian/feder-layout-ivf_flat/2) in observable.\n\nFeel free to visit the following links for more information~\n- **github**: https://github.com/zilliztech/feder\n- feder with **python** (colab): https://colab.research.google.com/drive/12L_oJPR-yFDlORpPondsqGNTPVsSsUwi#scrollTo=N3qqBAYxYcbt","pinned":false,"hidden":false,"mode":"md"},{"id":960,"value":"

Some feder screenshots

\n\n","pinned":false,"hidden":false,"mode":"html"},{"id":964,"value":"

","pinned":false,"hidden":false,"mode":"html"},{"id":18,"value":"## Data","pinned":false,"hidden":false,"mode":"md"},{"id":20,"value":"width = 900","pinned":false,"hidden":false,"mode":"ojs"},{"id":22,"value":"height = 600","pinned":false,"hidden":false,"mode":"ojs"},{"id":27,"value":"indexSource = \"faiss\"","pinned":false,"hidden":false,"mode":"ojs"},{"id":29,"value":"indexFilePath = \"https://assets.zilliz.com/faiss_ivf_flat_voc_17k_ab112eec72.index\"","pinned":false,"hidden":false,"mode":"ojs"},{"id":33,"value":"id2img = {\n const data = await d3.csv(\n \"https://assets.zilliz.com/voc_names_4cee9440b1.csv\"\n );\n const rowId2name = {};\n data.forEach((d, i) => (rowId2name[i] = d.name));\n const id2img = (rowId) =>\n rowId in rowId2name\n ? `https://assets.zilliz.com/voc2012/JPEGImages/${rowId2name[rowId]}`\n : null;\n return id2img;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":737,"value":"viewParams = ({\n width,\n height,\n mediaType: \"img\",\n mediaCallback: id2img,\n fineSearchWithProjection: false\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":31,"value":"ivfflatFeder = new Feder({\n source: indexSource,\n filePath: indexFilePath,\n viewParams,\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":718,"value":"ivfflatFeder.setSearchParams({ nprobe: 8, k: 12 });","pinned":false,"hidden":false,"mode":"ojs"},{"id":8,"value":"## Library","pinned":false,"hidden":false,"mode":"md"},{"id":10,"value":"d3 = require(\"d3\")","pinned":false,"hidden":false,"mode":"ojs"},{"id":12,"value":"FederModule = import(\"https://unpkg.com/@zilliz/feder@0.x\")","pinned":false,"hidden":false,"mode":"ojs"},{"id":14,"value":"Feder = FederModule.Feder","pinned":false,"hidden":false,"mode":"ojs"},{"id":141,"value":"randomSelect = (k, n) => {\n const res = []\n let t = Math.min(k, n);\n while (t) {\n const i = Math.floor(Math.random() * n);\n if (!res.includes(i)) {\n t--;\n res.push(i)\n }\n }\n return res\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":593,"value":"ZillizBlue = \"#175FFF\"","pinned":false,"hidden":false,"mode":"ojs"},{"id":566,"value":"$34","pinned":false,"hidden":false,"mode":"ojs"},{"id":887,"value":"$35","pinned":false,"hidden":false,"mode":"ojs"},{"id":893,"value":"$36","pinned":false,"hidden":false,"mode":"ojs"},{"id":672,"value":"selectInfo = 'Please select a target image~';","pinned":false,"hidden":false,"mode":"ojs"},{"id":962,"value":"","pinned":false,"hidden":false,"mode":"html"}],"files":"$W37","stdlib":"1","titling":"auto"}