Huajun He

Huajun He

Ph.D., Southwest Jiaotong University

Posts by Tags

category1

基于键值对数据库的高效轨迹相似查询方案 [ICDE-2022论文]

1 minute read

Published:

相似性搜索已成为许多轨迹数据分析任务的重要组成部分。随着物联网技术的快速发展，使得企业收集轨迹数据的途径变多、速度变快，导致许多轨迹分析任务必须从海量轨迹中寻找相似的轨迹。由于轨迹数据结构复杂，具有不规则的空间形状和连续的时间序列属性，存储和查询海量轨迹数据具有挑战性。西南交通大学博士生、京东实习生何华均为第一作者，郑宇教授和李天瑞教授为通讯作者，重庆大学李瑞远副教授、京东智能城市研究院-时空实验室鲍捷和何天赋，以及西安电子科技大学阮思捷博士共同完成的论文《TraSS: Efficient Trajectory Similarity Search Based on Key-Value Data Stores》提出了一种在key-value数据库中快速查询相似轨迹的高效方案。通常，海量轨迹数据可以通过key-value数据库进行管理。然而，现有的key-value数据库只能使用粗粒度的空间索引来存储轨迹数据，并且没有提供高效的查询处理算法来搜索相似的轨迹。TraSS提出了一种新颖的空间索引 XZ，它利用具有不同大小和不规则形状的索引空间来精细地表示轨迹的空间位置和形状。此外，TraSS设计了一个从 XZ 的多维索引空间到一维连续整数域的编码函数，可方便设计高效的轨迹存储策略和快速的轨迹查询处理算法。进一步地，为了提高相似性搜索的效率，TraSS采用两个步骤来修剪不相似的轨迹：（1）全局修剪。它利用 XZ* 索引来修剪没有相似于查询轨迹的索引空间。TraSS的全局剪枝只会挑选出与查询轨迹具有相似大小和形状的索引空间。与之前最先进的索引相比，TraSS的全局剪枝在查询处理过程中减少了高达 66.4% 的 I/O 开销；(2)局部过滤。它以降低相似度计算复杂度的方式来快速过滤不相似的轨迹。TraSS使用 Douglas-Peucker 算法从轨迹中提取代表性特征来加速局部过滤，极大地降低了查询处理过程中产生的计算量。大量实验和实际案例表明TraSS极大地提高了海量轨迹相似查询效率。

多维反向k近邻查询

2 minute read

Published:

近十年来，空间点数据的反向k最近邻(R$k$NN)查询引起了研究者的广泛关注。给定一个数据点 q，反向k最近邻(R$k$NN)查询查找每一条将q当作它的k个近邻之一的数据点。由于q与这些数据点很接近，所以q对这些点的影响很大。例如，居民有极大的可能会去最近的k个商店购物。因此，在市场调研中，可以通过检索所有将这家商店当作k 个最近邻之一的居民点，来评估一家新开的便利店q潜在的客户。R$k$NN还可在更多的商业选址场景中使用，具有很重要的现实意义和实用价值。在本文中，提供一种设施或服务的对象(如购物市场、加油站)称为设施，使用该设施的对象(如居民、司机)称为用户。在这个上下文中，给定一个查询设施q, 其R$k$NN返回所有将q作为k个最接近的设施之一的用户。本文将基于这种上下文介绍四种R$k$NN算法, 即six regions 、TPL、FINCH、InfZone。

管理海量空间数据的利器-空间填充曲线

less than 1 minute read

Published:

现实世界中存在大量的多维空间数据，如加油站位置、河流走向等。为了高效存储和管理海量的空间数据，很多基于Key-Value存储的空间数据库，如GeoMesa[1]、JUST[2]，使用了空间填充曲线技术。它们将多维空间数据转换到一维空间上，并通过转换后的一维空间索引值存储和查询多维数据。本文详细介绍了几种常用的空间填充曲线(Z曲线、Hilbert曲线、XZ-Ordering)的映射算法。

category2

基于键值对数据库的高效轨迹相似查询方案 [ICDE-2022论文]

1 minute read

Published:

相似性搜索已成为许多轨迹数据分析任务的重要组成部分。随着物联网技术的快速发展，使得企业收集轨迹数据的途径变多、速度变快，导致许多轨迹分析任务必须从海量轨迹中寻找相似的轨迹。由于轨迹数据结构复杂，具有不规则的空间形状和连续的时间序列属性，存储和查询海量轨迹数据具有挑战性。西南交通大学博士生、京东实习生何华均为第一作者，郑宇教授和李天瑞教授为通讯作者，重庆大学李瑞远副教授、京东智能城市研究院-时空实验室鲍捷和何天赋，以及西安电子科技大学阮思捷博士共同完成的论文《TraSS: Efficient Trajectory Similarity Search Based on Key-Value Data Stores》提出了一种在key-value数据库中快速查询相似轨迹的高效方案。通常，海量轨迹数据可以通过key-value数据库进行管理。然而，现有的key-value数据库只能使用粗粒度的空间索引来存储轨迹数据，并且没有提供高效的查询处理算法来搜索相似的轨迹。TraSS提出了一种新颖的空间索引 XZ，它利用具有不同大小和不规则形状的索引空间来精细地表示轨迹的空间位置和形状。此外，TraSS设计了一个从 XZ 的多维索引空间到一维连续整数域的编码函数，可方便设计高效的轨迹存储策略和快速的轨迹查询处理算法。进一步地，为了提高相似性搜索的效率，TraSS采用两个步骤来修剪不相似的轨迹：（1）全局修剪。它利用 XZ* 索引来修剪没有相似于查询轨迹的索引空间。TraSS的全局剪枝只会挑选出与查询轨迹具有相似大小和形状的索引空间。与之前最先进的索引相比，TraSS的全局剪枝在查询处理过程中减少了高达 66.4% 的 I/O 开销；(2)局部过滤。它以降低相似度计算复杂度的方式来快速过滤不相似的轨迹。TraSS使用 Douglas-Peucker 算法从轨迹中提取代表性特征来加速局部过滤，极大地降低了查询处理过程中产生的计算量。大量实验和实际案例表明TraSS极大地提高了海量轨迹相似查询效率。

多维反向k近邻查询

2 minute read

Published:

近十年来，空间点数据的反向k最近邻(R$k$NN)查询引起了研究者的广泛关注。给定一个数据点 q，反向k最近邻(R$k$NN)查询查找每一条将q当作它的k个近邻之一的数据点。由于q与这些数据点很接近，所以q对这些点的影响很大。例如，居民有极大的可能会去最近的k个商店购物。因此，在市场调研中，可以通过检索所有将这家商店当作k 个最近邻之一的居民点，来评估一家新开的便利店q潜在的客户。R$k$NN还可在更多的商业选址场景中使用，具有很重要的现实意义和实用价值。在本文中，提供一种设施或服务的对象(如购物市场、加油站)称为设施，使用该设施的对象(如居民、司机)称为用户。在这个上下文中，给定一个查询设施q, 其R$k$NN返回所有将q作为k个最接近的设施之一的用户。本文将基于这种上下文介绍四种R$k$NN算法, 即six regions 、TPL、FINCH、InfZone。

管理海量空间数据的利器-空间填充曲线

less than 1 minute read

Published:

现实世界中存在大量的多维空间数据，如加油站位置、河流走向等。为了高效存储和管理海量的空间数据，很多基于Key-Value存储的空间数据库，如GeoMesa[1]、JUST[2]，使用了空间填充曲线技术。它们将多维空间数据转换到一维空间上，并通过转换后的一维空间索引值存储和查询多维数据。本文详细介绍了几种常用的空间填充曲线(Z曲线、Hilbert曲线、XZ-Ordering)的映射算法。

cool posts

基于键值对数据库的高效轨迹相似查询方案 [ICDE-2022论文]

1 minute read

Published:

相似性搜索已成为许多轨迹数据分析任务的重要组成部分。随着物联网技术的快速发展，使得企业收集轨迹数据的途径变多、速度变快，导致许多轨迹分析任务必须从海量轨迹中寻找相似的轨迹。由于轨迹数据结构复杂，具有不规则的空间形状和连续的时间序列属性，存储和查询海量轨迹数据具有挑战性。西南交通大学博士生、京东实习生何华均为第一作者，郑宇教授和李天瑞教授为通讯作者，重庆大学李瑞远副教授、京东智能城市研究院-时空实验室鲍捷和何天赋，以及西安电子科技大学阮思捷博士共同完成的论文《TraSS: Efficient Trajectory Similarity Search Based on Key-Value Data Stores》提出了一种在key-value数据库中快速查询相似轨迹的高效方案。通常，海量轨迹数据可以通过key-value数据库进行管理。然而，现有的key-value数据库只能使用粗粒度的空间索引来存储轨迹数据，并且没有提供高效的查询处理算法来搜索相似的轨迹。TraSS提出了一种新颖的空间索引 XZ，它利用具有不同大小和不规则形状的索引空间来精细地表示轨迹的空间位置和形状。此外，TraSS设计了一个从 XZ 的多维索引空间到一维连续整数域的编码函数，可方便设计高效的轨迹存储策略和快速的轨迹查询处理算法。进一步地，为了提高相似性搜索的效率，TraSS采用两个步骤来修剪不相似的轨迹：（1）全局修剪。它利用 XZ* 索引来修剪没有相似于查询轨迹的索引空间。TraSS的全局剪枝只会挑选出与查询轨迹具有相似大小和形状的索引空间。与之前最先进的索引相比，TraSS的全局剪枝在查询处理过程中减少了高达 66.4% 的 I/O 开销；(2)局部过滤。它以降低相似度计算复杂度的方式来快速过滤不相似的轨迹。TraSS使用 Douglas-Peucker 算法从轨迹中提取代表性特征来加速局部过滤，极大地降低了查询处理过程中产生的计算量。大量实验和实际案例表明TraSS极大地提高了海量轨迹相似查询效率。

多维反向k近邻查询

2 minute read

Published:

近十年来，空间点数据的反向k最近邻(R$k$NN)查询引起了研究者的广泛关注。给定一个数据点 q，反向k最近邻(R$k$NN)查询查找每一条将q当作它的k个近邻之一的数据点。由于q与这些数据点很接近，所以q对这些点的影响很大。例如，居民有极大的可能会去最近的k个商店购物。因此，在市场调研中，可以通过检索所有将这家商店当作k 个最近邻之一的居民点，来评估一家新开的便利店q潜在的客户。R$k$NN还可在更多的商业选址场景中使用，具有很重要的现实意义和实用价值。在本文中，提供一种设施或服务的对象(如购物市场、加油站)称为设施，使用该设施的对象(如居民、司机)称为用户。在这个上下文中，给定一个查询设施q, 其R$k$NN返回所有将q作为k个最接近的设施之一的用户。本文将基于这种上下文介绍四种R$k$NN算法, 即six regions 、TPL、FINCH、InfZone。

管理海量空间数据的利器-空间填充曲线

less than 1 minute read

Published:

现实世界中存在大量的多维空间数据，如加油站位置、河流走向等。为了高效存储和管理海量的空间数据，很多基于Key-Value存储的空间数据库，如GeoMesa[1]、JUST[2]，使用了空间填充曲线技术。它们将多维空间数据转换到一维空间上，并通过转换后的一维空间索引值存储和查询多维数据。本文详细介绍了几种常用的空间填充曲线(Z曲线、Hilbert曲线、XZ-Ordering)的映射算法。