2b:null 2c:["$","title",null,{"children":"What happens when Reverse-Image-Search? How to understand embedding? Visualize Faiss IVF_Flat with Feder! | min tian | Observable"}] 32:T480,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", "cover") .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:T47c,{ const container = d3.create("div"); const button = customButton("Search top-k imgs"); const containerDiv = container.node(); containerDiv.appendChild(button.node()); const topKImgsContainer = container.append("div"); 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", "cover") .style("border-radius", "4px"); return container.node(); }; button.on("click", () => { const content = renderGetTopKRes(targetId); topKImgsContainer.selectAll("*").remove(); topKImgsContainer.node().appendChild(content); }); return container.node(); }34:T5fa,## Efficiency Analysis 效率分析 Since 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.
由于向量的维度常常很大（例如512，1024，或者更多），向量搜索过程中最耗时的部分是向量距离的计算，所以我们这里只分析向量的计算次数。 The most 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.
最直接的算法是遍历整个数据库，这至少需要计算**17,000**次，而在使用了ivf_flat之后（当前参数设置下），只计算了**1,000次左右**（粗略查询256次 + 精细查询800次左右），这大大加速了搜索结果的获取。 By 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.
通过调整nprobe，可以平衡召回率和搜索效率。增大nprobe，可以搜索更多的向量，获取更多的容错空间，减小nprobe，可以减少搜索的向量，缩短计算时间。35:T69d,## What's more in Feder? Feder还有哪些新鲜有趣的内容？ Maybe 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? Just find **viewParams** below and set **fineSearchWithProjection** to **true**~ Projection is a widely used and effective method for analyzing high-dimensional data. If you have any findings, please feel free to share with us~
也许细心的你已经发现了，在精细查询时，Feder还支持投影布局，但是点击之后发现是随机布局。其实是我们为了减少运算消耗，关闭了投影计算。想知道怎么开启吗？只需要在下方找到`viewParams`，将其中的`fineSearchWithProjection`设置为`true`即可~降维投影是分析高维数据的常见方法，如果你有什么发现欢迎和大家一起分享~ If 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.
如果你对Feder的布局设计很感兴趣，我们也在observable介绍了[基于ivf_flat的数据驱动的voronoi布局计算原理](https://observablehq.com/@min-tian/feder-layout-ivf_flat/2)。 Feel free to visit the following links for more information~
欢迎访问下面的链接获取更多信息~ - **github**: https://github.com/zilliztech/feder - feder with **python** (colab): https://colab.research.google.com/drive/12L_oJPR-yFDlORpPondsqGNTPVsSsUwi#scrollTo=N3qqBAYxYcbt36:[{"id":"8ffecc652a8dfa22ac176987bece82603b90d9067e2fa4ff2c05ca4647fc76ee02f51edc1ed86cad3ebe8e60e01d25af8a2bdd43910d9682fdec7ba5f1989eae","href":"https://static.observableusercontent.com/files/8ffecc652a8dfa22ac176987bece82603b90d9067e2fa4ff2c05ca4647fc76ee02f51edc1ed86cad3ebe8e60e01d25af8a2bdd43910d9682fdec7ba5f1989eae","name":"image.png","type":"image/png","lastModified":1657014655044.595,"size":142784}] 2f:{"id":"c765cc98f65b15e3","slug":"reverse-image-search-feder-faiss-ivf_flat-visualizations-cn","title":"What happens when Reverse-Image-Search? How to understand embedding? Visualize Faiss IVF_Flat with Feder!","thumbnail":"06aa6b7a67723b4e9dd4894315eaeca26981c9819c4c4b5648a7d62c179a7161","access_level":"public","create_time":"$D2022-07-05T09:50:55.044Z","update_time":"$D2022-07-05T10:26:45.103Z","view_time":null,"first_public_time":"$D2022-07-05T10:29:57.396Z","fork":{"id":"3baf28efc6cfc1ba","slug":"reverse-image-search-feder-faiss-ivf_flat-visualizations","title":"Understanding vector embeddings with Feder by a reverse image search example (IVF_FLAT)!","owner":{"id":"20c79daf14e996c0","login":"min-tian","name":"min tian"}},"stars":1,"starred":false,"owner":{"type":"team","id":"20c79daf14e996c0","login":"min-tian","name":"min tian","avatar_url":"https://avatars-next.observableusercontent.com/011f8ba05b1eacda7c400d1e8e447b6cddff33f1e2127b213ed48b57f5dbad17","tier":"starter_2024"},"version":778,"publish_version":778,"role":null,"authored":false,"authors":[{"type":"individual","id":"24744ff9bd8512be","login":"min-tian","name":"min tian","avatar_url":"https://avatars-next.observableusercontent.com/011f8ba05b1eacda7c400d1e8e447b6cddff33f1e2127b213ed48b57f5dbad17","tier":null}],"members":[{"type":"individual","id":"24744ff9bd8512be","login":"min-tian","name":"min tian","avatar_url":"https://avatars-next.observableusercontent.com/011f8ba05b1eacda7c400d1e8e447b6cddff33f1e2127b213ed48b57f5dbad17","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":true,"trashed":false,"subscribed":null,"forks":2,"collection":null,"type":"notebook","body":{"title":"What happens when Reverse-Image-Search? How to understand embedding? Visualize Faiss IVF_Flat with Feder!","cells":[{"id":0,"value":"# What happens when Reverse-Image-Search? How to understand embedding? Visualize Faiss IVF_Flat with [Feder](https://github.com/zilliztech/feder)!\n以图搜图是如何实现的？嵌入向量要如何理解？我们将使用可视化工具[Feder](https://github.com/zilliztech/feder)来揭开ivf_flat(faiss)的神秘面纱！","pinned":false,"hidden":false,"mode":"md"},{"id":6,"value":"## Pick an image as a search target\n挑选一个你喜欢的图片作为搜索目标","pinned":false,"hidden":false,"mode":"md"},{"id":571,"value":"viewof optionList = {\n const container = d3.create(\"div\");\n const button = customButton(\"Refresh Options\");\n container.node().value = randomSelect(8, 10000);\n\n const update = () => {\n const optionList = randomSelect(8, 10000);\n container.node().value = optionList;\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":45,"value":"## Get the most similar top-12 images searched in VOC 2012 DataSet (17k+ images) using faiss's ivf_flat\n使用faiss的ivf_flat在VOC_2012数据集（包括17,000+张图片）中搜索到的最相似的top-12图片\n
\nDataset download: http://host.robots.ox.ac.uk/pascal/VOC/voc2012/VOCtrainval_11-May-2012.tar","pinned":false,"hidden":false,"mode":"md"},{"id":562,"value":"$33","pinned":false,"hidden":false,"mode":"ojs"},{"id":83,"value":"## You may be puzzled by how computers understand similarity.\n\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\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那什么是嵌入向量呢？举个例子，一个苹果，可以抽象为[红色，球形，甜，芳香，长在树上, ...]等多个特征，任何与这些特征相似（不一定完全相同）的我们都可以叫做苹果。如果用数字来对应这些概念，可能是[1.324, 2.3434, 4.7619, ...]。而向量之间的相似度显然是计算机可以处理的，比如欧氏距离，余弦距离等。\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.
\n我们使用[towhee](https://towhee.io/)将所有图片都编码为向量。towhee是一个内部集成了多个前沿模型，只需要一行代码就可以将所有图片转化为向量的便捷工具。","pinned":false,"hidden":false,"mode":"md"},{"id":245,"value":"For example, the selected target image, which has been embedding into a 512-dimensional vector.
\n例如，你所选择的目标图片，已经被编码为一个512维向量","pinned":false,"hidden":false,"mode":"md"},{"id":647,"value":"{\n if (!(targetId >= 0)) return html`Please select a target image~`;\n return html`

`;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"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":"## Let's see how the search results came about! Ivf_flat has a two-step query: coarse-search and fine-search.\n让我们一起看看这个结果是怎么搜索到的！ivf_flat总共有两级查询，分别是粗略查询和精细查询","pinned":false,"hidden":false,"mode":"md"},{"id":49,"value":"### 0. Before the search\nAt ivf_flat index construction, all vectors (17k+) are divided into 256 clusters according to k-means (set parameter nlist=256)
\n在搜索之前，即ivf_flat索引构建时，将所有向量（17k+）根据k-means分为256个聚类（设置参数nlist=256）","pinned":false,"hidden":false,"mode":"md"},{"id":683,"value":"{\n targetId;\n \n const container = d3.create(\"div\");\n const containerEle = container.node();\n\n const button = customButton(\"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":"### 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.\n
\n粗略查询。得到目标向量后，将其与256（nlist）个聚类的中心向量对比，找出最近的8个向量（设置参数nprobe=8）。ivf_flat在这里做了一个近似，认为最终需要的topk结果都存在于这nprobe个聚类之中。","pinned":false,"hidden":false,"mode":"md"},{"id":690,"value":"{\n const container = d3.create(\"div\");\n const containerEle = container.node();\n\n const button = customButton(\"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":"### 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.
\n精细查询。接下来ivf_flat将会计算目标向量和这nprobe个聚类内所有向量的距离，并从中找出最近的9（设置参数为k=9）个向量作为最终输出。","pinned":false,"hidden":false,"mode":"md"},{"id":698,"value":"{\n const container = d3.create(\"div\");\n const containerEle = container.node();\n\n const button = customButton(\"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":"$34","pinned":false,"hidden":false,"mode":"md"},{"id":79,"value":"$35","pinned":false,"hidden":false,"mode":"md"},{"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\")","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":"customButton = (label) => {\n const container = d3\n .create(\"div\")\n .style(\"display\", \"flex\")\n .style(\"flex-direction\", \"row\")\n .style(\"margin-bottom\", \"20px\");\n const div = container.append(\"div\");\n div\n .style(\"color\", \"#fff\")\n .style(\"background\", ZillizBlue)\n .style(\"display\", \"flex\")\n .style(\"align-items\", \"center\")\n .style(\"padding\", \"6px 16px\")\n .style(\"font-size\", \"20px\")\n .style(\"border-radius\", \"6px\")\n .style(\"cursor\", \"pointer\")\n .on(\"mouseenter\", function () {\n d3.select(this).style(\"opacity\", 0.8);\n })\n .on(\"mouseout\", function () {\n d3.select(this).style(\"opacity\", 1);\n });\n div.text(label);\n container.clickHandler = () => {};\n div.on(\"click\", () => container.clickHandler());\n return container;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":672,"value":"selectInfo = 'Please select a target image~';","pinned":false,"hidden":false,"mode":"ojs"}],"files":"$W36","stdlib":"1","titling":"auto"}} 30:"$2f:body"