Scalable near-repeat and event chain calculations over heterogeneous computer architecture and systems

Figures & data

Table 1. Example of input source data.

x	y	t
12,723,025	3,571,087	38,966
12,725,670	3,572,824	38,635
……	……	……
12,723,571	3,573,746	38,627

Table 2. Example of a 5 × 5 near-repeat output table.

1	11	1	3	3
2	236	248	154	209
2	275	244	183	367
1	255	255	215	340
3	455	440	387	660

Table 3. GPU program code segment for creating the all-event pair table in parallel.

__global__ void crimeCuda(float* xAxis_d, float* yAxis_d, float* time_d, int* label_d, int* timeSlots_d, int* distanceSlots_d, int dataNum, int timeNum, int distanceNum){

int idx = blockIdx.x * blockDim.x + threadIdx.x;

if(idx < dataNum){

for(int i = 0; i < dataNum; i ++){

if(i != idx){

label_d[idx * dataNum + i] =assignLabel(xAxis_d[idx],

yAxis_d[idx], time_d[idx], xAxis_d[i], yAxis_d[i],

time_d[i], timeSlots_d, distanceSlots_d, timeNum,

distanceNum);

}

}

}

}

Table 4. Computational intensity for varying number of chains.

Chain number	Formula	N = 100	N = 30,000
2-event chain	N × (N − 1)/(2 × 1)	4950	449,985,000
3-event chain	N × (N − 1) × (N − 2)/(3 × 2 × 1)	161,700	4.5 × 10^12
4-event chain	N × (N − 1) × (N − 2) × (N − 3)/(4 × 3 × 2 × 1)	3,921,225	3.4 × 10^16
5-event chain	N × (N − 1) × (N − 2) × (N − 3) × (N − 4)/(5 × 4 × 3 × 2 × 1)	75,287,520	2.0 × 10^20

Figure 1. One individual-event pair table for a 20 event use case.

Figure 2. Three-event chains that are associated with the first event.

Figure 3. Three-event chains that are associated with the fourth event.

Figure 4. Regular patterns shown with a higher number of chains.

Table 5. Two-event pair calculation result.

902 [0]	19,118 [5]	10,962 [10]	5764 [15]	10,960 [20]
89,430 [1]	10,616,749 [6]	7,096,991 [11]	4,012,736 [16]	7,903,840 [21]
201,122 [2]	24,758,642 [7]	16,575,721 [12]	9,512,489 [17]	18,520,012 [22]
254,539 [3]	31,528,334 [8]	21,104,195 [13]	12,077,044 [18]	23,365,331 [23]
979,689 [4]	121,121,618 [9]	81,166,971 [14]	46,248,867 [19]	91,089,234 [24]

Table 6. Three- and Four-event chain calculation result.

ID in 5 × 5 table	Pair number in three event chains	Start time	End time	Time used	Unique events in 4 event chain	Estimated calculations
0	162	01:35:22	02:04:01	0:28:39	170	3.36E+07
1	167,352	02:04:38	02:32:20	0:27:42	23,984	1.38E+16
2	335,568	02:32:49	02:59:42	0:26:53	26,645	2.10E+16
3	284,600	03:07:10	03:35:05	0:27:55	27,871	2.51E+16
4	14,643,984	05:05:54	05:35:14	0:29:20	31,576	4.14E+16
5	107,160	05:36:26	06:03:03	0:26:37	4352	1.49E+13
6	1,897,464,639	06:05:08	06:34:26	0:29:18	32,306	4.54E+16
7	4,147,853,641	06:19:54	06:50:30	0:30:36	32,326	4.55E+16
8	3,612,469,509	06:47:06	07:16:08	0:29:02	32,243	4.50E+16
9	183,759,055,736	06:51:10	07:19:35	0:28:25	32,476	4.63E+16
20	6018	08:35:23	09:01:35	0:26:12	1688	6.05E+10
21	316,239,815	08:49:58	09:18:53	0:28:55	32,466	4.63E+16
22	761,491,797	08:50:47	09:18:21	0:27:34	32,404	4.59E+16
23	633,774,016	08:57:52	09:31:16	0:33:24	32,390	4.59E+16
24	35,091,135,040	08:58:56	09:31:01	0:32:05	32,505	4.65E+16

Data availability statement

The data that support the findings of this study are openly available in Github at https://github.com/xinyueye/TBED1402485.