草庐IT

mysql - MySQL 或 PostgreSQL 的汉明距离优化？

coder 2023-10-05 原文

我试图改进在 MySQL 数据库中搜索 pHashed 相似图像。 现在我比较 pHash 计数汉明距离是这样的:

SELECT * FROM images WHERE BIT_COUNT(hash ^ 2028359052535108275) <= 4

选择(引擎 MyISAM)的结果

  • 20000 行；查询时间 <>
  • 100000 行；查询时间 ~ 60ms # 这很好，直到它达到 150000 行
  • 300000 行；查询时间 ~ 150ms

所以查询时间的增加取决于表中的行数。

我也尝试在 stackoverflow 上找到的解决方案 Hamming distance on binary strings in SQL 

SELECT * FROM images WHERE 
BIT_COUNT(h1 ^ 11110011) + 
BIT_COUNT(h2 ^ 10110100) + 
BIT_COUNT(h3 ^ 11001001) + 
BIT_COUNT(h4 ^ 11010001) + 
BIT_COUNT(h5 ^ 00100011) + 
BIT_COUNT(h6 ^ 00010100) + 
BIT_COUNT(h7 ^ 00011111) + 
BIT_COUNT(h8 ^ 00001111) <= 4

第 300000 行；查询时间~240ms

我将数据库引擎更改为 PostgreSQL。 Translate this MySQL query to PyGreSQL 没有成功。 第 300000 行；查询时间~18s

是否有优化上述查询的解决方案？ 我的意思是优化不依赖于行数。

我解决这个问题的方法(工具)有限。 到目前为止，MySQL 似乎是最简单的解决方案，但我可以在每个开源数据库引擎上部署代码，这些引擎将在专用机器上与 Ruby 一起工作。 MsSQL 有一些现成的解决方案 https://stackoverflow.com/a/5930944/766217 (未测试)。也许有人知道如何为 MySQL 或 PostgreSQL 翻译它。

请根据一些代码或观察发布答案。我们在 stackoverflow.com 上有很多关于汉明距离的理论问题

谢谢!

最佳答案

在考虑算法的效率时，计算机科学家使用表示为 O(something) 的 order 的概念，其中 something 是 n 的函数，n 是被计算的事物的数量，在本例中为行。所以我们得到，随着时间的增加:

  • O(1) - 与项目数无关
  • O(log(n)) - 随着项目的对数增加
  • O(n) - 项目(你拥有的)的比例增加
  • O(n^2) - 随着项目的平方增加
  • O(n^3) - 等等
  • O(2^n) - 呈指数增长
  • O(n!) - 随着数字的阶乘增加

对于任何合理数量的 n (80+)，最后 2 个实际上是不可计算的。

只有最重要的项很重要，因为它在大 n 中占主导地位，所以 n^2 和 65*n^2+787*n+4656566 都是 O(n^2)

请记住，这是一个数学结构，算法在使用真实数据的真实硬件上使用真实软件所花费的时间可能会受到其他因素的严重影响(例如，O(n^2) 内存操作可能比O(n) 磁盘操作)。

对于您的问题，您需要遍历每一行并计算 BIT_COUNT(hash ^ 2028359052535108275) <= 4 .这是一个 O(n) 操作。

唯一可以改进的方法是利用索引，因为 b 树索引检索是一个 O(log(n)) 操作。

但是，因为您的列字段包含在一个函数中，所以不能使用该列的索引。您有 2 种可能性:

  1. 这是一个 SQL 服务器解决方案，我不知道它是否可以移植到 MySQL。使用公式 BIT_COUNT(hash ^ 2028359052535108275) 在表中创建持久计算列并在上面放一个索引。如果您需要更改位掩码，这不是合适的。
  2. 想出一种不使用 BIT_COUNT 函数进行按位算术的方法。

关于mysql - MySQL 或 PostgreSQL 的汉明距离优化？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/14925151/

汉明PostgreSQLBIT_COUNTstackoverflowCOUNTmysqlsqlquery-optimizationhamming-distancephash

有关mysql - MySQL 或 PostgreSQL 的汉明距离优化？的更多相关文章

  1. 使用canal同步MySQL数据到ES - 2

    文章目录一、概述简介原理模块二、配置Mysql使用版本环境要求1.操作系统2.mysql要求三、配置canal-server离线下载在线下载上传解压修改配置单机配置集群配置分库分表配置1.修改全局配置2.实例配置垂直分库水平分库3.修改group-instance.xml4.启动监听四、配置canal-adapter1修改启动配置2配置映射文件3启动ES数据同步查询所有订阅同步数据同步开关启动4.验证五、配置canal-admin一、概述简介canal是Alibaba旗下的一款开源项目，Java开发。基于数据库增量日志解析，提供增量数据订阅&消费。Git地址：https://github.co

  2. ruby-on-rails - 如何让 datamapper 与 postgresql 数据库一起工作？ - 2

    我已经找到了几个使用datamapper的示例，并且能够让它们正常工作。不过，所有这些示例都是针对sqlite数据库的。我正在尝试将数据映射器与postgresql一起使用。我将datamapper中的调用从sqlite3更改为postgres，并且我已经安装了dm-postgres-adapter。但它仍然不起作用。我还需要做什么？ 最佳答案 与SQLite不同，PostgreSQL不将数据库存储在单个文件中。在你拥有createdyourdatabase之后，尝试这样的事情:DataMapper.setup:default,{:

  3. ruby-on-rails - 无法安装 mysql2 0.3.14 gem - 2

    我看到其他人也遇到过类似的问题，但没有一个解决方案对我有用。0.3.14gem与其他gem文件一起存在。我已经完全按照此处指示完成了所有操作:https://github.com/brianmario/mysql2.我仍然得到以下信息。我不知道为什么安装程序指示它找不到include目录，因为我已经检查过它存在。thread.h文件存在，但不在ruby​​目录中。相反，它在这里:C:\RailsInstaller\DevKit\lib\perl5\5.8\msys\CORE\我正在运行Windows7并尝试在Aptana3中构建我的Rails项目。我的Ruby是1.9.3。$gemin

  4. ruby - 如何使用 ruby​​ mysql2 执行事务 - 2

    我已经开始使用mysql2gem。我试图弄清楚一些基本的事情——其中之一是如何明确地执行事务(对于批处理操作，比如多个INSERT/UPDATE查询)。在旧的ruby-mysql中，这是我的方法:client=Mysql.real_connect(...)inserts=["INSERTINTO...","UPDATE..WHEREid=..",#etc]client.autocommit(false)inserts.eachdo|ins|beginclient.query(ins)rescue#handleerrorsorabortentirelyendendclient.commi

  5. sql - 在 Rails Console for PostgreSQL 的表中显示数据 - 2

    我找到了这样的东西:Rails:Howtolistdatabasetables/objectsusingtheRailsconsole?这一行没问题:ActiveRecord::Base.connection.tables并返回所有表但是ActiveRecord::Base.connection.table_structure("users")产生错误:ActiveRecord::Base.connection.table_structure("projects")我认为table_structure不是Postgres方法。如何列出Postgres数据库的Rails控制台中表中的所有

  6. ruby-on-rails - Rails 迁移中的 PostgreSQL 点类型 - 2

    我想使用PostgreSQL中的point类型。我已经完成了:railsgmodelTestpoint:point最终的迁移是:classCreateTests当我运行时:rakedb:migrate结果是:==CreateTests:migrating====================================================--create_table(:tests)rakeaborted!Anerrorhasoccurred,thisandalllatermigrationscanceled:undefinedmethod`point'for#/hom

  7. ruby-on-rails - Ruby on Rails 单表继承(STI)和单元测试问题(使用 PostgreSQL) - 2

    我正在使用带有单个“帐户”表的STI模型来保存用户和技术人员的信息(即用户...8)错误:test_the_truth(用户测试):ActiveRecord::StatementInvalid:PGError:ERROR:关系“技术人员”不存在:从“技术人员”中删除...从本质上讲，标准框架不承认Technicians和Users表(或PostgreSQL称它们为“关系”)不存在，事实上，应该别名为Accounts。有什么想法吗？我对RoR比较陌生，不知道如何解决这个问题而又不完全删除STI。 最佳答案 原来问题是由于存在:./te

  8. ruby - rails 3.2.2(或 3.2.1)+ Postgresql 9.1.3 + Ubuntu 11.10 连接错误 - 2

    我正在使用PostgreSQL9.1.3(x86_64-pc-linux-gnu上的PostgreSQL9.1.3，由gcc-4.6.real(Ubuntu/Linaro4.6.1-9ubuntu3)4.6.1，64位编译)和在ubuntu11.10上运行3.2.2或3.2.1。现在，我可以使用以下命令连接PostgreSQLsupostgres输入密码我可以看到postgres=#我将以下详细信息放在我的config/database.yml中并执行“railsdb”，它工作正常。开发:adapter:postgresqlencoding:utf8reconnect:falsedat

  9. 最新版人脸识别小程序 图片识别 生成二维码签到 地图上选点进行位置签到 计算签到距离 课程会议活动打卡日常考勤 上课签到打卡考勤口令签到 - 2

    技术选型1，前端小程序原生MINA框架cssJavaScriptWxml2，管理后台云开发Cms内容管理系统web网页3，数据后台小程序云开发云函数云开发数据库（基于MongoDB）云存储4，人脸识别算法基于百度智能云实现人脸识别一，用户端效果图预览老规矩我们先来看效果图，如果效果图符合你的需求，就继续往下看，如果不符合你的需求，可以跳过。1-1，登录注册页可以看到登录页有注册入口，注册页如下我们的注册，需要管理员审核，审核通过后才可以正常登录使用小程序1-2，个人中心页登录成功以后，我们会进入个人中心页我们在个人中心页可以注册人脸，因为我们做人脸识别签到，需要先注册人脸才可以进行人脸比对，进

  10. ruby-on-rails - 当我通过 rvm 使用 rails3 时，如何在 ubuntu 上安装 mysql2 gem？ - 2

    我正在尝试绕过rails配置这个极其复杂的迷宫。到目前为止，我设法在ubuntu上设置了rvm(出于某种原因，ruby在ubuntu存储库中已经过时了)。我设法建立了一个Rails项目。我希望我的测试项目使用mysql而不是mysqlite。当我尝试“rakedb:migrate”时，出现错误:“!!!缺少mysql2gem。将其添加到您的Gemfile:gem'mysql2'”当我尝试“geminstallmysql”时，出现错误，告诉我需要为安装命令提供参数。但是，参数列表很大，我不知道该选择哪些。如何通过在ubuntu上运行的rvm和mysql获取rails3？谢谢。

随机推荐