Page 232 - 《软件学报》2020年第10期

3208 Journal of Software 软件学报 Vol.31, No.10, October 2020

的结果集 R={(o 2 ,0.510)}.
Table 2 Running instance of VGRID
表 2 VGRID 算法运行实例
结果集 R 被访问的单元 邻近 8 个单元及其与查询对应的空间文本相似性 栈 nbs 状态
300(0.740),301(0.728),310(0.729),312(0.576), 330(0.485),312(0.576),321(0.707),301(0.728),
{} 303(0.700)
330(0.485),321(0.707),320(0.729),302(0.728) 302(0.728),310(0.729),320(0.729),300(0.740)
312(0.576),321(0.707),301(0.728),302(0.728),
303(0.700),312(0.579),313(0.742),331(0.743),
(o 2,0.510) 330(0.485) 310(0.729),320(0.729),300(0.740),313(0.742),
333(0.760),332(0.743),323(0.742),321(0.707)
323(0.742),331(0.743),332(0.743),333(0.760)

(3) 邻近 8 个单元的计算方法
Morton 码 [23] 是空间网格划分后每一个单元(cell)的唯一标识,与单元的空间坐标可进行相互转换.利用这个
性质,通过二进制位运算很容易获得某单元周围邻近 8 个单元的码值乃至位置坐标.下面首先说明 Morton 码与
空间坐标的相互转换方法,接下来说明如何通过二进制的位运算在 O(1)时间内获得邻近单元的码值.
已知某单元的十进制坐标为(x,y),其 Morton 码的具体计算方法如下.先将单元位置坐标(x,y)的值转化为二
进制形式,令 x=x r−1 ...x 1 x 0 ,y=y r−1 ...y 1 y 0 ,其中,x i ,y i ∈{0,1},r 为线性四分树划分的深度.该单元对应的二进制编码为
n=y r−1 x r−1 ...y 1 x 1 y 0 x 0 .例如,图 3 中单元 303 的坐标为(5,5),将两个坐标转化为二进制,分别是 x=110,y=110,则该单元
对应的编码为 n=110011,转化为四进制后即 Morton 码为 303.
在算法 3 的第 13 行需要查找中心单元邻近的 8 个单元,如图 9 所示.其中,任意单元的 8 个邻近单元的计算
方法如公式(5) [36] .设中心单元的 Morton 码值为 code,则有:
| ) ( n+ Δ∧
m = n ⊕ Δ = (((n t t )) t∧ ) | (((n t t )) t∧ ) (5)
| ) ( n+ Δ∧
n
q q q i q y i x x q x i y y
在公式(5)中,m q 是邻近单元 Morton 码的二进制表示.n q
是中心单元 code 的二进制表示.t x 和 t y 是两个二进制常数:
t x =01...0101 表示“01”重复 r 次,t y =10...1010 表示“10”重复 r
次.Δn i 是基本方向增量之一,即计算中心单元任意方向的单
元码值时坐 标的变化量 ,8 个方位的 基本增量即 Δn 0 =
(−1,−1),Δn 1 =(0,−1),Δn 2 =(1,−1),Δn 3 =(1,0),Δn 4 =(1,1),Δn 5 =(0,1),
Δn 6 =(−1,1),Δn 7 =(−1,0).采用上文单元码值的计算方法,将∆n i
Fig.9 The eight neighbor cells for the cell 303 由坐标值转换为 Morton 码(见表 3 第 2 列).公式(5)采用的
图 9 303 单元的 8 个邻近单元 是位运算:“+”表示相加;“|”表示 OR;“^”表示 AND.设线性四
分树划分深度 r=3,计算中心单元 303(转换成二进制为 110011)的邻近 8 个单元码值的过程见表 3.
Table 3 Increment of direction
表 3 方向增量
Morton
n i ∆n i 公式(4)带入后的 m q
码值
n 0 Δn 0=111111 (((110011|101010)+(111111∧010101))∧010101)|(((110011|010101)+(111111∧101010))∧101010)=110000 300
n 1 Δn 1=101010 (((110011|101010)+(101010∧010101))∧010101)|(((110011|010101)+(101010∧101010))∧101010)=110001 301
n 2 Δn 2=101011 (((110011|101010)+(101011∧010101))∧010101)|(((110011|010101)+(101011∧101010))∧101010)=110100 310
n 3 Δn 3=000001 (((110011|101010)+(000001∧010101))∧010101)|(((110011|010101)+(000001∧101010))∧101010)=110110 312
n 4 Δn 4=000011 (((110011|101010)+(000011∧010101))∧010101)|(((110011|010101)+(000011∧101010))∧101010)=111100 330
n 5 Δn 5=000010 (((110011|101010)+(000010∧010101))∧010101)|(((110011|010101)+(000010∧101010))∧101010)=111001 321
n 6 Δn 6=010111 (((110011|101010)+(010111∧010101))∧010101)|(((110011|010101)+(010111∧101010))∧101010)=111000 320
n 7 Δn 7=010101 (((110011|101010)+(010101∧010101))∧010101)|(((110011|010101)+(010101∧101010))∧101010)=110010 302
5 实 验

5.1 实验设置

实验采用 Foursquare 上真实的签到数据集 [41,42] ,包括纽约(NYC)和洛杉矶(LA)两个城市用户的签到数据.