Posted on | In

背景

在空间索引类问题当中，一个最普遍而又最重要的问题是：”给定你某个点的坐标，你如何能够在海量的数据点中找到他所在的区域以及最靠近他的点”？

最常见的应用就像是**POI(Point of Interest)**的查询了，比方说客户在路上突然想吃饭了，那么我就要根据他的位置查询最近的餐馆并根据这个做出推荐。

通常情况下，一提到查找类问题，我们就会想到二分查找或者是B树查找。但是问题在于我们不仅要找到这个点，而且要找到这个点附近的点。因此对于以经纬度来确定的坐标又不好直接进行二分查找。（如果是直接用数据库索引的话，由于数据库通常是B树索引和Hash索引，因此查找效率并没有提高。）

通常情况下我们会用R树、Kd树或者是四叉树之类的数据结构来存储这些点从而高效的做到临近点的查找。但是这些数据结构通常都会存在数据冗余，以及不稳定的查改效率；况且抛开他们的时间效率、空间效率以及算法复杂度不谈，用了这些数据结构也就意味这我们放弃了使用现成强大的数据库而自己编写数据查改系统，这显然是繁琐而又没有必要的过程。而且当系统需要扩展到分布式计算的时候就更不如使用那些分布式的数据库了。

这时我们就会想到，如果能够把一个二维的信息转化为一维的数据加以存储，那么我们不就可以直接存储到数据库中做到快速的查找了么？

GeoHash做的就是这个工作。

简述

GeoHash是由Gustavo Niemeyer（大概于2013年）提出的，目的原本是为地球上的每一个点（根据经纬度）确定一条短的URL作为唯一标识。只是后来被广泛的应用到空间检索方面、尤其是之前提到的POI查询中。这个服务一直在http://geohash.org上，上面还有一些具体的介绍。

GeoHash所做的事就是把一个坐标点映射到一个字符串上，每一个字符串代表的就是一个以经纬度划分的矩形区域。比方下面的图就展现了北京地区所在的九个区域，分别是WX4ER、WX4G2等等。


于此同时，每一个区域又可以继续划分为许多个小区域，如下图所示，WX4G0就包含了WX4G09、WX4G0C、WX4G08等等。而且每一个子区域的GeoHash值都是在父区域后面拓展一个字符。


这样就形成了一个层次分明的结构，越高级的区域GeoHash值越短，表示的区域最大；越小的区域GeoHash值越长，表示的区域越小。

算法

定位算法：

事实上GeoHash算法也十分简单，根据上面的意义我们很容易想到他用的是类似四叉树的方法来寻找一个点；换句话说就是不停的在经度和纬度上进行二分类，最终确定到想要的精度，划分的过程下图所示。

交替在两个方向进行分割，一个区域计为0，一个区域记为1，并将结果追加在父区域GeoHash值的后面。不断的进行划分直到得到了想要的深度。对于每一个区域最后会得到一个二进制的字符串，然后每5位为一组，用0-9 b-z（去掉a, i, l, o）进行Base32编码即可得到该区域经过编码后的GeoHash值。当然，编码这个步骤只是为了让结果看上去变短而已，实际应用中可以把它变成一个二进制数（由于存在前导0，所以要在最前面加一个1），当然直接用字符串的形式也未尝不可。

有一个小细节，就是区域之间会有边界，那么边界上的点属于哪里呢？我的处理是所有的区域都只是包含经度和纬度方向上的左闭右开区间。

邻居查找算法：

如果想要查找某个点附近的Top m个临近点，我们显然不会直接扫描地图中所有的点（这样效率会极其低下），而是用上面的定位算法，将该点定位到一个比较小的区域里（这个区域里有n个临近点，且n>m），然后再扫描这个较小区域里的所有点，用自己定义的权重公式，取出最符合的点。这个方法一般叫做“Filter and Refine”方法，即”先过滤，后提纯“。

既然如此，通过上面的定位算法，我们可以将这个点定位到一个比较小的区域里，然后查找该区域的所有点即可。不过问题来了，由于GeoHash编码并不能保证查询的点是在他所在区域的中心，这就导致了下图中的问题：

显然，红色的点属于最中间的区域，直接查找该区域会得到他下方的绿色点是最接近的点。但是由于这个点比较靠近区域的边界，事实上更接近的点却是位于他上方的相邻格子的绿色的点。因此我们并不能仅仅查找他当前区域内的所有点，而是要查找以该区域为中心的九个区域范围。（当然这样也有可能存在着查找错误的问题，但是可能性就大大降低了）。

随便在网上找了下，没有找到比较方便的查找邻居的算法（当然预处理保存的除外），于是我就想了一个朴素简单的方法：我们可以在定位某点的时候，记录下该点所在区域的经纬度范围，然后只要取出这个区域外的八个点，然后对这八个点分别跑八次定位算法就可以求出他附近的所有区域了。

临近点的查找策略：

由于GeoHash对一个坐标点的编码可以有不同的深度（精度），因此在临近点的查找中也就存在了层次的选择策略。我们显然不能一概而论的将每个点都查找到相同的层次，否则要么由于精度太高而找不到临近点，要么由于精度太低而找到太多的临近点。我的策略是：

  1. 首先确定一个最高的精度，我们认为在这个精度下的所有区域中的点都是极少的；
  2. 然后确定一个期望的临近点个数k；
  3. 对于某个坐标点，计算出在最高精度下的区域时由邻居查找算法得到的临近点的个数b。
  4. 如果b小于k，那么就把精度提高一层（即将其GeoHash编码末尾的几个字符删除）继续执行邻居查找算法直到找到的临近点的个数大于等于k；
  5. 用邻居查找算法查询当前精度下的所有临近点并将其作为”Filter”后的候选集供后续的“Refine”。
  6. 注意到这个参数k非常重要，当他的值小的时候算法的准确率会下降，但是效率会提高；反之准确率会提高，效率会下降。因此，当我们期望的运行时间一定时，我们可以通过用启发式的方法，根据期望运行的时间、路径中点的个数等因素调节参数k，从而达到效率和准确率的最佳平衡。

精度

最初Gustavo Niemeyer在定义GeoHash编码的时候是以全球的坐标作为总的区域来分的，因此他计算出了不同编码长度的GeoHash区域对应的范围。不过我们平常自己写的时候并不需要覆盖全球的所有地区，而且也不必用Base32来编码。如果非得那拿全球作为总的区域来划分，那么我们可以很容易的计算出来只要最多在经度和纬度上分别划分24次左右就可以使最小的区块达到1m的精度。在没有缓存的情况下也只要循环二十几次就可以定位到需要的区域，效率还是很高的。

与R树的比较

一、稳定性：GeoHash编码与数据集的大小无关，因此对于任意大的数据集，他的定位和查找效率都非常高（常数时间）；而R树在建树时需要花费至少$O(nlogN)$的复杂度（事实上为了保持树的平衡还会花费更多的时间），况且R树家族的数据结构基本都会存在区域重叠，当数据量大的时候无论是建树还是查找都会很费时。

二、拓展性：GeoHash可以与当前的任何一种数据库管理系统结合使用，不仅可以享受数据库的优化，而且还可以利用NoSQL数据库非常轻松的实现分布式存储和查找；R树则一般是在内存中进行查找，虽然现今大多数数据库也有空间索引的引擎，但是标准不统一，性能也不是很稳定，而且大规模批量插入数据时性能也不理想。

参考

GeoHash核心原理解析
wiki–GeoHash
基于GeoHash的面数据区域查询

Posted on | In

有了自己的网站当然也想弄个自己的邮箱了，虽然不一定用得上，但是搞一个自己域名的邮件系统还是很酷的。（前提是已经购买了域名）

一些复杂的文件配置和指令操作就不细研究了，毕竟现在也用不上，下面就简单搭建一个能够首发邮件的服务器。

安装PostFix

postfix就是我们的邮件服务器了，用$sudo apt install postfix 即可安装。

安装好了我们的服务就算是启动了，下面我们就用他来发邮件。

（注意，此时的本机的邮箱地址就是当前的”用户名@域名“，因此注册自己的邮箱的过程其实就是添加用户的过程）

发邮件

bash中输入 $telnet localhost 25 ，即登陆本机的邮件服务端口，进入postfix提示符：

1
2
3
4
5
myths@Business:~$ telnet localhost 25
Trying ::1...
Connected to localhost.
Escape character is '^]'.
220 Business ESMTP Postfix (Ubuntu)

然后就按照下面的格式输入正文：

1
2
3
4
5
6
7
8
9
10
11
ehlo localhost
mail from: myths@localhost
rcpt to: test@localhost
data
Subjet: My first mail on Postfix
Hi,
Are you there?
regards,
Admin
.
quit

即，在ehlo后输入名称，mail from: 后输入自己的邮件地址，rcpt to: 后面输入目的的邮件地址，data后输入正文并以”<回车><点><回车>”作为正文结束标志。

最后再输入quit关闭终端。

安装mailutils

用$sudo apt install mailtuils安装，然后就可以用这个工具查看邮件了。

收邮件

登陆到需要收邮件的用户，输入mail，即可进入mail的终端。这里会提示类似下面的信息：

1
2
3
4
myths@Business:~$ mail
"/var/mail/myths": 1 message 1 new
>N   1 myths@localhost     三 5月 18 14:2  16/393
?

这样告诉了我们未读的邮件。我们可以输入邮件前面的序号”１“来查看信息。

当然还有其他很多的命令和配置，不过既然一时半会用不到，我们暂时也就不研究了。

用上面的方法我们基本上可以把这个邮件服务器当成商业邮箱来用了，不过在跟qq邮箱进行互发的时候发现qq的文本还得先用base64解码才行。。。也是麻烦。。

Posted on | In

现在我需要在Mysql里插入大量的数据大约1000w，目测会比较耗时。所以现在就像测试一下到底用什么插入数据的方法比较快捷高效。

下面就针对每一种方法分别测试不同数据量下的插入效率。测试数据库的基本与操作如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
mysql> create database test;
Query OK, 1 row affected (0.02 sec)
mysql> use test;
Database changed
mysql> create table mytable(id int primary key auto_increment ,value varchar(50));
Query OK, 0 rows affected (0.35 sec)
mysql> desc mytable;
+-------+-------------+------+-----+---------+----------------+
| Field | Type        | Null | Key | Default | Extra          |
+-------+-------------+------+-----+---------+----------------+
| id    | int(11)     | NO   | PRI | NULL    | auto_increment |
| value | varchar(50) | YES  |     | NULL    |                |
+-------+-------------+------+-----+---------+----------------+
2 rows in set (0.02 sec)

方便测试，这里建了一个表，两个字段，一个是自增的id，另一个是字符串表示内容。

测试时每次实验结束都要mysql> truncate mytable，来清空已存在的表。

方法一：逐条插入

测试代码：（中间有1000条insert语句，用vim复制粘贴比较方便，写完后保存到a.sql，然后在mysql提示符中输入source a.sql）

1
2
3
4
5
6
7
set @start=(select current_timestamp(6));
insert into mytable values(null,"value");
......
insert into mytable values(null,"value");
set @end=(select current_timestamp(6));
select @start;
select @end;

输出结果：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
Query OK, 1 row affected (0.03 sec)
......
Query OK, 1 row affected (0.03 sec)
Query OK, 0 rows affected (0.00 sec)

+----------------------------+
| @start                     |
+----------------------------+
| 2016-05-05 23:06:51.267029 |
+----------------------------+
1 row in set (0.00 sec)

+----------------------------+
| @end                       |
+----------------------------+
| 2016-05-05 23:07:22.831889 |
+----------------------------+
1 row in set (0.00 sec)

总共耗时31.56486s，事实上几乎每条语句花的时间是差不多的，基本就是30ms。

这样子1000w的数据就得花87h。

至于更大的数据量也就不试了，这种方法肯定不可取。

方法二：基于事务的批量插入

实际上就是把这么多的查询放在一个事务中。事实上方法一中没一条语句都开了一个事务，因此才会特别慢。

测试代码：（与方法一基本类似，主要添加两行，由于比较快，这里测试了多种数据量）

1
2
3
4
5
6
7
8
9
set @start=(select current_timestamp(6));
start transaction;
insert into mytable values(null,"value");
......
insert into mytable values(null,"value");
commit;
set @end=(select current_timestamp(6));
select @start;
select @end;

测试结果：

1
2
3
4
5
数据量      时间(s)
1k         0.1458
1w         1.0793
10w        5.546006
100w       38.930997

看出来基本是对数时间，效率还是比较高的。

方法三：单条语句一次插入多组数据

就是一条insert一次插入多个value。

测试代码：

1
2
3
4
insert into mytable values  (null,"value"),
                            (null,"value"),
                             ......
                            (null,"value");

测试结果：

1
2
3
4
5
数据量      时间(s)
1k         0.15
1w         0.80
10w        2.14
100w       *

看上去也是对数时间，而且比方法二要稍微快一点。不过问题在于单次SQL语句是有缓冲区大小限制的，虽然可以修改配置让他变大，但也不能太大。所以在插入大批量的数据时也用不了。

方法四：导入数据文件

将数数据写成数据文件直接导入（参照上一节）。

数据文件（a.dat）：

1
2
3
4
5
null    value
null    value
.....
null    value
null    value

测试代码：

1
mysql> load data local infile "a.dat" into table mytable;

测试结果：

1
2
3
4
5
6
数据量      时间(s)
1k         0.13
1w         0.75
10w        1.97
100w       6.75
1000w      58.18

时间最快，就是他了。。。。

Posted on | In

第一次真正意义上使用数据库，当然是从简单方便的mysql开始了，咱们不好高骛远扯些有的没的。

对于mysql来说虽然可以用phpmyadmin这样的东西，但是这还是会略显臃肿，既然是程序员，还是尽量使用简单清楚的命令行来写吧～～

第一次系统的搞这个难免摸不着头脑，下面就一步一步开始学习吧。

登陆和退出

登陆时用如下命令即可：

1
mysql -h 主机地址 -u 用户名 －p

其中很明显-h是指host，-u是指user，-p是指passwd。

这时候命令行会等待我们输入密码，这时候输入密码即可（没有回显）。

需要注意的是，如果想在一条语句里面输密码的话，-p后面是要马上接密码，中间不能有空格（显然这时候输的密码是会被回显出来的）。

登陆后，shell的提示符就会变成mysql的提示符了：

1
mysql>

在这里输入适当的语句并以”;”结尾即可。

退出时输入exit或者Ctrl+d都可以。

选择数据库和表

显示数据库

1
mysql> show databases;

创建数据库

1
mysql> create database mydatabase;

使用该数据库

1
mysql> use mydatabase;

显示数据库中所有的表

1
mysql> show tables;

删除表

1
mysql> drop table  mydatabase;

显示表结构

1
mysql> describe mytable;

or

1
mysql> desc mytable;

显示格式如下：

1
2
3
4
5
6
7
8
mysql> desc mytable;
+-------+-------------+------+-----+---------+----------------+
| Field | Type        | Null | Key | Default | Extra          |
+-------+-------------+------+-----+---------+----------------+
| id    | int(11)     | NO   | PRI | NULL    | auto_increment |
| value | varchar(50) | YES  |     | NULL    |                |
+-------+-------------+------+-----+---------+----------------+
2 rows in set (0.00 sec)

增删查改

增删查改的内容就是普通的sql语句了，这里不做解释，需要的时候再找也不迟。

批处理

导入数据

对于需要导入大量数据的时候，我们可以将需要的数据写成一个数据文件，数据文件中每一行就是一条记录；每条记录中的字段是按照表中的字段顺序排列，用TAB键进行分割。最后输入以下命令：

1
mysql> load data local infile "b.txt" into table mytable;

上面是将b.txt中的数据导入到mytable表中，这个文件名需要加引号。

需要注意的是数据文件中的字符串是不用加引号的，而且也可以直接写null。

执行SQL命令

对于现成的sql命令，我们可以在mysql提示符中直接这样加以执行。

1
mysql> source a.sql

这个文件名不用加引号。

或者也可以在bash中执行：

1
$mysql -h localhost -u root -p <a.sql> ans.txt

其中ans.txt是查询的结果，尖括号不可以省略，输出文件也不可以省略。通过这个方法我们就能把执行结果写入文件了。

存储过程

存储过程感觉就是一种函数，可以执行一些简单的逻辑，封装了零零散散的SQL语句。

修改标志

在创建过程之前我们需要修改下语句的结束标志，因为过程本身是一条SQL语句，但是过程又是由多条SQL语句组成的，这样我们就无法判断过程的结束标志了。因此我们需要修改下外层的结束标志，默认的结束标志是”;”，我们可以如下修改成其他的标志：

1
mysql> delimiter $

这样SQL语句的结束标志就标称了”$”，这样我们就可以在过程内部仍然用”;”作为单个语句的结束标志了。不过最后我们还是要记得把他修改回常用的标志“;”；

创建过程

1
2
3
4
mysql>create procedure mypro()
    ->begin
    ->select * from mytable;
    ->end$

这样我们就创建了一个简单的过程mypro。这个过程是数据库级的，因此他是归属于我们当前选择的数据库的。

执行过程

1
mysql> call mypro()

call下即可。

操作语言

过程中我们经常会用到选择或循环之类的控制语句，这些东西的语法类似pascal，具体用到的时候查下即可，这里不做解释。

查看和删除过程

当然，我们需要对过程进行管理：

查看当前数据库中的过程：

1
mysql> select `name` from mysql.proc where db = 'your_db_name' and `type` = 'PROCEDURE'；

把your_db_name换成自己的数据库名即可。

删除某个过程：

1
mysql> drop procedure mypro;

参考资料

MySQL语法大全_自己整理的学习笔记
MySQL用文本方式将数据装入一个数据库表
MySQL存储过程详解 mysql 存储过程

Posted on | In

简述

编辑距离（Edit Distance），又称Levenshtein距离，原本是用来描述指两个字串之间，由一个转成另一个所需的最少编辑操作次数。这里的”编辑操作“是指“插入”、“删除”和“修改”。是由俄罗斯科学家Vladimir Levenshtein在1965年提出的概念。他通常就被用作一种相似度计算函数，尤其在自然语言处理方面。

问题描述

具体的讲，用编辑距离来描述处理路径相似度问题需要解决的是如下的问题，这个问题又叫”Edit Distance on Real sequence“(解决的方法就叫EDR算法)：

给定两个序列$(A_1,A_2,A_3,A_4…A_n)$和$(B_1,B_2,B_3,B_4…B_m)$，现在我们需要将其中一个序列改成另一个序列（反之亦然，易证相互转换的编辑距离是相等的），且我们一次只能对一个元素做插入、修改、删除中的一个操作。我们将变换所需的最小步数记为$EDR(A,B)$，这个值就可以作为两个序列相异度的一个量度。当然，跟LCSS一样，判断两个点”相等“还需要设定一个阈值$\varepsilon$，距离小于这个阈值的点可以被认为是”相等“的（不过论文中认为只有两个点的所有维度上的距离只差都小于这个阈值才被判断为相等，虽然我认为意思都差不多）。如下例：

其中黑线表示目标路径，红色实线表示当前路径，红色虚线表示改变后的路径。显然他们的编辑距离是３，包含两个插入操作、一个替换操作。

算法

简单dp。

对于序列$A[1:n],B[1:m]$，令$EDR[i,j]$表示$A[1:i],B[1:j]$之间的编辑距离；$\varepsilon$表示判断两点相等的阈值；$subcost[i][j]$的值表示$A[i],B[j]$是否相等，若是则取１，若否则取０。那么：

$$EDR[i,j]=\left\{\begin{matrix}m&if\ i=0\\n&if\ j=0\\min\left\{\begin{aligned}EDR[i-1][j-1]+subcost[i][j]\\EDR[i][j-1]+1\\EDR[i-1][j]+1\end{aligned}\right.&otherwise\end{matrix}\right.$$

根据这个递推式就可以求出编辑距离了。

其他处理

通常情况下这种距离在进行对比的时候都会进行归一化。这么做的基础当然是认为路径的相似度主要是考虑形状而不考虑位置）。既然是需要用阈值来判断相等，当然还是将路径的尺度固定到一个相对稳定的度量范围内才更有适用性。归一化的操作也非常简单，就是对于待归一化的路径点的每一个维度$x_k$，令他的值等于$\frac{x_k-\mu_x}{\sigma_x}$，其中$\mu_x,\sigma_x$分别表示该维度下的坐标的平均值和标准差。

总结

用EDR算法表示的路径相似度，有着对噪声不敏感的特点。但是他所表示的意义不是非常好（表示路径之间转换的操作数而跟距离没啥关系），而且确定阈值的过程还是很麻烦的。

参考

编辑距离
Edit distance
Robust and Fast Similarity Search for Moving Object Trajectories

Posted on | In

简述

距离归并算法（Merge Distance）也是一种计算路径相似度的算法（其实“路径归并”是我自己瞎翻译的，因为没有找到更加官方的中文翻译）。跟DTW，LCSS之类不同，他提出来时间不算长，但是思想也是十分简单的。计算方便理解容易，也是进行路径相似度匹配的不错的思路。

问题描述

MD算法解决的问题是，给定两个序列$(A_1,A_2,A_3,A_4…A_n)$和$(B_1,B_2,B_3,B_4…B_m)$，其中每一个元素可以都可以是一个二维坐标点或者是更高维度的坐标。现在我们需要找到一条路径，使他经过这两个序列的所有点，且保证若$i < j$那么$A_j$一定在$A_i$后面出现（对于$B$亦然）。显然这样我们可以有多种结果，那么我们只要取最短的那个路径来作为最后能够代表他们相似度的路径。具体要求如下图所示：

对于左边的图，下面的那个路径就是对上面的路径进行归并后的最短路径；对于右边的图，绿色的实线路径就是对蓝色和红色的虚线路径归并后的最短路径。

Merge Distance算法就是为了求出这个最短的路径长度。

算法

简单dp。

对于序列$A[1:n],B[1:m]$，令$MDa[i][j]$表示以$A[i]$为终点的序列$A[1:i]$和$B[1:j]$所形成的最短路径的长度；令$MDb[i][j]$表示以$B[j]$为终点的序列$A[1:i]$和$B[1:j]$所形成的最短路径的长度；$dis(X,Y)$表示$X$和$Y$之间的距离。这样我们就可以构造如下的递推关系式：

$i=1:$

$$MDa[i][j]=dis(A[i],B[j])+\sum_{k=2}^{j}dis(B[k-1],B[k])$$

$j=1:$

$$MDb[i][j]=dis(A[i],B[j])+\sum_{k=2}^{i}dis(A[k-1],A[k])$$

$for\ 1< i\leq n,1\leq j \leq m:$

$$MDa[i][j]=min\left\{\begin{matrix}MDa[i-1][j]+dis(A[i-1],A[i])\\MDb[i-1][j]+dis(A[i],B[j])\end{matrix}\right.$$

$for\ 1\leq i\leq n,1< j \leq m:$

$$MDb[i][j]=min\left\{\begin{matrix}MDa[i][j-1]+dis(A[i],B[j])\\MDb[i][j-1]+dis(B[j-1],B[j])\end{matrix}\right.$$

 

这样我们就可以很容易的求出$MDa[n][m]$和$MDb[n][m]$，然后取其中的较小值作为最终的长度。复杂度$O(m*n)$

后续处理

通过上面的算法我们算出了两个序列归并后的路径长度记为$L(A,B)$，同时我们把路径$A$的长度记为$L(A)$，路径$B$的长度记为$L(B)$。当两个路径完全重合的时候，很明显这个值会等于$L(A)\ or\ L(B)$。显然，如果我们想把$L(A,B)$作为路径相异度的量度的话，最好还是让他此时的值等于零。因此我们会对他的值进行一下处理，使他更像一个相似度的量度而不仅仅是一种距离。我们如下定义这个量度$MD(A,B)$：

$$MD(A,B)=\frac{2*L(A,B)}{L(A)+L(B)}-1$$

这样，我们所定义的这个值就满足路径完全相同时，相异度就是０，而且这个值并不会随着路径长度的增加而丧失准确度。

总结

Merge Distance算法所得到的量度对于原路径点与降采样（SubSampling）后的路径点或**超采样(SuperSampling)**后的路径点的相异度评判差别很小（论文中实验为证），这也是相对于传统的DTW，欧氏距离等相似度评判方法表现突出的地方。

参考

Anas Ismail,Antoine Vigneron.A New Trajectory Similarity Measure for GPS Data, (KAUST) Thuwal 23955-6900, Saudi Arabia