# Prefetching Scheme for Massive Spatiotemporal Data in a Smart City

Authors: Lian Xiong; Zhengquan Xu; Hao Wang; Shan Jia; Li Zhu
Journal: International Journal of Distributed Sensor Networks
 (2016)

---

## Abstract

Employing user access patterns to develop a prefetching scheme can effectively improve system I/O performance and reduce user access latency. For massive spatiotemporal data, traditional pattern mining methods fail to directly reflect the spatiotemporal correlation and transition rules of user access, resulting in poor prefetching performance. This paper proposed a prefetching scheme based on spatial-temporal attribute prediction, named STAP. It maps the history of user access requests to the spatiotemporal attribute domain by analyzing the characteristics of spatiotemporal data in a smart city. According to the spatial locality and time stationarity of user access, correlation analysis is performed and variation rules are identified for the history of user access requests. Further, the STAP scheme mines the user access patterns and constructs a predictive function to predict the user’s next access request. Experimental results show that the prefetching scheme is simple yet effective; it achieves a prediction accuracy of 84.3% for access requests and reduces the average data access response time by 44.71% compared with the nonprefetching scheme.


---

## Body

## 1. Introduction

The development of smart cities based on cloud computing and the Internet of Things has generated massive spatiotemporal data, including meteorological data, hydrological data, natural disaster data, and remote-sensing images, with three basic attributes, namely, location, time, and type. Such data are characterized by wide variety, large quantity, high redundancy, and dynamic growth over time. A smart city can quickly and conveniently provide users with rich predefined applications through a network platform based on the users’ demands for spatiotemporal data services such as data visualization, spatiotemporal correlation analysis, temporal emergency aid, and massive information retrieval.Low latency, high concurrency, and high aggregate bandwidth are the three important criteria for measuring the quality of spatiotemporal data services in a smart city. Under the same bandwidth and computing power, the key factor affecting the quality of a spatiotemporal data service is the system delay in the network environment. Prefetching schemes have been widely used because they can effectively improve the data transfer rate and reduce the user access latency [1]. Therefore, it is important to develop an efficient prefetching scheme for improving the quality of spatiotemporal data services in a smart city.Compared with nonspatiotemporal data, spatiotemporal data not only have three basic spatiotemporal attributes but also have obvious spatiotemporal correlation of user access; moreover, the corresponding prefetching schemes are different. Based on the different types of data, data prefetching schemes can be divided into two categories in the network environment.(
1) Nonspatiotemporal Data Prefetching. Nonspatiotemporal data prefetching mainly concerns web prefetching and personalized recommendations. In general, user access information is obtained by clustering or correlation analysis of webpages or users in order to mine user access patterns and develop a prefetching scheme. Pallis et al. [2] employed the association rule to filter webpages visited by users in order to perform webpage clustering; then, they used the clustering result sets to develop a prefetching scheme for overcoming the problem of web access latency. Further, Wan et al. [3] used clustering to develop a method based on random indexing with various weight functions in order to track user access and cluster users with similar activity patterns. Khosravi and Tarokh [4] adopted a naive Bayesian approach for dynamic mining of user access patterns in order to predict the pages accessed by users. Bamshad et al. [5] developed a personalized webpage recommendation system by using the a priori algorithm to identify pagesets frequently accessed by users; then, they matched the users’ currently accessed pages with the frequently accessed pagesets. Matthews et al. [6] proposed a genetic algorithm based on association rules and discovered extra rules that are complementary to existing algorithms, which can facilitate the development of more effective prefetching schemes. Similar studies have been described in the literature [7–13].(
2) Spatiotemporal Prefetching. Spatiotemporal data prefetching mainly concerns WebGIS. The corresponding prefetching schemes use not only the characteristics of the data but also the spatiotemporal correlation of user access. Typically, the characteristics of the data are used to mine user access patterns and develop a prefetching scheme by spatiotemporal correlation analysis, transition probability calculation, access frequency ranking, and other methods related to user access requests or data. In order to overcome the problem of a long delay when users browse large objects in WebGIS, Park and Kim [14] used the spatial clustering characteristic of the Hilbert curve. They divided the entire geographic space using Hilbert curves and gave them appropriate values; then, they proposed a prefetching method based on the spatial locality of user access. Dong et al. [15] exploited the spatial locality of user access and proposed two prefetching methods. The first method computes transition probabilities between tiles and prefetches the most probable tile; the second method uses a “Neighbor Selection Markov Chain” to compute the objects to be prefetched based on the data of the k tiles previously requested. Considering the previous action of a given user, Yeşilmurat and Işler [16] proposed a heuristic prefetching algorithm that analyzes and ranks the previous moves of a user to predict the user’s next move; then, it identifies the locations of candidate tiles to be prefetched. Considering both long-term and short-term popularity features for tile access in a geographic space, Li et al. [17] presented a Markov prefetching model in a cluster-based caching system based on the Zipf distribution and verified that the method has a high prefetch hit rate and a short average response time.From existing studies, it can be seen that, in the network environment, a typical data prefetching scheme is based on current/historical user access information. It analyzes and processes the information at the level of access requests or data by using user access continuity, spatial locality, popularity, association rules between objects, and other methods in order to mine the user access patterns. Then, it predicts user access requests according to these patterns in order to achieve data prefetching.However, we note that user access to spatiotemporal data usually has obvious spatiotemporal features in a smart city. The general approach mines user access patterns at the level of access requests or data, the results can only reflect this feature indirectly, and they are not useful for developing a high-efficiency prefetching scheme for massive spatiotemporal data. But if we analyze and process user access information at the level of spatiotemporal attributes, then the hidden spatiotemporal correlation and transition rules can be found, and we can develop a more targeted prefetching scheme. Therefore, how to effectively mine the spatiotemporal features and patterns from the user access information is the focus of this paper.In this paper, we propose a prefetching scheme, STAP, for massive spatiotemporal data in a smart city. The proposed method analyzes the characteristics of spatiotemporal data and the spatiotemporal correlation of user access, parameterizes the history of user access requests, and extracts the spatiotemporal attributes. Then, it uses regional meshing, association rules, and the autoregressive integrated moving average (ARIMA) model in the spatiotemporal attribute domain to perform correlation analysis and identify transition rules, mines user access patterns, and constructs a predictive function to predict the user’s next access request, in order to achieve spatiotemporal data prefetching.The remainder of this paper is organized as follows. Section2 introduces the motivation and principle of our prefetching scheme. Section 3 describes the implementation of our prefetching scheme, which mainly involves two steps. The first step shows how to (i) mine the user access patterns from the history of user access requests and (ii) construct the predictive function for predicting requests. The second part explains how to (i) predict the user’s next access request according to the current one by using the abovementioned predictive function and (ii) prefetch the corresponding data. Section 4 presents and discusses the performance evaluation results of our prefetching scheme. Finally, Section 5 briefly summarizes our findings and concludes the paper.


## 2. Principle of Prefetching Scheme

### 2.1. Motivation

Typical prefetching schemes involve two steps. The first step is to mine the user access patterns and construct the predictive function; the second step is to predict access requests and prefetch the data. The first step is usually based on historical user access information as well as the characteristics of the data. It uses clustering, association rules, Markov models, and other methods to mine associate items accessed by users. Then, it merges them to form associate itemsets or uses mathematical functions to describe the correlation between the associate items. Thus, the corresponding request predictive function is constructed. The second step is based on the current user access request, the predictive function is used to predict the next access request of the user, and then the corresponding data is loaded into the cache.For instance, suppose thath
i, 1
≤
i
≤
n, is a user access request; then, the history of user access requests can be expressed as the sequence H
=
h
1
,
h
2
,
h
3
,
…
,
h
n. The first step is to mine the access pattern, that is, to mine associate items h
i
→
h
j from H and construct the request predictive function according to the associate itemsets. The second step involves access request prediction and data prefetching. Take the current user access request h
i
,
h
j as the input for the prediction function. Then, scan the associate itemsets to find the matching associate items h
i
,
h
j
→
h
k; the output of the function h
k is the predicted access request. Finally, prefetch the corresponding data of request h
k to the cache.It can be seen that the key aspect of the prefetching scheme is to mine user access patterns and construct the request predictive function. However, unlike ordinary user access features in the network environment, the users obtain spatiotemporal data services based on predefined applications in a smart city, which have obvious spatiotemporal correlation. For example, if a user checks the weather conditions by predefined applications, the access data are current time and location related meteorological data; when searching for the nearby living facilities, the access data, such as restaurants and parking lots, are closely related to the user’s current location. Therefore, if we treat the access request as a whole for direct mining as in the case of traditional mining patterns, the spatiotemporal correlation of user access will not be reflected directly, and the corresponding prediction function will not predict user access requests accurately.In order to overcome the inherent drawback of mining user access patterns directly at the level of access requests, we start with the characteristics of spatiotemporal data and the spatiotemporal correlation of user access. Then, we mine the user access patterns at the level of spatiotemporal attributes and construct the access request predictive function.


### 2.2. Principle

Suppose that the history of user access requests in a smart city can be expressed as the sequenceA
=
a
1
,
a
2
,
a
3
,
…
,
a
n, where each a
i, 1
≤
i
≤
n, contains the following information: location attribute p, type attribute s, time attribute t, user IP, and session time. In order to analyze and process the access sequences at the level of the spatiotemporal domain, we parameterize the information and extract the spatiotemporal attributes to form spatiotemporal attribute sequences:(1)
A
=
p
1
,
s
1
,
t
1
,
p
2
,
s
2
,
t
2
,
…
,
p
n
,
s
n
,
t
n
=
P
n
,
S
n
,
T
n
,where a
i
=
p
i
,
s
i
,
t
i represents a parameterized request with the extraction results of the spatiotemporal attributes. Specifically, P
n
=
p
1
,
p
2
,
p
3
,
…
,
p
n represents the sequence of location attributes, S
n
=
s
1
,
s
2
,
s
3
,
…
,
s
n represents the sequence of type attributes, and T
n
=
t
1
,
t
2
,
t
3
,
…
,
t
n represents the sequence of time attributes.Because the spatiotemporal attribute sequencesP
n
,
S
n
,
T
n contain three types of spatiotemporal attributes, it is extremely difficult to find the hidden spatiotemporal correlations and variation rules. However, we observe that, in a smart city, when most users request access to spatiotemporal data, the spatiotemporal attributes of the request have strong self-correlation but weak cross-correlation. That is to say, any two consecutive access requests, a
i
,
a
i
+
1, have weak correlation between the location attribute p
i and the type attribute s
i
+
1 but very strong correlation between p
i and p
i
+
1. For example, when a user checks the current temperature of regional A, there is a huge possibility that he will further query the wind speed, PM2.5 of region A, rather than the water quality of other regions.Therefore, to simplify access pattern mining, we process spatiotemporal attribute sequencesP
n
,
S
n
,
T
n based on the self-correlation and cross-correlation of the spatiotemporal attributes of the access requests, in order to construct the access request predictive function. The specific steps are as follows:(1)
For access requests with self-correlation of spatiotemporal attributes, we analyze the self-correlation of the spatiotemporal attribute sequences to mine associate itemsp
i
→
p
j, s
i
→
s
j, and t
i
→
t
j. Then, we construct the independent attribute prediction function P
r
e
′
p
,
s
,
t
=
Pre
p
,
P
r
e
s
,
P
r
e
t, where Pre
p represents the location attribute predictive function, Pre
s represents the type attribute predictive function, and Pre
t represents the time attribute predictive function.
(2)
For access requests with cross-correlation of spatiotemporal attributes, we carry out cross-correlation analysis of the spatiotemporal attribute sequences, and we mine associate itemsp
i
,
s
i
,
t
i
→
p
j
,
s
j
,
t
j. Then, we construct the conjoint attribute prediction function Pre
′
′
p
,
s
,
t.


## 2.1. Motivation

Typical prefetching schemes involve two steps. The first step is to mine the user access patterns and construct the predictive function; the second step is to predict access requests and prefetch the data. The first step is usually based on historical user access information as well as the characteristics of the data. It uses clustering, association rules, Markov models, and other methods to mine associate items accessed by users. Then, it merges them to form associate itemsets or uses mathematical functions to describe the correlation between the associate items. Thus, the corresponding request predictive function is constructed. The second step is based on the current user access request, the predictive function is used to predict the next access request of the user, and then the corresponding data is loaded into the cache.For instance, suppose thath
i, 1
≤
i
≤
n, is a user access request; then, the history of user access requests can be expressed as the sequence H
=
h
1
,
h
2
,
h
3
,
…
,
h
n. The first step is to mine the access pattern, that is, to mine associate items h
i
→
h
j from H and construct the request predictive function according to the associate itemsets. The second step involves access request prediction and data prefetching. Take the current user access request h
i
,
h
j as the input for the prediction function. Then, scan the associate itemsets to find the matching associate items h
i
,
h
j
→
h
k; the output of the function h
k is the predicted access request. Finally, prefetch the corresponding data of request h
k to the cache.It can be seen that the key aspect of the prefetching scheme is to mine user access patterns and construct the request predictive function. However, unlike ordinary user access features in the network environment, the users obtain spatiotemporal data services based on predefined applications in a smart city, which have obvious spatiotemporal correlation. For example, if a user checks the weather conditions by predefined applications, the access data are current time and location related meteorological data; when searching for the nearby living facilities, the access data, such as restaurants and parking lots, are closely related to the user’s current location. Therefore, if we treat the access request as a whole for direct mining as in the case of traditional mining patterns, the spatiotemporal correlation of user access will not be reflected directly, and the corresponding prediction function will not predict user access requests accurately.In order to overcome the inherent drawback of mining user access patterns directly at the level of access requests, we start with the characteristics of spatiotemporal data and the spatiotemporal correlation of user access. Then, we mine the user access patterns at the level of spatiotemporal attributes and construct the access request predictive function.


## 2.2. Principle

Suppose that the history of user access requests in a smart city can be expressed as the sequenceA
=
a
1
,
a
2
,
a
3
,
…
,
a
n, where each a
i, 1
≤
i
≤
n, contains the following information: location attribute p, type attribute s, time attribute t, user IP, and session time. In order to analyze and process the access sequences at the level of the spatiotemporal domain, we parameterize the information and extract the spatiotemporal attributes to form spatiotemporal attribute sequences:(1)
A
=
p
1
,
s
1
,
t
1
,
p
2
,
s
2
,
t
2
,
…
,
p
n
,
s
n
,
t
n
=
P
n
,
S
n
,
T
n
,where a
i
=
p
i
,
s
i
,
t
i represents a parameterized request with the extraction results of the spatiotemporal attributes. Specifically, P
n
=
p
1
,
p
2
,
p
3
,
…
,
p
n represents the sequence of location attributes, S
n
=
s
1
,
s
2
,
s
3
,
…
,
s
n represents the sequence of type attributes, and T
n
=
t
1
,
t
2
,
t
3
,
…
,
t
n represents the sequence of time attributes.Because the spatiotemporal attribute sequencesP
n
,
S
n
,
T
n contain three types of spatiotemporal attributes, it is extremely difficult to find the hidden spatiotemporal correlations and variation rules. However, we observe that, in a smart city, when most users request access to spatiotemporal data, the spatiotemporal attributes of the request have strong self-correlation but weak cross-correlation. That is to say, any two consecutive access requests, a
i
,
a
i
+
1, have weak correlation between the location attribute p
i and the type attribute s
i
+
1 but very strong correlation between p
i and p
i
+
1. For example, when a user checks the current temperature of regional A, there is a huge possibility that he will further query the wind speed, PM2.5 of region A, rather than the water quality of other regions.Therefore, to simplify access pattern mining, we process spatiotemporal attribute sequencesP
n
,
S
n
,
T
n based on the self-correlation and cross-correlation of the spatiotemporal attributes of the access requests, in order to construct the access request predictive function. The specific steps are as follows:(1)
For access requests with self-correlation of spatiotemporal attributes, we analyze the self-correlation of the spatiotemporal attribute sequences to mine associate itemsp
i
→
p
j, s
i
→
s
j, and t
i
→
t
j. Then, we construct the independent attribute prediction function P
r
e
′
p
,
s
,
t
=
Pre
p
,
P
r
e
s
,
P
r
e
t, where Pre
p represents the location attribute predictive function, Pre
s represents the type attribute predictive function, and Pre
t represents the time attribute predictive function.
(2)
For access requests with cross-correlation of spatiotemporal attributes, we carry out cross-correlation analysis of the spatiotemporal attribute sequences, and we mine associate itemsp
i
,
s
i
,
t
i
→
p
j
,
s
j
,
t
j. Then, we construct the conjoint attribute prediction function Pre
′
′
p
,
s
,
t.


## 3. Implementation

The method is implemented in two steps. The first step is the offline mining of user access patterns to construct the predictive function, and the second step is the online access request prediction and data prefetching.


### 3.1. Construction of Predictive Function

The predictive function consists of the independent attribute prediction functionPre
′
p
,
s
,
t
=
Pre
p
,
P
r
e
s
,
P
r
e
t and the conjoint attribute prediction function Pre
′
′
p
,
s
,
t.


#### 3.1.1. Construction of Independent Attribute Predictive Function

(
1) Construction of Location Attribute Predictive Function. The key aspect of the location attribute predictive function Pre
p is the correlation of access requests in the spatial domain. Therefore, we can use the association rule algorithm [18] to mine associate items p
i
→
p
j from the sequence of location attributes P
n
=
p
1
,
p
2
,
p
3
,
…
,
p
n and construct the location attribute predictive function according to the associate rulesets.(a) Regional Meshing. The location attribute of spatiotemporal data represents the geographical location of a data source in a smart city, usually expressed by latitude and longitude coordinates p
=
x
,
y. However, solving the association rules of the location attribute coordinate points directly requires numerous calculations. Moreover, updating, modification, addition, or deletion operations on location attributes will require recalculation for the entire area. Therefore, we exploit regional meshing for the entire area, which allows for both the early solution of rules and late update of associate rules in the cell area, thereby providing partial and incremental solution of association rules and reducing the computation considerably.Suppose that the geographic area is a two-dimensional Euclidean rectangular space0
,
X
0
,
Y in a smart city. We divide it into r
o
w
×
c
o
l rectangular cells with coding, where the code of the area covered by the ith row jth column is g
i
j
=
j
+
c
o
l
·
i
-
1. Then, for any location attribute coordinate point p
k
=
x
k
,
y
k in the geographic area, we assume that it belongs to the cell g
i
j if it satisfies the following equation: (2)
i
-
1
X
row
≤
x
k
≤
i
X
row
,
1
≤
i
≤
row
j
-
1
Y
col
≤
y
k
≤
j
Y
col
,
1
≤
j
≤
col
.Figure1(a) shows the geographic rectangular area divided into 4 × 5 cells and the meshing cell coding. Figure 1(b) shows all the neighbor cells of the cell g
i
j.Figure 1
Regional meshing and coding: (a) meshing cell coding; (b) neighbor cells ofg
i
j.
(a)
(b)(b) Construction of Predictive Function. Through regional meshing, we can use an association rule algorithm to mine the associate items of each cell from the sequence of location attributes P
n
=
p
1
,
p
2
,
p
3
,
…
,
p
n and construct the location attribute predictive function Pre
p according to the associate rulesets. The specific steps are as follows:(1)
Calculate the location coordinate setsp
g
i
j
=
p
g
1
,
p
g
2
,
…
,
p
g
m
,
…
,
p
g
n contained in the cell g
i
j and its neighbor cells, as shown in Figure 1(b).
(2)
Count the number of times every coordinate pointp
g
i
,
p
g
i
∈
p
g
i
j, appears in the sequence of location attributes, that is,support, and compare it with the predefinedsupport threshold
δ
p to find frequent 1-itemsets. By looping through the location attribute sequence via the connection and cut between the frequent itemsets, we can find frequent 2-itemsets, frequent 3-itemsets, and so on until frequent m-, 2
≤
m
≤
n, itemsets.
(3)
Calculate theconfidence of each frequent m-itemsets and its subset frequentm-1-itemsets. Generate association rules p
g
i
,
p
g
i
+
1
,
…
,
p
g
i
+
m
-
1
→
p
g
i
+
m
,
ϕ
g
i
g
i
+
m on those associate itemsets whoseconfidence values are greater than theconfidence threshold
ϕ
p. Then, form the association rulesets R
g
i
j
,
ϕ
i
j
=
⋃
m
p
g
i
,
p
g
i
+
1
,
…
,
p
g
i
+
m
-
1
→
p
g
i
+
m
,
ϕ
g
i
g
i
+
m of the cell g
i
j.
(4)
Loop through each cell in the geographical area to calculate the location attribute association rulesets and merge them to form the associate rulesetsR
p
i
j
,
ϕ
i
j
=
⋃
i
,
j
R
g
i
j
,
ϕ
i
j of the entire geographic area. Then, construct the location attribute predictive function,(3)
Pre
p
=
Match
p
,
R
p
i
j
,
ϕ
i
j
,
whereM
a
t
c
h
· is a rule matching function, whose output is an associate rule matching successfully with location attribute p; the specific methods are as in Section 3.2.1.(
2) Construction of Type Attribute Predictive Function. The key aspect of the type attribute predictive function Pre
s is the correlation of access requests in the type domain. Therefore, we can use the association rule algorithm to mine associate items s
i
→
s
j from the sequence of type attributes S
n
=
s
1
,
s
2
,
s
3
,
…
,
s
n and construct the type attribute predictive function according to the associate rulesets. The specific steps are as follows:(1)
Count the number of times everys
i
,
s
i
∈
S, appears in the sequence of type attributes, that is,support, and compare it with the predefinedsupport threshold
δ
s to find frequent 1-itemsets. By looping through the type attribute sequences via the connection and cut between the frequent itemsets, we can find frequent 2-itemsets, frequent 3-itemsets, and so on until frequentm-, 2
≤
m
≤
n, itemsets.
(2)
Calculate theconfidenceof each frequent m-itemsets and its subset frequentm-1-itemsets. Generate association rules s
i
,
s
i
+
1
,
…
,
s
i
+
m
-
1
→
s
i
+
m
,
ϕ
i
,
i
+
m on those associate itemsets whoseconfidence values are greater than theconfidence threshold
ϕ
s, and form the association rulesets R
s
i
j
,
ϕ
i
j
=
⋃
m
s
i
,
s
i
+
1
,
…
,
s
i
+
m
-
1
→
s
i
+
m
,
ϕ
i
,
i
+
m. Then, construct the type attribute predictive function(4)
Pre
s
=
Match
s
,
R
s
i
j
,
ϕ
i
j
.(3
) Construction of Time Attribute Predictive Function. The key aspect of the time attribute predictive function Pre
t is the correlation of access requests in the time domain. Therefore, we can analyze the sequence of time attributes T
n
=
t
1
,
t
2
,
t
3
,
…
,
t
n, to develop a model to describe this underlying correlation.The time attribute sequence of user access requests is a typical nonstationary sequence influenced by a predefined application, which has obvious trends in a local range. ARIMA is an important and widely used short-term time series prediction model. It can predict future values according to the current and historical values of the sequence, but it requires the sequence to be stationary [19–23]. To this end, we can piecewise represent the time attribute sequence and perform difference processing to achieve local stationarity. Then, we build the ARIMA model and construct the time attribute predictive function.(a) Piecewise Representation of Time Attribute Sequence. We use extreme point detection based on the slope change and piecewise representation of the time attribute sequence according to local extreme values in the sequence (the beginning and end value of each curve). The method calculates the slope difference t
i
-
t
i
-
1
-
t
i
+
1
-
t
i
/
Δ
T of the line segment formed by sequence value t
i, 1
<
i
<
n, and its neighbor points t
i
-
1, t
i
+
1, where Δ
T is the time interval of the access request. Then, we compare the slope difference with a predefined threshold. If it is greater than or equal to the predefined threshold, we assume that t
i is a local extremum. Finally, by using local extrema, we can piecewise represent the time attribute sequence as follows:(5)
T
=
t
1
L
,
t
1
R
,
t
2
L
,
t
2
R
,
…
,
t
k
L
,
t
k
R
,where t
i
L is the starting value of i
,
i
∈
k, segment, t
i
R is the end value of i
,
i
∈
k, piecewise, and k is the number of piecewise segments.(b) Construction of Predictive Function. With the abovementioned piecewise representation and difference processing, we can realize local stationarity of the time attribute sequence and build ARIMA to construct the time attribute predictive function Pre
t. By introducing the k-step lag operator B
k
t
h
n
=
t
h
n
-
k and d-order difference w
n
=
Δ
d
t
h
n
=
1
-
B
d
t
h
n, d
=
0,1
,
2, the standard A
R
I
M
A
p
,
d
,
q model can be expressed as follows: (6)
w
n
=
φ
1
w
n
-
1
+
φ
2
w
n
-
2
+
⋯
+
φ
p
w
n
-
p
+
δ
+
u
t
+
θ
1
u
t
-
1
+
θ
2
u
t
-
2
+
⋯
+
θ
q
u
t
-
q
,where w
n
=
Δ
d
t
n
=
1
-
B
d
t
n is the difference order, φ
1
,
φ
2
,
…
,
φ
p are the autoregressive parameters, θ
1
,
θ
2
,
…
,
θ
q are the moving average parameters, δ is a constant that indicates that the sequence is nonzero mean, and u
t is white noise sequence.Suppose that the right-and-left local extreme value ofj, 1
<
j
<
k, piecewise is t
j
L
=
t
m, t
j
R
=
t
n. Then, according to formula (5), we can piecewise represent it as t
j
L
,
t
j
R
=
t
m
,
t
m
+
1
,
…
,
t
n, and, through d-order difference processing, it can be stationary. Judging from the fact that the user access is restricted by the predefined application, the change trend of the time attribute sequence can be only linear and regular, which means that it remains unchanged in terms of cycle and step size, so the parameters are p
=
1, φ
1
=
1. At the same time, the time attribute sequence of access request is not affected by external random interference, so the parameters are u
t
=
0, q
=
0.Finally, we can buildA
R
I
M
A
1
,
d
,
0 as w
n
=
w
n
-
1. Combined with the lag operator B
k
t
h
n
=
t
h
n
-
k and d-order difference, the time attribute predictive function Pre
(
t
) can be expressed as follows:(7)
Pre
t
n
=
t
n
-
1
,
d
=
0
2
t
n
-
1
-
t
n
-
2
,
d
=
1
3
t
n
-
1
-
3
t
n
-
2
+
t
n
-
3
,
d
=
2
.


#### 3.1.2. Construction of Conjoint Attribute Predictive Function

Because the access requests with cross-correlation of spatiotemporal attributes account for a very small proportion of the total number of requests, it is difficult to jointly analyze the attributes. Therefore, we analyze only the access requests that have special cross-correlation of spatiotemporal attributes, that is, if the sequence of location attributesP
l
=
p
i
,
p
i
+
1
,
…
,
p
i
+
l and the sequence of type attributes S
l
=
s
i
+
1
,
s
i
+
2
,
…
,
s
i
+
l remain unchanged and the length reaches the minimum threshold l
=
3, as expressed by the following equation:(8)
p
i
+
1
=
p
i
+
2
=
⋯
=
p
i
+
l
,
s
i
+
1
=
s
i
+
2
=
⋯
=
s
i
+
l
,
l
≥
3
.Then, we assume that the location attribute and the type attribute remain unchanged in the next access request, and the time attribute can be predicted byPre
(
t
). Finally, the conjoint attribute predictive function Pre
′
′
p
,
s
,
t can be constructed as(9)
Pre
′
′
p
n
,
s
n
,
t
n
=
p
n
-
1
,
s
n
-
1
,
t
n
-
1
,
d
=
0
p
n
-
1
,
s
n
-
1
,
2
t
n
-
1
-
t
n
-
2
,
d
=
1
p
n
-
1
,
s
n
-
1
,
3
t
n
-
1
-
3
t
n
-
2
+
t
n
-
3
,
d
=
2
.


### 3.2. Prediction Method for Access Requests

The purpose of this section is to show how to use the predictive function to predict the user’s next access request based on the current one.Suppose that the current user access request can be expressed as the sequenceB
=
b
1
,
b
2
,
b
3
,
…
,
b
m, and spatiotemporal attributes sequences are B
=
p
1
,
s
1
,
t
1
,
p
2
,
s
2
,
t
2
,
…
,
p
m
,
s
m
,
t
m
=
P
m
,
S
m
,
T
m, where each b
i
=
p
i
,
s
i
,
t
i, b
i
∈
B, represents one user access request. First, we parameterize it and extract the spatiotemporal attributes to form the spatiotemporal attribute sequence. Then, according to the access request predictive functions Pre
′
p
,
s
,
t and Pre
′
′
p
,
s
,
t, we take the spatiotemporal attribute sequence as the input, and the output b
^
m
+
1
=
p
^
m
+
1
,
s
^
m
+
1
,
t
^
m
+
1 is predicted as the access request.We define a sliding and adaptive observation window with initial sizew, and we take the spatiotemporal attribute sequence {
P
W
,
S
W
,
T
W
}, which falls into the observation window, as the input of the prediction function. Then, we judge whether {
P
W
,
S
W
,
T
W
} can satisfy formula (8). If it satisfies (8), we use the conjoint predictive function; otherwise, we use the independent attribute predictive function. As a result, p
^
m
+
1, s
^
m
+
1, and t
^
m
+
1 can be predicted. Here,(10)
P
W
=
p
m
-
w
+
1
,
p
m
-
w
+
2
,
…
,
p
m
S
W
=
s
m
-
w
+
1
,
s
m
-
w
+
2
,
…
,
s
m
T
W
=
t
m
-
w
+
1
,
t
m
-
w
+
2
,
…
,
t
m
.


#### 3.2.1. Independent Attribute Predictive Function

For the access requests that dissatisfy formula (8), we predict the spatiotemporal attribute according to independent attribute prediction Pre
′
p
,
s
,
t
=
Pre
p
,
P
r
e
s
,
P
r
e
t, and then we form the predictive access request b
^
m
+
1
=
p
^
m
+
1
,
s
^
m
+
1
,
t
^
m
+
1.(
1) Location Attribute Prediction. Because regional meshing is used for the entire geographic area, before prediction, we need to judge whether the coordinate points belong to the same cell or neighbor cells according to formula (2). If the points belong to the same cell, we trigger the prediction; otherwise, we forgo prediction. The pseudocode for prediction of the location attribute is shown in Pseudocode 1.Pseudocode 1:Pseudocode for predicting location attribute.
Algorithm  p
^
m
+
1
=
pre
P
W
Input
P
W: location attribute sequence of the observation window
w
′:    the  minimum observation window
R
g
i
j
,
ϕ
i
j: associate rulesets of a regional cell
R
′
g
i
j
,
ϕ
i
j: temporary associate rulesets
Output
p
^
m
+
1: predicted  location attribute
while (w
≥
w
′)
if  Match
P
W
,
R
g
i
j
,
ϕ
i
j  // find a matching associate rules
R
′
g
i
j
,
ϕ
i
j
⇐
Match
P
W
,
R
g
i
j
,
ϕ
i
j  // put the matched rules into the temporary rulesets
break
else
w
←
w
-
1; P
W
←
P
W
-
1
end while
for  Scan
R
′
g
i
j
,
ϕ
i
j  // scan the temporary rulesets
if  ϕ
1
=
max
⁡
ϕ
i
j         // find the largest degree of confidence
p
^
m
+
1
←
R
′
(
g
i
j
,
ϕ
1
)
end forHere,w
′ is the minimum observation window, R
′
s
i
j
,
ϕ
i
j is a temporary ruleset to store matched associate items and theconfidence, and P
W
-
1
=
p
m
-
w
+
2
,
p
m
-
w
+
3
,
…
,
p
m is a location attribute sequence with an observation window of one-bit duration. M
a
t
c
h
P
W
,
R
g
i
j
,
ϕ
i
j is a rule matching function, whose output is an associate rule item matching successfully with P
W, and the output is N
U
L
L when the match fails. For example, if the coordinate points of P
W belong to the same cell g
i
j or neighbor cell, we use the rule matching function M
a
t
c
h
P
W
,
R
g
i
j
,
ϕ
i
j to scan associate rulesets R
g
i
j
,
ϕ
i
j for three matched associate items:(11)
p
1
,
p
2
,
…
,
p
m
⟶
p
m
+
1
′
,
ϕ
1
p
1
,
p
2
,
…
,
p
m
⟶
p
m
+
1
′
′
,
ϕ
2
p
1
,
p
2
,
…
,
p
m
⟶
p
m
+
1
′
′
′
,
ϕ
3
,where theconfidencesatisfies ϕ
1
+
ϕ
2
+
ϕ
3
=
1. If ϕ
1
=
max
⁡
ϕ
1
,
ϕ
2
,
ϕ
3, the location attribute of the predicted access request is p
^
m
+
1
=
p
m
+
1
′.(
2) Type Attribute Prediction. The type attribute prediction is similar to the location attribute prediction. Scan associate rulesets R
s
i
j
,
ϕ
i
j according to the predictive function Pre
s. Find the associate rules matched with the type attribute sequence in the current observation window. Then, select the confidence rules with the largest confidence as the output results. Suppose that s
1
,
s
2
,
…
,
s
m
→
s
m
+
1
′
,
ϕ
1 is the associate rule matched successfully with S
W, and ϕ
1 is the largest; then, the type attribute of the predicted access request is s
^
m
+
1
=
s
m
+
1
′.(
3) Time Attribute Prediction. The time attribute prediction is based on the predictive function Pre
t. First, we perform d-order difference processing for T
W to achieve stationarity. Then, we use ARIMA to calculate the time attribute of the predicted access request; the result is given by(12)
t
^
m
+
1
=
t
m
+
1
′
=
t
m
,
d
=
0
2
t
m
-
t
m
-
1
,
d
=
1
3
t
m
-
3
t
m
-
1
+
t
m
-
2
,
d
=
2
.


#### 3.2.2. Conjoint Attribute Predictive Function

For the access requests that satisfy formula (9), we predict the next access request b
^
m
+
1 according to the conjoint attribute prediction function Pre
′
′
(
p
,
s
,
t
) and then form the predictive access request: (13)
b
^
m
+
1
=
p
^
m
+
1
,
s
^
m
+
1
,
t
^
m
+
1
=
p
m
,
s
m
,
t
m
,
d
=
0
p
m
,
s
m
,
2
t
m
-
t
m
-
1
,
d
=
1
p
m
,
s
m
,
3
t
m
-
3
t
m
-
1
+
t
m
-
2
,
d
=
2
.


### 3.3. Data Prefetching

Data prefetching is performed to load data into the cache in accordance with the predicted request. To avoid unnecessary consumption of memory and computing resources, we built two data structure queues of lengthλ. One is used to store the actual access requests and the other to store the predicted requests. By calculating the consistent rate of the two queues, we can judge the degree of credibility of the current predicted requests. If the consistent rate achieves the predefined threshold, we assume that the predicted request is credible, and accordingly we carry out the data prefetching.Suppose that the actual access request stored in a queue of lengthλ is b
m
-
λ
+
1
,
b
m
-
λ
+
2
,
…
,
b
m and the predicted request is b
^
m
-
λ
+
1
,
b
^
m
-
λ
+
2
,
…
,
b
^
m. If they satisfy formula (14), we assume that the predicted request b
^
m
+
1
=
p
^
m
+
1
,
s
^
m
+
1
,
t
^
m
+
1 is credible, and we load the corresponding data d
n
+
1 into the cache: (14)
p
^
m
-
λ
+
1
=
p
m
-
λ
+
1
,
p
^
m
-
λ
+
2
=
p
m
-
λ
+
2
,
…
,
p
^
m
=
p
m
s
^
m
-
λ
+
1
=
s
m
-
λ
+
1
,
s
^
m
-
λ
+
2
=
s
m
-
λ
+
2
,
…
,
s
^
m
=
s
m
t
^
m
-
λ
+
1
=
t
m
-
λ
+
1
,
t
^
m
-
λ
+
2
=
t
m
-
λ
+
2
,
…
,
t
^
m
=
t
m
.


## 3.1. Construction of Predictive Function

The predictive function consists of the independent attribute prediction functionPre
′
p
,
s
,
t
=
Pre
p
,
P
r
e
s
,
P
r
e
t and the conjoint attribute prediction function Pre
′
′
p
,
s
,
t.


### 3.1.1. Construction of Independent Attribute Predictive Function

(
1) Construction of Location Attribute Predictive Function. The key aspect of the location attribute predictive function Pre
p is the correlation of access requests in the spatial domain. Therefore, we can use the association rule algorithm [18] to mine associate items p
i
→
p
j from the sequence of location attributes P
n
=
p
1
,
p
2
,
p
3
,
…
,
p
n and construct the location attribute predictive function according to the associate rulesets.(a) Regional Meshing. The location attribute of spatiotemporal data represents the geographical location of a data source in a smart city, usually expressed by latitude and longitude coordinates p
=
x
,
y. However, solving the association rules of the location attribute coordinate points directly requires numerous calculations. Moreover, updating, modification, addition, or deletion operations on location attributes will require recalculation for the entire area. Therefore, we exploit regional meshing for the entire area, which allows for both the early solution of rules and late update of associate rules in the cell area, thereby providing partial and incremental solution of association rules and reducing the computation considerably.Suppose that the geographic area is a two-dimensional Euclidean rectangular space0
,
X
0
,
Y in a smart city. We divide it into r
o
w
×
c
o
l rectangular cells with coding, where the code of the area covered by the ith row jth column is g
i
j
=
j
+
c
o
l
·
i
-
1. Then, for any location attribute coordinate point p
k
=
x
k
,
y
k in the geographic area, we assume that it belongs to the cell g
i
j if it satisfies the following equation: (2)
i
-
1
X
row
≤
x
k
≤
i
X
row
,
1
≤
i
≤
row
j
-
1
Y
col
≤
y
k
≤
j
Y
col
,
1
≤
j
≤
col
.Figure1(a) shows the geographic rectangular area divided into 4 × 5 cells and the meshing cell coding. Figure 1(b) shows all the neighbor cells of the cell g
i
j.Figure 1
Regional meshing and coding: (a) meshing cell coding; (b) neighbor cells ofg
i
j.
(a)
(b)(b) Construction of Predictive Function. Through regional meshing, we can use an association rule algorithm to mine the associate items of each cell from the sequence of location attributes P
n
=
p
1
,
p
2
,
p
3
,
…
,
p
n and construct the location attribute predictive function Pre
p according to the associate rulesets. The specific steps are as follows:(1)
Calculate the location coordinate setsp
g
i
j
=
p
g
1
,
p
g
2
,
…
,
p
g
m
,
…
,
p
g
n contained in the cell g
i
j and its neighbor cells, as shown in Figure 1(b).
(2)
Count the number of times every coordinate pointp
g
i
,
p
g
i
∈
p
g
i
j, appears in the sequence of location attributes, that is,support, and compare it with the predefinedsupport threshold
δ
p to find frequent 1-itemsets. By looping through the location attribute sequence via the connection and cut between the frequent itemsets, we can find frequent 2-itemsets, frequent 3-itemsets, and so on until frequent m-, 2
≤
m
≤
n, itemsets.
(3)
Calculate theconfidence of each frequent m-itemsets and its subset frequentm-1-itemsets. Generate association rules p
g
i
,
p
g
i
+
1
,
…
,
p
g
i
+
m
-
1
→
p
g
i
+
m
,
ϕ
g
i
g
i
+
m on those associate itemsets whoseconfidence values are greater than theconfidence threshold
ϕ
p. Then, form the association rulesets R
g
i
j
,
ϕ
i
j
=
⋃
m
p
g
i
,
p
g
i
+
1
,
…
,
p
g
i
+
m
-
1
→
p
g
i
+
m
,
ϕ
g
i
g
i
+
m of the cell g
i
j.
(4)
Loop through each cell in the geographical area to calculate the location attribute association rulesets and merge them to form the associate rulesetsR
p
i
j
,
ϕ
i
j
=
⋃
i
,
j
R
g
i
j
,
ϕ
i
j of the entire geographic area. Then, construct the location attribute predictive function,(3)
Pre
p
=
Match
p
,
R
p
i
j
,
ϕ
i
j
,
whereM
a
t
c
h
· is a rule matching function, whose output is an associate rule matching successfully with location attribute p; the specific methods are as in Section 3.2.1.(
2) Construction of Type Attribute Predictive Function. The key aspect of the type attribute predictive function Pre
s is the correlation of access requests in the type domain. Therefore, we can use the association rule algorithm to mine associate items s
i
→
s
j from the sequence of type attributes S
n
=
s
1
,
s
2
,
s
3
,
…
,
s
n and construct the type attribute predictive function according to the associate rulesets. The specific steps are as follows:(1)
Count the number of times everys
i
,
s
i
∈
S, appears in the sequence of type attributes, that is,support, and compare it with the predefinedsupport threshold
δ
s to find frequent 1-itemsets. By looping through the type attribute sequences via the connection and cut between the frequent itemsets, we can find frequent 2-itemsets, frequent 3-itemsets, and so on until frequentm-, 2
≤
m
≤
n, itemsets.
(2)
Calculate theconfidenceof each frequent m-itemsets and its subset frequentm-1-itemsets. Generate association rules s
i
,
s
i
+
1
,
…
,
s
i
+
m
-
1
→
s
i
+
m
,
ϕ
i
,
i
+
m on those associate itemsets whoseconfidence values are greater than theconfidence threshold
ϕ
s, and form the association rulesets R
s
i
j
,
ϕ
i
j
=
⋃
m
s
i
,
s
i
+
1
,
…
,
s
i
+
m
-
1
→
s
i
+
m
,
ϕ
i
,
i
+
m. Then, construct the type attribute predictive function(4)
Pre
s
=
Match
s
,
R
s
i
j
,
ϕ
i
j
.(3
) Construction of Time Attribute Predictive Function. The key aspect of the time attribute predictive function Pre
t is the correlation of access requests in the time domain. Therefore, we can analyze the sequence of time attributes T
n
=
t
1
,
t
2
,
t
3
,
…
,
t
n, to develop a model to describe this underlying correlation.The time attribute sequence of user access requests is a typical nonstationary sequence influenced by a predefined application, which has obvious trends in a local range. ARIMA is an important and widely used short-term time series prediction model. It can predict future values according to the current and historical values of the sequence, but it requires the sequence to be stationary [19–23]. To this end, we can piecewise represent the time attribute sequence and perform difference processing to achieve local stationarity. Then, we build the ARIMA model and construct the time attribute predictive function.(a) Piecewise Representation of Time Attribute Sequence. We use extreme point detection based on the slope change and piecewise representation of the time attribute sequence according to local extreme values in the sequence (the beginning and end value of each curve). The method calculates the slope difference t
i
-
t
i
-
1
-
t
i
+
1
-
t
i
/
Δ
T of the line segment formed by sequence value t
i, 1
<
i
<
n, and its neighbor points t
i
-
1, t
i
+
1, where Δ
T is the time interval of the access request. Then, we compare the slope difference with a predefined threshold. If it is greater than or equal to the predefined threshold, we assume that t
i is a local extremum. Finally, by using local extrema, we can piecewise represent the time attribute sequence as follows:(5)
T
=
t
1
L
,
t
1
R
,
t
2
L
,
t
2
R
,
…
,
t
k
L
,
t
k
R
,where t
i
L is the starting value of i
,
i
∈
k, segment, t
i
R is the end value of i
,
i
∈
k, piecewise, and k is the number of piecewise segments.(b) Construction of Predictive Function. With the abovementioned piecewise representation and difference processing, we can realize local stationarity of the time attribute sequence and build ARIMA to construct the time attribute predictive function Pre
t. By introducing the k-step lag operator B
k
t
h
n
=
t
h
n
-
k and d-order difference w
n
=
Δ
d
t
h
n
=
1
-
B
d
t
h
n, d
=
0,1
,
2, the standard A
R
I
M
A
p
,
d
,
q model can be expressed as follows: (6)
w
n
=
φ
1
w
n
-
1
+
φ
2
w
n
-
2
+
⋯
+
φ
p
w
n
-
p
+
δ
+
u
t
+
θ
1
u
t
-
1
+
θ
2
u
t
-
2
+
⋯
+
θ
q
u
t
-
q
,where w
n
=
Δ
d
t
n
=
1
-
B
d
t
n is the difference order, φ
1
,
φ
2
,
…
,
φ
p are the autoregressive parameters, θ
1
,
θ
2
,
…
,
θ
q are the moving average parameters, δ is a constant that indicates that the sequence is nonzero mean, and u
t is white noise sequence.Suppose that the right-and-left local extreme value ofj, 1
<
j
<
k, piecewise is t
j
L
=
t
m, t
j
R
=
t
n. Then, according to formula (5), we can piecewise represent it as t
j
L
,
t
j
R
=
t
m
,
t
m
+
1
,
…
,
t
n, and, through d-order difference processing, it can be stationary. Judging from the fact that the user access is restricted by the predefined application, the change trend of the time attribute sequence can be only linear and regular, which means that it remains unchanged in terms of cycle and step size, so the parameters are p
=
1, φ
1
=
1. At the same time, the time attribute sequence of access request is not affected by external random interference, so the parameters are u
t
=
0, q
=
0.Finally, we can buildA
R
I
M
A
1
,
d
,
0 as w
n
=
w
n
-
1. Combined with the lag operator B
k
t
h
n
=
t
h
n
-
k and d-order difference, the time attribute predictive function Pre
(
t
) can be expressed as follows:(7)
Pre
t
n
=
t
n
-
1
,
d
=
0
2
t
n
-
1
-
t
n
-
2
,
d
=
1
3
t
n
-
1
-
3
t
n
-
2
+
t
n
-
3
,
d
=
2
.


### 3.1.2. Construction of Conjoint Attribute Predictive Function

Because the access requests with cross-correlation of spatiotemporal attributes account for a very small proportion of the total number of requests, it is difficult to jointly analyze the attributes. Therefore, we analyze only the access requests that have special cross-correlation of spatiotemporal attributes, that is, if the sequence of location attributesP
l
=
p
i
,
p
i
+
1
,
…
,
p
i
+
l and the sequence of type attributes S
l
=
s
i
+
1
,
s
i
+
2
,
…
,
s
i
+
l remain unchanged and the length reaches the minimum threshold l
=
3, as expressed by the following equation:(8)
p
i
+
1
=
p
i
+
2
=
⋯
=
p
i
+
l
,
s
i
+
1
=
s
i
+
2
=
⋯
=
s
i
+
l
,
l
≥
3
.Then, we assume that the location attribute and the type attribute remain unchanged in the next access request, and the time attribute can be predicted byPre
(
t
). Finally, the conjoint attribute predictive function Pre
′
′
p
,
s
,
t can be constructed as(9)
Pre
′
′
p
n
,
s
n
,
t
n
=
p
n
-
1
,
s
n
-
1
,
t
n
-
1
,
d
=
0
p
n
-
1
,
s
n
-
1
,
2
t
n
-
1
-
t
n
-
2
,
d
=
1
p
n
-
1
,
s
n
-
1
,
3
t
n
-
1
-
3
t
n
-
2
+
t
n
-
3
,
d
=
2
.


## 3.1.1. Construction of Independent Attribute Predictive Function

(
1) Construction of Location Attribute Predictive Function. The key aspect of the location attribute predictive function Pre
p is the correlation of access requests in the spatial domain. Therefore, we can use the association rule algorithm [18] to mine associate items p
i
→
p
j from the sequence of location attributes P
n
=
p
1
,
p
2
,
p
3
,
…
,
p
n and construct the location attribute predictive function according to the associate rulesets.(a) Regional Meshing. The location attribute of spatiotemporal data represents the geographical location of a data source in a smart city, usually expressed by latitude and longitude coordinates p
=
x
,
y. However, solving the association rules of the location attribute coordinate points directly requires numerous calculations. Moreover, updating, modification, addition, or deletion operations on location attributes will require recalculation for the entire area. Therefore, we exploit regional meshing for the entire area, which allows for both the early solution of rules and late update of associate rules in the cell area, thereby providing partial and incremental solution of association rules and reducing the computation considerably.Suppose that the geographic area is a two-dimensional Euclidean rectangular space0
,
X
0
,
Y in a smart city. We divide it into r
o
w
×
c
o
l rectangular cells with coding, where the code of the area covered by the ith row jth column is g
i
j
=
j
+
c
o
l
·
i
-
1. Then, for any location attribute coordinate point p
k
=
x
k
,
y
k in the geographic area, we assume that it belongs to the cell g
i
j if it satisfies the following equation: (2)
i
-
1
X
row
≤
x
k
≤
i
X
row
,
1
≤
i
≤
row
j
-
1
Y
col
≤
y
k
≤
j
Y
col
,
1
≤
j
≤
col
.Figure1(a) shows the geographic rectangular area divided into 4 × 5 cells and the meshing cell coding. Figure 1(b) shows all the neighbor cells of the cell g
i
j.Figure 1
Regional meshing and coding: (a) meshing cell coding; (b) neighbor cells ofg
i
j.
(a)
(b)(b) Construction of Predictive Function. Through regional meshing, we can use an association rule algorithm to mine the associate items of each cell from the sequence of location attributes P
n
=
p
1
,
p
2
,
p
3
,
…
,
p
n and construct the location attribute predictive function Pre
p according to the associate rulesets. The specific steps are as follows:(1)
Calculate the location coordinate setsp
g
i
j
=
p
g
1
,
p
g
2
,
…
,
p
g
m
,
…
,
p
g
n contained in the cell g
i
j and its neighbor cells, as shown in Figure 1(b).
(2)
Count the number of times every coordinate pointp
g
i
,
p
g
i
∈
p
g
i
j, appears in the sequence of location attributes, that is,support, and compare it with the predefinedsupport threshold
δ
p to find frequent 1-itemsets. By looping through the location attribute sequence via the connection and cut between the frequent itemsets, we can find frequent 2-itemsets, frequent 3-itemsets, and so on until frequent m-, 2
≤
m
≤
n, itemsets.
(3)
Calculate theconfidence of each frequent m-itemsets and its subset frequentm-1-itemsets. Generate association rules p
g
i
,
p
g
i
+
1
,
…
,
p
g
i
+
m
-
1
→
p
g
i
+
m
,
ϕ
g
i
g
i
+
m on those associate itemsets whoseconfidence values are greater than theconfidence threshold
ϕ
p. Then, form the association rulesets R
g
i
j
,
ϕ
i
j
=
⋃
m
p
g
i
,
p
g
i
+
1
,
…
,
p
g
i
+
m
-
1
→
p
g
i
+
m
,
ϕ
g
i
g
i
+
m of the cell g
i
j.
(4)
Loop through each cell in the geographical area to calculate the location attribute association rulesets and merge them to form the associate rulesetsR
p
i
j
,
ϕ
i
j
=
⋃
i
,
j
R
g
i
j
,
ϕ
i
j of the entire geographic area. Then, construct the location attribute predictive function,(3)
Pre
p
=
Match
p
,
R
p
i
j
,
ϕ
i
j
,
whereM
a
t
c
h
· is a rule matching function, whose output is an associate rule matching successfully with location attribute p; the specific methods are as in Section 3.2.1.(
2) Construction of Type Attribute Predictive Function. The key aspect of the type attribute predictive function Pre
s is the correlation of access requests in the type domain. Therefore, we can use the association rule algorithm to mine associate items s
i
→
s
j from the sequence of type attributes S
n
=
s
1
,
s
2
,
s
3
,
…
,
s
n and construct the type attribute predictive function according to the associate rulesets. The specific steps are as follows:(1)
Count the number of times everys
i
,
s
i
∈
S, appears in the sequence of type attributes, that is,support, and compare it with the predefinedsupport threshold
δ
s to find frequent 1-itemsets. By looping through the type attribute sequences via the connection and cut between the frequent itemsets, we can find frequent 2-itemsets, frequent 3-itemsets, and so on until frequentm-, 2
≤
m
≤
n, itemsets.
(2)
Calculate theconfidenceof each frequent m-itemsets and its subset frequentm-1-itemsets. Generate association rules s
i
,
s
i
+
1
,
…
,
s
i
+
m
-
1
→
s
i
+
m
,
ϕ
i
,
i
+
m on those associate itemsets whoseconfidence values are greater than theconfidence threshold
ϕ
s, and form the association rulesets R
s
i
j
,
ϕ
i
j
=
⋃
m
s
i
,
s
i
+
1
,
…
,
s
i
+
m
-
1
→
s
i
+
m
,
ϕ
i
,
i
+
m. Then, construct the type attribute predictive function(4)
Pre
s
=
Match
s
,
R
s
i
j
,
ϕ
i
j
.(3
) Construction of Time Attribute Predictive Function. The key aspect of the time attribute predictive function Pre
t is the correlation of access requests in the time domain. Therefore, we can analyze the sequence of time attributes T
n
=
t
1
,
t
2
,
t
3
,
…
,
t
n, to develop a model to describe this underlying correlation.The time attribute sequence of user access requests is a typical nonstationary sequence influenced by a predefined application, which has obvious trends in a local range. ARIMA is an important and widely used short-term time series prediction model. It can predict future values according to the current and historical values of the sequence, but it requires the sequence to be stationary [19–23]. To this end, we can piecewise represent the time attribute sequence and perform difference processing to achieve local stationarity. Then, we build the ARIMA model and construct the time attribute predictive function.(a) Piecewise Representation of Time Attribute Sequence. We use extreme point detection based on the slope change and piecewise representation of the time attribute sequence according to local extreme values in the sequence (the beginning and end value of each curve). The method calculates the slope difference t
i
-
t
i
-
1
-
t
i
+
1
-
t
i
/
Δ
T of the line segment formed by sequence value t
i, 1
<
i
<
n, and its neighbor points t
i
-
1, t
i
+
1, where Δ
T is the time interval of the access request. Then, we compare the slope difference with a predefined threshold. If it is greater than or equal to the predefined threshold, we assume that t
i is a local extremum. Finally, by using local extrema, we can piecewise represent the time attribute sequence as follows:(5)
T
=
t
1
L
,
t
1
R
,
t
2
L
,
t
2
R
,
…
,
t
k
L
,
t
k
R
,where t
i
L is the starting value of i
,
i
∈
k, segment, t
i
R is the end value of i
,
i
∈
k, piecewise, and k is the number of piecewise segments.(b) Construction of Predictive Function. With the abovementioned piecewise representation and difference processing, we can realize local stationarity of the time attribute sequence and build ARIMA to construct the time attribute predictive function Pre
t. By introducing the k-step lag operator B
k
t
h
n
=
t
h
n
-
k and d-order difference w
n
=
Δ
d
t
h
n
=
1
-
B
d
t
h
n, d
=
0,1
,
2, the standard A
R
I
M
A
p
,
d
,
q model can be expressed as follows: (6)
w
n
=
φ
1
w
n
-
1
+
φ
2
w
n
-
2
+
⋯
+
φ
p
w
n
-
p
+
δ
+
u
t
+
θ
1
u
t
-
1
+
θ
2
u
t
-
2
+
⋯
+
θ
q
u
t
-
q
,where w
n
=
Δ
d
t
n
=
1
-
B
d
t
n is the difference order, φ
1
,
φ
2
,
…
,
φ
p are the autoregressive parameters, θ
1
,
θ
2
,
…
,
θ
q are the moving average parameters, δ is a constant that indicates that the sequence is nonzero mean, and u
t is white noise sequence.Suppose that the right-and-left local extreme value ofj, 1
<
j
<
k, piecewise is t
j
L
=
t
m, t
j
R
=
t
n. Then, according to formula (5), we can piecewise represent it as t
j
L
,
t
j
R
=
t
m
,
t
m
+
1
,
…
,
t
n, and, through d-order difference processing, it can be stationary. Judging from the fact that the user access is restricted by the predefined application, the change trend of the time attribute sequence can be only linear and regular, which means that it remains unchanged in terms of cycle and step size, so the parameters are p
=
1, φ
1
=
1. At the same time, the time attribute sequence of access request is not affected by external random interference, so the parameters are u
t
=
0, q
=
0.Finally, we can buildA
R
I
M
A
1
,
d
,
0 as w
n
=
w
n
-
1. Combined with the lag operator B
k
t
h
n
=
t
h
n
-
k and d-order difference, the time attribute predictive function Pre
(
t
) can be expressed as follows:(7)
Pre
t
n
=
t
n
-
1
,
d
=
0
2
t
n
-
1
-
t
n
-
2
,
d
=
1
3
t
n
-
1
-
3
t
n
-
2
+
t
n
-
3
,
d
=
2
.


## 3.1.2. Construction of Conjoint Attribute Predictive Function

Because the access requests with cross-correlation of spatiotemporal attributes account for a very small proportion of the total number of requests, it is difficult to jointly analyze the attributes. Therefore, we analyze only the access requests that have special cross-correlation of spatiotemporal attributes, that is, if the sequence of location attributesP
l
=
p
i
,
p
i
+
1
,
…
,
p
i
+
l and the sequence of type attributes S
l
=
s
i
+
1
,
s
i
+
2
,
…
,
s
i
+
l remain unchanged and the length reaches the minimum threshold l
=
3, as expressed by the following equation:(8)
p
i
+
1
=
p
i
+
2
=
⋯
=
p
i
+
l
,
s
i
+
1
=
s
i
+
2
=
⋯
=
s
i
+
l
,
l
≥
3
.Then, we assume that the location attribute and the type attribute remain unchanged in the next access request, and the time attribute can be predicted byPre
(
t
). Finally, the conjoint attribute predictive function Pre
′
′
p
,
s
,
t can be constructed as(9)
Pre
′
′
p
n
,
s
n
,
t
n
=
p
n
-
1
,
s
n
-
1
,
t
n
-
1
,
d
=
0
p
n
-
1
,
s
n
-
1
,
2
t
n
-
1
-
t
n
-
2
,
d
=
1
p
n
-
1
,
s
n
-
1
,
3
t
n
-
1
-
3
t
n
-
2
+
t
n
-
3
,
d
=
2
.


## 3.2. Prediction Method for Access Requests

The purpose of this section is to show how to use the predictive function to predict the user’s next access request based on the current one.Suppose that the current user access request can be expressed as the sequenceB
=
b
1
,
b
2
,
b
3
,
…
,
b
m, and spatiotemporal attributes sequences are B
=
p
1
,
s
1
,
t
1
,
p
2
,
s
2
,
t
2
,
…
,
p
m
,
s
m
,
t
m
=
P
m
,
S
m
,
T
m, where each b
i
=
p
i
,
s
i
,
t
i, b
i
∈
B, represents one user access request. First, we parameterize it and extract the spatiotemporal attributes to form the spatiotemporal attribute sequence. Then, according to the access request predictive functions Pre
′
p
,
s
,
t and Pre
′
′
p
,
s
,
t, we take the spatiotemporal attribute sequence as the input, and the output b
^
m
+
1
=
p
^
m
+
1
,
s
^
m
+
1
,
t
^
m
+
1 is predicted as the access request.We define a sliding and adaptive observation window with initial sizew, and we take the spatiotemporal attribute sequence {
P
W
,
S
W
,
T
W
}, which falls into the observation window, as the input of the prediction function. Then, we judge whether {
P
W
,
S
W
,
T
W
} can satisfy formula (8). If it satisfies (8), we use the conjoint predictive function; otherwise, we use the independent attribute predictive function. As a result, p
^
m
+
1, s
^
m
+
1, and t
^
m
+
1 can be predicted. Here,(10)
P
W
=
p
m
-
w
+
1
,
p
m
-
w
+
2
,
…
,
p
m
S
W
=
s
m
-
w
+
1
,
s
m
-
w
+
2
,
…
,
s
m
T
W
=
t
m
-
w
+
1
,
t
m
-
w
+
2
,
…
,
t
m
.


### 3.2.1. Independent Attribute Predictive Function

For the access requests that dissatisfy formula (8), we predict the spatiotemporal attribute according to independent attribute prediction Pre
′
p
,
s
,
t
=
Pre
p
,
P
r
e
s
,
P
r
e
t, and then we form the predictive access request b
^
m
+
1
=
p
^
m
+
1
,
s
^
m
+
1
,
t
^
m
+
1.(
1) Location Attribute Prediction. Because regional meshing is used for the entire geographic area, before prediction, we need to judge whether the coordinate points belong to the same cell or neighbor cells according to formula (2). If the points belong to the same cell, we trigger the prediction; otherwise, we forgo prediction. The pseudocode for prediction of the location attribute is shown in Pseudocode 1.Pseudocode 1:Pseudocode for predicting location attribute.
Algorithm  p
^
m
+
1
=
pre
P
W
Input
P
W: location attribute sequence of the observation window
w
′:    the  minimum observation window
R
g
i
j
,
ϕ
i
j: associate rulesets of a regional cell
R
′
g
i
j
,
ϕ
i
j: temporary associate rulesets
Output
p
^
m
+
1: predicted  location attribute
while (w
≥
w
′)
if  Match
P
W
,
R
g
i
j
,
ϕ
i
j  // find a matching associate rules
R
′
g
i
j
,
ϕ
i
j
⇐
Match
P
W
,
R
g
i
j
,
ϕ
i
j  // put the matched rules into the temporary rulesets
break
else
w
←
w
-
1; P
W
←
P
W
-
1
end while
for  Scan
R
′
g
i
j
,
ϕ
i
j  // scan the temporary rulesets
if  ϕ
1
=
max
⁡
ϕ
i
j         // find the largest degree of confidence
p
^
m
+
1
←
R
′
(
g
i
j
,
ϕ
1
)
end forHere,w
′ is the minimum observation window, R
′
s
i
j
,
ϕ
i
j is a temporary ruleset to store matched associate items and theconfidence, and P
W
-
1
=
p
m
-
w
+
2
,
p
m
-
w
+
3
,
…
,
p
m is a location attribute sequence with an observation window of one-bit duration. M
a
t
c
h
P
W
,
R
g
i
j
,
ϕ
i
j is a rule matching function, whose output is an associate rule item matching successfully with P
W, and the output is N
U
L
L when the match fails. For example, if the coordinate points of P
W belong to the same cell g
i
j or neighbor cell, we use the rule matching function M
a
t
c
h
P
W
,
R
g
i
j
,
ϕ
i
j to scan associate rulesets R
g
i
j
,
ϕ
i
j for three matched associate items:(11)
p
1
,
p
2
,
…
,
p
m
⟶
p
m
+
1
′
,
ϕ
1
p
1
,
p
2
,
…
,
p
m
⟶
p
m
+
1
′
′
,
ϕ
2
p
1
,
p
2
,
…
,
p
m
⟶
p
m
+
1
′
′
′
,
ϕ
3
,where theconfidencesatisfies ϕ
1
+
ϕ
2
+
ϕ
3
=
1. If ϕ
1
=
max
⁡
ϕ
1
,
ϕ
2
,
ϕ
3, the location attribute of the predicted access request is p
^
m
+
1
=
p
m
+
1
′.(
2) Type Attribute Prediction. The type attribute prediction is similar to the location attribute prediction. Scan associate rulesets R
s
i
j
,
ϕ
i
j according to the predictive function Pre
s. Find the associate rules matched with the type attribute sequence in the current observation window. Then, select the confidence rules with the largest confidence as the output results. Suppose that s
1
,
s
2
,
…
,
s
m
→
s
m
+
1
′
,
ϕ
1 is the associate rule matched successfully with S
W, and ϕ
1 is the largest; then, the type attribute of the predicted access request is s
^
m
+
1
=
s
m
+
1
′.(
3) Time Attribute Prediction. The time attribute prediction is based on the predictive function Pre
t. First, we perform d-order difference processing for T
W to achieve stationarity. Then, we use ARIMA to calculate the time attribute of the predicted access request; the result is given by(12)
t
^
m
+
1
=
t
m
+
1
′
=
t
m
,
d
=
0
2
t
m
-
t
m
-
1
,
d
=
1
3
t
m
-
3
t
m
-
1
+
t
m
-
2
,
d
=
2
.


### 3.2.2. Conjoint Attribute Predictive Function

For the access requests that satisfy formula (9), we predict the next access request b
^
m
+
1 according to the conjoint attribute prediction function Pre
′
′
(
p
,
s
,
t
) and then form the predictive access request: (13)
b
^
m
+
1
=
p
^
m
+
1
,
s
^
m
+
1
,
t
^
m
+
1
=
p
m
,
s
m
,
t
m
,
d
=
0
p
m
,
s
m
,
2
t
m
-
t
m
-
1
,
d
=
1
p
m
,
s
m
,
3
t
m
-
3
t
m
-
1
+
t
m
-
2
,
d
=
2
.


## 3.2.1. Independent Attribute Predictive Function

For the access requests that dissatisfy formula (8), we predict the spatiotemporal attribute according to independent attribute prediction Pre
′
p
,
s
,
t
=
Pre
p
,
P
r
e
s
,
P
r
e
t, and then we form the predictive access request b
^
m
+
1
=
p
^
m
+
1
,
s
^
m
+
1
,
t
^
m
+
1.(
1) Location Attribute Prediction. Because regional meshing is used for the entire geographic area, before prediction, we need to judge whether the coordinate points belong to the same cell or neighbor cells according to formula (2). If the points belong to the same cell, we trigger the prediction; otherwise, we forgo prediction. The pseudocode for prediction of the location attribute is shown in Pseudocode 1.Pseudocode 1:Pseudocode for predicting location attribute.
Algorithm  p
^
m
+
1
=
pre
P
W
Input
P
W: location attribute sequence of the observation window
w
′:    the  minimum observation window
R
g
i
j
,
ϕ
i
j: associate rulesets of a regional cell
R
′
g
i
j
,
ϕ
i
j: temporary associate rulesets
Output
p
^
m
+
1: predicted  location attribute
while (w
≥
w
′)
if  Match
P
W
,
R
g
i
j
,
ϕ
i
j  // find a matching associate rules
R
′
g
i
j
,
ϕ
i
j
⇐
Match
P
W
,
R
g
i
j
,
ϕ
i
j  // put the matched rules into the temporary rulesets
break
else
w
←
w
-
1; P
W
←
P
W
-
1
end while
for  Scan
R
′
g
i
j
,
ϕ
i
j  // scan the temporary rulesets
if  ϕ
1
=
max
⁡
ϕ
i
j         // find the largest degree of confidence
p
^
m
+
1
←
R
′
(
g
i
j
,
ϕ
1
)
end forHere,w
′ is the minimum observation window, R
′
s
i
j
,
ϕ
i
j is a temporary ruleset to store matched associate items and theconfidence, and P
W
-
1
=
p
m
-
w
+
2
,
p
m
-
w
+
3
,
…
,
p
m is a location attribute sequence with an observation window of one-bit duration. M
a
t
c
h
P
W
,
R
g
i
j
,
ϕ
i
j is a rule matching function, whose output is an associate rule item matching successfully with P
W, and the output is N
U
L
L when the match fails. For example, if the coordinate points of P
W belong to the same cell g
i
j or neighbor cell, we use the rule matching function M
a
t
c
h
P
W
,
R
g
i
j
,
ϕ
i
j to scan associate rulesets R
g
i
j
,
ϕ
i
j for three matched associate items:(11)
p
1
,
p
2
,
…
,
p
m
⟶
p
m
+
1
′
,
ϕ
1
p
1
,
p
2
,
…
,
p
m
⟶
p
m
+
1
′
′
,
ϕ
2
p
1
,
p
2
,
…
,
p
m
⟶
p
m
+
1
′
′
′
,
ϕ
3
,where theconfidencesatisfies ϕ
1
+
ϕ
2
+
ϕ
3
=
1. If ϕ
1
=
max
⁡
ϕ
1
,
ϕ
2
,
ϕ
3, the location attribute of the predicted access request is p
^
m
+
1
=
p
m
+
1
′.(
2) Type Attribute Prediction. The type attribute prediction is similar to the location attribute prediction. Scan associate rulesets R
s
i
j
,
ϕ
i
j according to the predictive function Pre
s. Find the associate rules matched with the type attribute sequence in the current observation window. Then, select the confidence rules with the largest confidence as the output results. Suppose that s
1
,
s
2
,
…
,
s
m
→
s
m
+
1
′
,
ϕ
1 is the associate rule matched successfully with S
W, and ϕ
1 is the largest; then, the type attribute of the predicted access request is s
^
m
+
1
=
s
m
+
1
′.(
3) Time Attribute Prediction. The time attribute prediction is based on the predictive function Pre
t. First, we perform d-order difference processing for T
W to achieve stationarity. Then, we use ARIMA to calculate the time attribute of the predicted access request; the result is given by(12)
t
^
m
+
1
=
t
m
+
1
′
=
t
m
,
d
=
0
2
t
m
-
t
m
-
1
,
d
=
1
3
t
m
-
3
t
m
-
1
+
t
m
-
2
,
d
=
2
.


## 3.2.2. Conjoint Attribute Predictive Function

For the access requests that satisfy formula (9), we predict the next access request b
^
m
+
1 according to the conjoint attribute prediction function Pre
′
′
(
p
,
s
,
t
) and then form the predictive access request: (13)
b
^
m
+
1
=
p
^
m
+
1
,
s
^
m
+
1
,
t
^
m
+
1
=
p
m
,
s
m
,
t
m
,
d
=
0
p
m
,
s
m
,
2
t
m
-
t
m
-
1
,
d
=
1
p
m
,
s
m
,
3
t
m
-
3
t
m
-
1
+
t
m
-
2
,
d
=
2
.


## 3.3. Data Prefetching

Data prefetching is performed to load data into the cache in accordance with the predicted request. To avoid unnecessary consumption of memory and computing resources, we built two data structure queues of lengthλ. One is used to store the actual access requests and the other to store the predicted requests. By calculating the consistent rate of the two queues, we can judge the degree of credibility of the current predicted requests. If the consistent rate achieves the predefined threshold, we assume that the predicted request is credible, and accordingly we carry out the data prefetching.Suppose that the actual access request stored in a queue of lengthλ is b
m
-
λ
+
1
,
b
m
-
λ
+
2
,
…
,
b
m and the predicted request is b
^
m
-
λ
+
1
,
b
^
m
-
λ
+
2
,
…
,
b
^
m. If they satisfy formula (14), we assume that the predicted request b
^
m
+
1
=
p
^
m
+
1
,
s
^
m
+
1
,
t
^
m
+
1 is credible, and we load the corresponding data d
n
+
1 into the cache: (14)
p
^
m
-
λ
+
1
=
p
m
-
λ
+
1
,
p
^
m
-
λ
+
2
=
p
m
-
λ
+
2
,
…
,
p
^
m
=
p
m
s
^
m
-
λ
+
1
=
s
m
-
λ
+
1
,
s
^
m
-
λ
+
2
=
s
m
-
λ
+
2
,
…
,
s
^
m
=
s
m
t
^
m
-
λ
+
1
=
t
m
-
λ
+
1
,
t
^
m
-
λ
+
2
=
t
m
-
λ
+
2
,
…
,
t
^
m
=
t
m
.


## 4. Experiment

This section consists of three parts. The first part introduces the performance evaluation metrics for our prefetching scheme. The second part describes the experimental data and methods. The last part presents and discusses the results of the experiments.


### 4.1. Evaluation Metrics

We propose five criteria for performance evaluation of the proposed prefetching scheme in terms of accuracy, efficiency, and effectiveness.Prediction Accuracy. It is the correct number of predicted requests as a percentage of the total number of requests.Prediction Coverage. It is the number of predicted requests as a percentage of the total number of requests.Pattern Mining Time. It is the time consumed for mining user access patterns from the history of user access requests.Request Prediction Time. It is the average time for predicting an access request.Average Response Time. It is the average response time to obtain a single data item.


### 4.2. Experimental Data and Methods

The experimental data was obtained from Wuhan smart city network application demonstration platform, which includes 14 types of sensors in different regions; it has been generating sensor data since January 1, 2010, and provides 20 types of predefined applications to the public. We obtained the historical user access information from the user access log in the server for the period from September 1, 2014, to February 16, 2015. After processing, we generated 1,819,008 data access requests. The initial 1,628,183 requests formed the training set for mining user access patterns and constructing the predictive function. The remaining 190,825 requests formed the test set for testing the performance of the prefetching scheme.The performance of the prefetching scheme is determined by the initial size of the observation window, regional meshing level, support threshold, and confidence threshold. Considering that the pattern mining is performed offline, the objective of the prediction is to choose the association rules with the maximum confidence. In order to choose the maximum number of rules and improve the trigger probability of prediction, we set thesupport threshold at 0.05% of the total number of access requests; that is, δ
p
=
δ
s
=
0.05
%, and theconfidence thresholdwas 0.01; that is, ϕ
p
=
ϕ
s
=
0.01. Experiments were conducted to determine the changes in the evaluation metrics with different initial sizes of the observation window (w
=
2, 3, 4, 5, and 6) and different regional meshing levels (r
o
w
×
c
o
l = 1 × 1, 50 × 50, 80 × 80, 100 × 100, 120 × 120, and 150 × 150), and the average response time for users to access a single data item was recorded. Finally, we compare our prefetching algorithm (STAP, spatial-temporal attributes prediction) with associate rules discovery prefetching algorithm (ARP) proposed by [5] and neighbor selection Markov Chain prefetching algorithm (MCP) proposed by [15].


### 4.3. Experimental Results

#### 4.3.1. Prediction Accuracy and Coverage

(
1) Spatiotemporal Attribute Prediction(a) Location Attribute Prediction. The prediction accuracy and coverage of the location attribute with different regional meshing levels and observation window sizes are summarized in Table 1. As can be seen, for the same observation window size, when the meshing level increases (the area of the cell becomes smaller), the accuracy and coverage decrease. This is because the regional meshing results in the loss of the association rules between nonneighbor cells and leads to unsuccessful trigger prediction of some access requests. In contrast, for the same regional meshing level, as the observation window size increases, the accuracy gradually increases while the coverage remains unchanged. This can be explained as follows. On the one hand, the larger the window size, the greater the amount of available prediction information. On the other hand, the short rules form a subset of the long rules, and the current observation window cannot trigger prediction; the size of the window will adaptively decrease for further prediction until the minimum size is reached.Table 1
Location attribute prediction.
Regional meshing
Accuracy/coverage (%)
Window size
2
3
4
5
6
1 × 1
86.95/93.92
89.11/93.92
89.19/93.92
89.23/93.92
89.27/93.92
50 × 50
81.04/91.11
85.93/91.11
85.96/91.11
86.01/91.11
86.08/91.11
80 × 80
80.26/90.32
85.11/90.32
85.17/90.32
85.21/90.32
85.26/90.32
100 × 100
79.70/89.79
84.58/89.79
84.63/89.79
84.72/89.79
84.75/89.79
120 × 120
79.22/89.27
84.07/89.27
84.13/89.27
84.18/89.27
84.24/89.27
150 × 150
78.43/88.49
83.27/88.49
83.33/88.49
83.39/88.49
83.43/88.49(b) Type Attribute Prediction. The prediction of the type attribute is related only to the observation window size. As can be seen from Table 2, as the observation window size increases, the prediction accuracy gradually increases from 94.38% to 96.05%, while the prediction coverage remains unchanged at 96.76%. This can be explained as follows. The larger the observation window size, the greater the amount of available prediction information, and the adaptive observation window size achieves exactly the same prediction coverage.Table 2
Type attribute prediction.
Window size
2
3
4
5
6
Accuracy (%)
94.38
95.28
95.52
95.80
96.05
Coverage (%)
96.76
96.76
96.76
96.76
96.76(c) Time Attribute Prediction. The time attributesare predicted by the ARIMA model, because the change trend of the time attribute sequences comprises only three situations (remaining unchanged, changing periodically, and changing in step length). Furthermore, the adaptive observation window size makes the ARIMA model available for all the time attribute sequences. Therefore, the prediction errors appear only in the case of inconsistent change trends of sequence, and all requests falling within the observation windows can be predicted. The experimental results show that the prediction accuracy of the time attribute with different observation windows sizes is 88.63%, while the prediction coverage is 100%.(
2) Access Request Prediction. The final prediction request must include three basic attributes: location, time, and type. Therefore, we should synthesize the spatiotemporal attributes predicted previously to form the access request.The prediction accuracy and coverage of the user access requests with different regional meshing levels and observation window sizes are shown in Figures2 and 3. We can see that, without meshing for the same observation window size, the prediction accuracy and coverage are the highest, and as the meshing level increases, the prediction accuracy gradually decreases. This is because the regional meshing can result in the loss of association rules between nonneighbor cells and reduce the probability of triggering prediction. In contrast, at the same regional meshing level, the prediction accuracy at different observation window sizes varies slightly, except for a window size of 2, where the prediction accuracy is significantly lower. And the curves for different window sizes overlap completely. These results can be explained as follows. First, the rules mined from user access are very similar when the rule length is greater than 2. Second, when the window size w
=
2, it will fail to trigger joint property prediction. Finally, as stated before, the adaptive observation window size has no effect on the coverage.Figure 2
Request accuracy.Figure 3
Request coverage.Figures4 and 5 show the prediction accuracy and coverage of the user access of the proposed prefetching scheme STAP and another two schemes, ARP [5] and MCP [15], with different observation window sizes. Regional meshing levels were set as 50
∗
50 in the experiment, the observation window size is the active session window size in ARP, and the number of previous movements was monitored in MCP. As shown in Figure 4, the STAP achieves the highest prediction accuracy compared with the other two prefetching schemes. This is because the ARP and MCP can only predict user access requests that have appeared in history. When the observation window size increases gradually, prediction accuracy of the three prefetching schemes are all improved. The prediction coverage of the user access requests with different observation window size is shown in Figure 5. The prediction coverage of ARP and MCP is lower than STAP, because it cannot trigger the prediction when the user’s access request has not happened in history. At the same time, as the observation window size increases gradually, the prediction coverage of ARP and MCP decreases, while STAP remains unchanged because of its adaptability.Figure 4
Request accuracy.Figure 5
Request coverage.


#### 4.3.2. Pattern Mining and Prediction Times

Figure6 shows the time consumed for mining user access patterns from the history of user access requests. As can be seen, the time of construction decreases from 430,401 s to 21,237 s; it falls drastically as the regional meshing level increases. This is because the calculation of associate rules for the coordinate points of the entire geographic area is disaggregated to the calculation of cells and neighbor cells based on regional meshing, and partial and incremental solutions of the association rules of the location attribute are achieved.Figure 6
Patterns mining time.Figure7 shows the time for predicting 190,825 access requests with different regional meshing levels and observation window sizes. As can be seen, without meshing for the same observation window, maximum time is consumed. Then, as the meshing level increases, the time consumed decreases gradually and reaches a stable level. In contrast, for the same regional meshing level, the prediction time clearly varies with the size of the observation window. The smaller the window size, the short the prediction time. This is because, without regional meshing, the entire regional rulesets need to be scanned for matching to predict requests. However, with meshing, only the association rules belonging to the cell are to be scanned, and it is clear that the larger the window size, the longer the prediction time.Figure 7
Request prediction time.


#### 4.3.3. Average Response Time

From the abovementioned experimental results, we can see that, in the request prediction phase, although the prediction accuracy and coverage of requests decrease under the regional meshing, the time consumed for pattern mining is effectively reduced, and more importantly, regional meshing avoids the numerous calculations required for updating the location attribute. In the data prefetching phase, it is clear that the larger the length of the buffer queue, the more credible the request for the previous prediction, and the prefetching data is more accurate. However, it also means that some data of the predicted request fail to be prefetched.Therefore, to compare the average response time, we set the regional meshing asr
o
w
×
c
o
l
=
50
×
50, the initial size of the observation window as w
=
3, and the length of the buffer queue as λ
=
3 and then test the average response time for users to access a single data item of the four schemes: STAP, ARP, MCP, and nonprefetching. From Table 3, we can see that the average response time for users to access a single data item is 0.378 ms under the nonprefetching scheme. When the prefetching mechanism is employed, the average response time is reduced obviously; the proposed scheme STAP gets the minimum average response time, with a 44.71% reduction over nonprefetching mechanism.Table 3
The average response time (ms).
Nonprefetching
MCP
ARP
STAP
0.378
0.258
0.245
0.209


## 4.1. Evaluation Metrics

We propose five criteria for performance evaluation of the proposed prefetching scheme in terms of accuracy, efficiency, and effectiveness.Prediction Accuracy. It is the correct number of predicted requests as a percentage of the total number of requests.Prediction Coverage. It is the number of predicted requests as a percentage of the total number of requests.Pattern Mining Time. It is the time consumed for mining user access patterns from the history of user access requests.Request Prediction Time. It is the average time for predicting an access request.Average Response Time. It is the average response time to obtain a single data item.


## 4.2. Experimental Data and Methods

The experimental data was obtained from Wuhan smart city network application demonstration platform, which includes 14 types of sensors in different regions; it has been generating sensor data since January 1, 2010, and provides 20 types of predefined applications to the public. We obtained the historical user access information from the user access log in the server for the period from September 1, 2014, to February 16, 2015. After processing, we generated 1,819,008 data access requests. The initial 1,628,183 requests formed the training set for mining user access patterns and constructing the predictive function. The remaining 190,825 requests formed the test set for testing the performance of the prefetching scheme.The performance of the prefetching scheme is determined by the initial size of the observation window, regional meshing level, support threshold, and confidence threshold. Considering that the pattern mining is performed offline, the objective of the prediction is to choose the association rules with the maximum confidence. In order to choose the maximum number of rules and improve the trigger probability of prediction, we set thesupport threshold at 0.05% of the total number of access requests; that is, δ
p
=
δ
s
=
0.05
%, and theconfidence thresholdwas 0.01; that is, ϕ
p
=
ϕ
s
=
0.01. Experiments were conducted to determine the changes in the evaluation metrics with different initial sizes of the observation window (w
=
2, 3, 4, 5, and 6) and different regional meshing levels (r
o
w
×
c
o
l = 1 × 1, 50 × 50, 80 × 80, 100 × 100, 120 × 120, and 150 × 150), and the average response time for users to access a single data item was recorded. Finally, we compare our prefetching algorithm (STAP, spatial-temporal attributes prediction) with associate rules discovery prefetching algorithm (ARP) proposed by [5] and neighbor selection Markov Chain prefetching algorithm (MCP) proposed by [15].


## 4.3. Experimental Results

### 4.3.1. Prediction Accuracy and Coverage

(
1) Spatiotemporal Attribute Prediction(a) Location Attribute Prediction. The prediction accuracy and coverage of the location attribute with different regional meshing levels and observation window sizes are summarized in Table 1. As can be seen, for the same observation window size, when the meshing level increases (the area of the cell becomes smaller), the accuracy and coverage decrease. This is because the regional meshing results in the loss of the association rules between nonneighbor cells and leads to unsuccessful trigger prediction of some access requests. In contrast, for the same regional meshing level, as the observation window size increases, the accuracy gradually increases while the coverage remains unchanged. This can be explained as follows. On the one hand, the larger the window size, the greater the amount of available prediction information. On the other hand, the short rules form a subset of the long rules, and the current observation window cannot trigger prediction; the size of the window will adaptively decrease for further prediction until the minimum size is reached.Table 1
Location attribute prediction.
Regional meshing
Accuracy/coverage (%)
Window size
2
3
4
5
6
1 × 1
86.95/93.92
89.11/93.92
89.19/93.92
89.23/93.92
89.27/93.92
50 × 50
81.04/91.11
85.93/91.11
85.96/91.11
86.01/91.11
86.08/91.11
80 × 80
80.26/90.32
85.11/90.32
85.17/90.32
85.21/90.32
85.26/90.32
100 × 100
79.70/89.79
84.58/89.79
84.63/89.79
84.72/89.79
84.75/89.79
120 × 120
79.22/89.27
84.07/89.27
84.13/89.27
84.18/89.27
84.24/89.27
150 × 150
78.43/88.49
83.27/88.49
83.33/88.49
83.39/88.49
83.43/88.49(b) Type Attribute Prediction. The prediction of the type attribute is related only to the observation window size. As can be seen from Table 2, as the observation window size increases, the prediction accuracy gradually increases from 94.38% to 96.05%, while the prediction coverage remains unchanged at 96.76%. This can be explained as follows. The larger the observation window size, the greater the amount of available prediction information, and the adaptive observation window size achieves exactly the same prediction coverage.Table 2
Type attribute prediction.
Window size
2
3
4
5
6
Accuracy (%)
94.38
95.28
95.52
95.80
96.05
Coverage (%)
96.76
96.76
96.76
96.76
96.76(c) Time Attribute Prediction. The time attributesare predicted by the ARIMA model, because the change trend of the time attribute sequences comprises only three situations (remaining unchanged, changing periodically, and changing in step length). Furthermore, the adaptive observation window size makes the ARIMA model available for all the time attribute sequences. Therefore, the prediction errors appear only in the case of inconsistent change trends of sequence, and all requests falling within the observation windows can be predicted. The experimental results show that the prediction accuracy of the time attribute with different observation windows sizes is 88.63%, while the prediction coverage is 100%.(
2) Access Request Prediction. The final prediction request must include three basic attributes: location, time, and type. Therefore, we should synthesize the spatiotemporal attributes predicted previously to form the access request.The prediction accuracy and coverage of the user access requests with different regional meshing levels and observation window sizes are shown in Figures2 and 3. We can see that, without meshing for the same observation window size, the prediction accuracy and coverage are the highest, and as the meshing level increases, the prediction accuracy gradually decreases. This is because the regional meshing can result in the loss of association rules between nonneighbor cells and reduce the probability of triggering prediction. In contrast, at the same regional meshing level, the prediction accuracy at different observation window sizes varies slightly, except for a window size of 2, where the prediction accuracy is significantly lower. And the curves for different window sizes overlap completely. These results can be explained as follows. First, the rules mined from user access are very similar when the rule length is greater than 2. Second, when the window size w
=
2, it will fail to trigger joint property prediction. Finally, as stated before, the adaptive observation window size has no effect on the coverage.Figure 2
Request accuracy.Figure 3
Request coverage.Figures4 and 5 show the prediction accuracy and coverage of the user access of the proposed prefetching scheme STAP and another two schemes, ARP [5] and MCP [15], with different observation window sizes. Regional meshing levels were set as 50
∗
50 in the experiment, the observation window size is the active session window size in ARP, and the number of previous movements was monitored in MCP. As shown in Figure 4, the STAP achieves the highest prediction accuracy compared with the other two prefetching schemes. This is because the ARP and MCP can only predict user access requests that have appeared in history. When the observation window size increases gradually, prediction accuracy of the three prefetching schemes are all improved. The prediction coverage of the user access requests with different observation window size is shown in Figure 5. The prediction coverage of ARP and MCP is lower than STAP, because it cannot trigger the prediction when the user’s access request has not happened in history. At the same time, as the observation window size increases gradually, the prediction coverage of ARP and MCP decreases, while STAP remains unchanged because of its adaptability.Figure 4
Request accuracy.Figure 5
Request coverage.


### 4.3.2. Pattern Mining and Prediction Times

Figure6 shows the time consumed for mining user access patterns from the history of user access requests. As can be seen, the time of construction decreases from 430,401 s to 21,237 s; it falls drastically as the regional meshing level increases. This is because the calculation of associate rules for the coordinate points of the entire geographic area is disaggregated to the calculation of cells and neighbor cells based on regional meshing, and partial and incremental solutions of the association rules of the location attribute are achieved.Figure 6
Patterns mining time.Figure7 shows the time for predicting 190,825 access requests with different regional meshing levels and observation window sizes. As can be seen, without meshing for the same observation window, maximum time is consumed. Then, as the meshing level increases, the time consumed decreases gradually and reaches a stable level. In contrast, for the same regional meshing level, the prediction time clearly varies with the size of the observation window. The smaller the window size, the short the prediction time. This is because, without regional meshing, the entire regional rulesets need to be scanned for matching to predict requests. However, with meshing, only the association rules belonging to the cell are to be scanned, and it is clear that the larger the window size, the longer the prediction time.Figure 7
Request prediction time.


### 4.3.3. Average Response Time

From the abovementioned experimental results, we can see that, in the request prediction phase, although the prediction accuracy and coverage of requests decrease under the regional meshing, the time consumed for pattern mining is effectively reduced, and more importantly, regional meshing avoids the numerous calculations required for updating the location attribute. In the data prefetching phase, it is clear that the larger the length of the buffer queue, the more credible the request for the previous prediction, and the prefetching data is more accurate. However, it also means that some data of the predicted request fail to be prefetched.Therefore, to compare the average response time, we set the regional meshing asr
o
w
×
c
o
l
=
50
×
50, the initial size of the observation window as w
=
3, and the length of the buffer queue as λ
=
3 and then test the average response time for users to access a single data item of the four schemes: STAP, ARP, MCP, and nonprefetching. From Table 3, we can see that the average response time for users to access a single data item is 0.378 ms under the nonprefetching scheme. When the prefetching mechanism is employed, the average response time is reduced obviously; the proposed scheme STAP gets the minimum average response time, with a 44.71% reduction over nonprefetching mechanism.Table 3
The average response time (ms).
Nonprefetching
MCP
ARP
STAP
0.378
0.258
0.245
0.209


## 4.3.1. Prediction Accuracy and Coverage

(
1) Spatiotemporal Attribute Prediction(a) Location Attribute Prediction. The prediction accuracy and coverage of the location attribute with different regional meshing levels and observation window sizes are summarized in Table 1. As can be seen, for the same observation window size, when the meshing level increases (the area of the cell becomes smaller), the accuracy and coverage decrease. This is because the regional meshing results in the loss of the association rules between nonneighbor cells and leads to unsuccessful trigger prediction of some access requests. In contrast, for the same regional meshing level, as the observation window size increases, the accuracy gradually increases while the coverage remains unchanged. This can be explained as follows. On the one hand, the larger the window size, the greater the amount of available prediction information. On the other hand, the short rules form a subset of the long rules, and the current observation window cannot trigger prediction; the size of the window will adaptively decrease for further prediction until the minimum size is reached.Table 1
Location attribute prediction.
Regional meshing
Accuracy/coverage (%)
Window size
2
3
4
5
6
1 × 1
86.95/93.92
89.11/93.92
89.19/93.92
89.23/93.92
89.27/93.92
50 × 50
81.04/91.11
85.93/91.11
85.96/91.11
86.01/91.11
86.08/91.11
80 × 80
80.26/90.32
85.11/90.32
85.17/90.32
85.21/90.32
85.26/90.32
100 × 100
79.70/89.79
84.58/89.79
84.63/89.79
84.72/89.79
84.75/89.79
120 × 120
79.22/89.27
84.07/89.27
84.13/89.27
84.18/89.27
84.24/89.27
150 × 150
78.43/88.49
83.27/88.49
83.33/88.49
83.39/88.49
83.43/88.49(b) Type Attribute Prediction. The prediction of the type attribute is related only to the observation window size. As can be seen from Table 2, as the observation window size increases, the prediction accuracy gradually increases from 94.38% to 96.05%, while the prediction coverage remains unchanged at 96.76%. This can be explained as follows. The larger the observation window size, the greater the amount of available prediction information, and the adaptive observation window size achieves exactly the same prediction coverage.Table 2
Type attribute prediction.
Window size
2
3
4
5
6
Accuracy (%)
94.38
95.28
95.52
95.80
96.05
Coverage (%)
96.76
96.76
96.76
96.76
96.76(c) Time Attribute Prediction. The time attributesare predicted by the ARIMA model, because the change trend of the time attribute sequences comprises only three situations (remaining unchanged, changing periodically, and changing in step length). Furthermore, the adaptive observation window size makes the ARIMA model available for all the time attribute sequences. Therefore, the prediction errors appear only in the case of inconsistent change trends of sequence, and all requests falling within the observation windows can be predicted. The experimental results show that the prediction accuracy of the time attribute with different observation windows sizes is 88.63%, while the prediction coverage is 100%.(
2) Access Request Prediction. The final prediction request must include three basic attributes: location, time, and type. Therefore, we should synthesize the spatiotemporal attributes predicted previously to form the access request.The prediction accuracy and coverage of the user access requests with different regional meshing levels and observation window sizes are shown in Figures2 and 3. We can see that, without meshing for the same observation window size, the prediction accuracy and coverage are the highest, and as the meshing level increases, the prediction accuracy gradually decreases. This is because the regional meshing can result in the loss of association rules between nonneighbor cells and reduce the probability of triggering prediction. In contrast, at the same regional meshing level, the prediction accuracy at different observation window sizes varies slightly, except for a window size of 2, where the prediction accuracy is significantly lower. And the curves for different window sizes overlap completely. These results can be explained as follows. First, the rules mined from user access are very similar when the rule length is greater than 2. Second, when the window size w
=
2, it will fail to trigger joint property prediction. Finally, as stated before, the adaptive observation window size has no effect on the coverage.Figure 2
Request accuracy.Figure 3
Request coverage.Figures4 and 5 show the prediction accuracy and coverage of the user access of the proposed prefetching scheme STAP and another two schemes, ARP [5] and MCP [15], with different observation window sizes. Regional meshing levels were set as 50
∗
50 in the experiment, the observation window size is the active session window size in ARP, and the number of previous movements was monitored in MCP. As shown in Figure 4, the STAP achieves the highest prediction accuracy compared with the other two prefetching schemes. This is because the ARP and MCP can only predict user access requests that have appeared in history. When the observation window size increases gradually, prediction accuracy of the three prefetching schemes are all improved. The prediction coverage of the user access requests with different observation window size is shown in Figure 5. The prediction coverage of ARP and MCP is lower than STAP, because it cannot trigger the prediction when the user’s access request has not happened in history. At the same time, as the observation window size increases gradually, the prediction coverage of ARP and MCP decreases, while STAP remains unchanged because of its adaptability.Figure 4
Request accuracy.Figure 5
Request coverage.


## 4.3.2. Pattern Mining and Prediction Times

Figure6 shows the time consumed for mining user access patterns from the history of user access requests. As can be seen, the time of construction decreases from 430,401 s to 21,237 s; it falls drastically as the regional meshing level increases. This is because the calculation of associate rules for the coordinate points of the entire geographic area is disaggregated to the calculation of cells and neighbor cells based on regional meshing, and partial and incremental solutions of the association rules of the location attribute are achieved.Figure 6
Patterns mining time.Figure7 shows the time for predicting 190,825 access requests with different regional meshing levels and observation window sizes. As can be seen, without meshing for the same observation window, maximum time is consumed. Then, as the meshing level increases, the time consumed decreases gradually and reaches a stable level. In contrast, for the same regional meshing level, the prediction time clearly varies with the size of the observation window. The smaller the window size, the short the prediction time. This is because, without regional meshing, the entire regional rulesets need to be scanned for matching to predict requests. However, with meshing, only the association rules belonging to the cell are to be scanned, and it is clear that the larger the window size, the longer the prediction time.Figure 7
Request prediction time.


## 4.3.3. Average Response Time

From the abovementioned experimental results, we can see that, in the request prediction phase, although the prediction accuracy and coverage of requests decrease under the regional meshing, the time consumed for pattern mining is effectively reduced, and more importantly, regional meshing avoids the numerous calculations required for updating the location attribute. In the data prefetching phase, it is clear that the larger the length of the buffer queue, the more credible the request for the previous prediction, and the prefetching data is more accurate. However, it also means that some data of the predicted request fail to be prefetched.Therefore, to compare the average response time, we set the regional meshing asr
o
w
×
c
o
l
=
50
×
50, the initial size of the observation window as w
=
3, and the length of the buffer queue as λ
=
3 and then test the average response time for users to access a single data item of the four schemes: STAP, ARP, MCP, and nonprefetching. From Table 3, we can see that the average response time for users to access a single data item is 0.378 ms under the nonprefetching scheme. When the prefetching mechanism is employed, the average response time is reduced obviously; the proposed scheme STAP gets the minimum average response time, with a 44.71% reduction over nonprefetching mechanism.Table 3
The average response time (ms).
Nonprefetching
MCP
ARP
STAP
0.378
0.258
0.245
0.209


## 5. Conclusion

In this study, we exploited the spatiotemporal features of user access for spatiotemporal data in a smart city. We mapped the history of user access requests to the spatiotemporal attribute domain to perform correlation analysis and identify variation rules, mined the user access patterns, and developed a simple and efficient prefetching scheme. Specifically, the regional meshing methods use the spatial locality of user access; thus, they not only achieve partial and incremental solutions of association rules but also reduce the computation considerably. Furthermore, the ARIMA model uses the time stationarity of user access and realizes accurate prediction of the time attribute. Experimental results showed that our prefetching scheme is simple yet effective, and it can reduce the user access latency significantly.Finally, the proposed concept of access pattern mining in the spatiotemporal domain for spatiotemporal data not only has a significant effect on spatiotemporal data prefetching in a smart city but also can be widely used for user-personalized recommendation, active pushing of information, and other network applications based on location services.



---

*Source: 4127358-2016-01-21.xml*