Zheng Chang
email: zheng.chang@jyu.fi

Liqing Liu

Xijuan Guo

Tao Chen

Tapani Ristaniemi

Dynamic Resource Allocation and Computation Ooading for Edge Computing System

Keywords: Edge computing, Dynamic computation ooading, Lyapunov optimization, Resource allocation

In this work, we propose a dynamic optimization scheme for an edge computing system with multiple users, where the radio and computational resources, and ooading decisions, can be dynamically allocated with the variation of computation demands, radio channels and the computation resources. Specically, with the objective to minimize the energy consumption of the considered system, we propose a joint computation ooading, radio and computational resource allocation algorithm based on Lyapunov optimization. Through minimizing the derived upper bound of the Lyapunov drift-plus-penalty function, the main problem is divided into several sub-problems at each time slot and are addressed separately. The simulation results demonstrate the eectiveness of the proposed scheme.

Introduction

In mobile cloud computing (MCC), by ooading the computational tasks to the distant cloud for execution, the system performance, e.g., energy consumption and latency, is able to be improved [START_REF] Guerrero-Contreras | A context-aware architecture supporting service availability in mobile cloud computing[END_REF]. Among all dierent types of MCC technologies, fog/edge computing system, emerges as a proximity solution to provide pervasive and distributed computation services for the MDs, and especially for the Internet-of-Things (IoT) applications with stringent requirement of latency and reliability [START_REF] Liu | Multi-objective optimization for computation ooading in fog computing[END_REF]. In the edge computing system, as the computing capability of the edge node (EN) is not comparable to the traditional cloud center and one EN only serves a relative small area where the radio resource is also limited, the ooading decisions of the MDs may have a signicant impact on the quality of services (QoS). Accordingly, the usage of the radio resources, such as transmit power and frequency spectrum, and the harvested energy should be carefully coordinated and optimized in line with the ooading decisions. In addition, as Supported by organization x.

the radio environment and the demand for computational resources vary in a fast speed, dynamic scheduling and optimization are more preferred compared to static optimization schemes. However, due to the randomness of radio environment, harvested energy and computation demands, realizing the dynamic optimization is challenging. Therefore, in this paper, our aim is to overcome the obstacles and provide dynamic computation ooading and resource allocation schemes for edge computing system with EH devices.

Most of the researches on the ooading problem focus on designing dierent and eective static schemes for battery-powered MDs, through optimizing the MD's execution decision, radio resource, and/or computational resource [START_REF] Liu | Multi-objective optimization for computation ooading in fog computing[END_REF]- [START_REF] You | Energy-ecient resource allocation for mobile-edge computation ooading[END_REF]. Considering a edge computing system, the authors of [START_REF] Liu | Multi-objective optimization for computation ooading in fog computing[END_REF] apply queuing theory to investigate the delay, energy consumption, and payment cost (E&D&P) of ooading processes. Based on the theoretical analysis, a multi-objective optimization problem is then formulated to minimize the formulated cost functions by nding the ooading decisions and power allocation for each MD. In [START_REF] Deng | Optimal workload allocation in fog-cloud computing towards balanced delay and power consumption[END_REF], the authors explore the tradeo between delay and energy consumption in the edgecloud hybrid computing system. The associated workload allocation problem is addressed accordingly. In [START_REF] Dinh | Ooading in mobile edge computing: task allocation and computational frequency scaling[END_REF], the authors propose an optimization framework of ooading to optimize the task allocation decision and the computational resource allocation.

In this work, to address the ooading problem in edge computing, we consider dierent queue models at dierent edge computing devices to provide thorough analysis on the delay and energy consumption performance. At the MD, a M/M/1 queue is considered and at the EN, a M/G/1 queue is assumed. With the derived analytical results, we are able to formulate the system cost, which consists of service latency and energy consumption. With the objective to minimize the formulated system cost, the ooading strategy, the transmit power, and the subcarrier assignment are jointly optimized in the proposed resource allocation and ooading scheme. Due to the stochastic nature of the radio channel, the request arrival and the amount of harvesting energy, we propose to leverage the advantages of Lyapunov optimization to design an online dynamic algorithm. By minimizing the upper bound of the Lyapunov drift-plus-penalty function from the perspective of dierent decision variables, the initial problem is divided into several simple sub-problems with low-complexity and can be addressed accordingly.

System Model

We consider the system consisting of N single-core MDs, one AP, and one EN. The set of MDs is denoted as N = {1, 2, • • • , N }. Each MD generates a series of homogeneous service requests in order to execute an application. At the MD, a rst-in-rst-out (FIFO) queue is considered for storing arriving requests, and the radio interface is used for wireless connection. As a single processor is assumed, the process queue at the MD is assumed as a M/M/1 queue. The EH capability enables the MD to obtain energy supply from the environment. The harvested energy used for local task execution and data transmission. The AP is responsible for receiving requests from the MD and delivering data to the EN for further processing. The process queue of EN is modelled as a M/G/1 queue. The MD ooads (part of) the computation requests to the EN to enjoy a higher level of quality of computation experience. We assume that the time is slotted and the length of each time slot is τ . We denote the time slot set

T = {0, 1 • • • , t • • • , T -1}.

Local Execution Model

The computation requests generated by MD i, i ∈ N is assumed to follow Poisson process with an average arrival rate A i (t) and within

[A i,min , A i,max ].
Each request is of data size θ i . Note that "at time slot t" means the requests are generated at time slot "t" but executed at time slot "t + 1".

For MD i, some of the computation requests may be locally executed and the rest will be ooaded to the EN. It may also happen that when neither of these computation modes is feasible, e.g., when MD has insucient energy, and some of the computation requests have to be dropped. The decision of MD i at time slot t is modeled as a vector p i (t

) = p M i (t) , p F i (t) , p D i (t)
, where

p M i (t) + p F i (t) + p D i (t) = 1. p M i (t)
represents the portion that the requests are executed locally at time slot t, p F i (t) denotes the portion that the requests are ooaded to the EN, and p D i (t) expresses the portion that the requests are dropped.

We denote u M i as the computing capability of MD i, which depends on CPU Cycle the MD. Additionally we assume that l M i (t) denotes the normalized workload on the MD i at time slot t, which shows the occupation of CPU. For example, l M i (t) = 0 indicates at time slot t, the CPU is totally idle. When considering a M/M/1 queue with request arrival rate λ and service rate u, the response time is R = 1/u 1-ρ , where ρ = λ u [START_REF] Lazar | The throughput time delay function of an M/M/1 queue (Corresp.)[END_REF]. Then, the average response time D M i (t) for local execution of MD i at time slot t is expressed as follows:

D M i (t) = 1 u M i 1 -l M i (t) -p M i (t) A i (t)
.

(1)

Assume that the computing capability of MD

i is u M i 1 -l M i (t)
and the corresponding CPU-cycle frequency is denoted as f i (t) at time slot t. As shown in [?], under the assumption of a low CPU voltage, the power consumption of CPU is kf 3 , where k is a constant depending on the switched capacitance of MD, and f is the CPU-cycle frequency. Thus, the energy consumption

E M i (t)
of MD i for local execution can be denoted as follows:

E M i (t) =k i f 3 i (t) D M i (t) = k i f 3 i (t) u M i 1 -l M i (t) -p M i (t) A i (t) . (2)
Nevertheless, if some of the requests cannot be executed due to lack of energy, they have to be dropped. We dene a cost coecient µ i for the task drop, and accordingly the punishment cost for MD i at time slot t can be expressed as follows:

C D i (t) = µ i p D i (t) A i (t) τ.
(3)

Uplink Transmission

The wireless network is assumed to be Orthogonal Frequency Division Multiplexing (OFDM)-based. The set of the subcarrier is denoted as

K= {1, 2 • • • , k, • • • , K},
where |K| = K. The channels are assumed to be independent and identically distributed (i.i.d) block fading during time slots, i.e. the channels remain static within each time slot, but vary among dierent time slots. Let B denotes the channel bandwidth, N 0 denotes the noise power spectral density at the AP, h i,k (t) denotes the channel gain and p i,k (t) denotes the transmit power of MD i on subcarrier k at time slot t which cannot exceed its maximum value of p i,max . Dene ρ i,k (t) ∈ {0, 1} as the subcarrier assignment indicator, where ρ i,k (t) = 1 indicates that the subcarrier k is assigned to MD i at time slot t. Otherwise, ρ i,k (t) = 0. Correspondingly, the uplink data rate r i,k (t) of MD i on subcarrier k at time slot t is expressed as follows:

r i,k (t) =ρ i,k (t)Blog 2 1 + p i,k (t) h i,k (t) N 0 B . (4)
In this work, we consider one subcarrier can only be assigned to one MD to avoid transmission interference, while one MD can be assigned several subcarriers. The total uplink data rate for MD i at time slot t is denoted as follows:

R i (t) = k∈K ρ i,k (t) Blog 2 1 + p i,k (t) h i,k (t) N 0 B . (5)
Correspondingly, we can obtain the uplink transmission time D up i (t), as follows:

D up i (t) = p F i (t) Ai (t) θiτ k∈K ρ i,k (t) Blog 2 1 + p i,k (t)h i,k (t) N 0 B . (6)
Then the energy consumption E up i (t) of the uplink transmission can be given as follows:

E up i (t) = k∈K ρ i,k (t) p i,k (t) p F i (t) A i (t) θ i τ k∈K ρ i,k (t) Blog 2 1 + p i,k (t)h i,k (t) N0B . ( 7
)

Fog Execution Model

The EN connecting to the AP can process the ooaded requests and execute the computation task. We consider the connection between the EN and AP is ber-based with large enough bandwidth and the transmission time from the AP to EN is ignored. We denote the service rate of the EN as u F . The pending requests of the MDs are pooled together with a total rate A total (t) which also follows the Poisson process. Therefore, A total (t) is given as follows:

A total (t) = i∈N p F i (t) A i (t). (8)
We denote the workload of the EN as l F (t), which presents the occupied percentage of each server and l F (t) < 1. As a M/G/1 queue is considered at the EN , the average response time D F (t) is given as follows [START_REF] Machol | Queue theory[END_REF]:

D F (t) = 2u F 1 -l F (t) - i∈N Ai (t) p F i (t) 2u F (1 -l F (t)) u F (1 -l F (t)) - i∈N Ai (t) p F i (t) . (9)

Energy Harvesting Model

To model the energy harvesting, a successive energy packet arrival model is considered. The arrival of energy packet follows a Poisson process with an average arrival rate e i (t), and 0 < e i (t) ≤ e max i (t) where e max i (t) is the maximum energy arrival rate in each time slot. The harvested energy is stored in the battery and will be available for further actions. We denote the battery energy level of MD i at the beginning of time slot t as B i (t). In this work, energy consumed for purposes other than local computation and transmission is ignored for simplicity. The energy consumption E i,total (t) of MD i consists of two parts:

E i,total (t) = E M i (t) + E up i (t) . ( 10
)
where E M i (t) is the energy consumption for local processing and E up i (t) is energy consumption for delivering the requests. Note that E i,total (t) should be smaller than the battery level, i.e., E i,total (t) ≤ B i (t). Thus, the battery level of MD i evolves as follows,

B i (t + 1) = B i (t) -E i,total (t) + e i (t) .
(11)

Problem Formulation

The execution cost consists of the execution delay and the task dropping punishment cost. The execution delay D i (t) at time slot t is derived as follows:

D i (t) = p M i (t) D M i (t) + p F i (t) D up i (t) + D F (t) . (12)
Consequently, the execution cost for MD i can be formulated as follows:

EC i (t) = D i (t) + α i C D i (t) , (13)
where α i is the weight of task dropping cost. The total weighted execution cost of the system at time slot t is denoted as Γ total (t), which is given as

Γ total (t) = i∈N ωi p M i (t) D M i (t) + p F i (t) D up i (t) + D F (t) + αiC D i (t) , (14)
where ω i is the weight factor, which reects the relative importance of MD i.

Then we derive the average execution cost Φ (t) of the edge computing system during T time slots, which is given in (15).

Φ (t) = lim T →+∞ 1 T t∈T W EC total (t) = lim T →+∞ 1 T t∈T i∈N ωi p M i (t) D M i (t) + p F i (t) D up i (t) + D F (t) + αiC D i (t) . ( 15
)
We denote the system decision at time slot t as V(t) = p(t), ρ(t), p up (t) , ∀t ∈ T , where p

(t) = [p 1 (t), • • • , p i (t), • • • p N (t)]
are execution strategies for all the MDs at time slot t and p i (t

) = p M i (t), p F i (t), p D i (t) is the execution strategy for MD i at time slot t. ρ(t)= [ρ 1 (t), • • • , ρ i (t), • • • , ρ N (t)]
is the subcarrier assignment matrix for all MDs at time slot t and ρ

i (t)= [ρ i,1 (t), • • • , ρ i,k (t), • • • , ρ i,K (t)]
is the subcarrier assignment vector for MD i at time slot t.

p up (t) = [p 1 (t), • • • , p N (t)]
is the uplink transmit power matrix for all the MDs at time slot t and p

i (t)= [p i,1 (t), • • • , p i,K (t)]
is the set of transmit power for MD i. Thus, the problem can be formulated as shown in P1, which is P1 : min

V (t) Φ (t) , (16) s
.t. p M i (t) +p F i (t) +p D i (t) =1, 0 ≤ p M i (t) , p F i (t) , p D i (t) ≤ 1; (17a)
p M i (t) A i (t) -u M i 1 -l M i (t) < 0; (17b) i∈N p F i (t)A i (t) -u F 1 -l F (t) < 0; (17c) 0 < p i,k (t) < p i,max ; (17d) i∈N ρ i,k (t) ≤ 1, ρ i,k ∈ {0, 1} ; (17e)
E i,total (t) ≤ B i (t) ; (17f) i ∈ N , t ∈ T , k ∈ K. (17g)
As we can see, the MDs' decisions are coupled among dierent time slots due to the constraints (17f), which makes the problem dicult to be tackled. As presented in [START_REF] Mao | Dynamic computation ooading for mobileedge computing with energy harvesting devices[END_REF], by introducing a reasonable upper bound E max i (t) and a nonnegative lower bound E min i (t) of the battery, the coupling eect is eliminated. Correspondingly, the system operation can be optimized by ignoring (17f). Thus, the problem can be modied as follows: P1 : min

V (t) Φ (t) (17a) -(17e), (17g) ( 18
) E i,total (t) ∈ E min i (t) , E max i (t) (19)
For simplify, we consider E min i (t) = 0. For P1, a stochastic optimization problem is formulated with decision variables of the execution strategy, the uplink transmit power and the subcarrier assignment. By addressing the deterministic per-time slot problem, we can obtain the total optimal decisions in a stochastic manner.

Proposed Solution

Lyapunov optimization is an ecient framework for designing online control algorithm without requiring any prior knowledge [START_REF] Mao | Dynamic computation ooading for mobileedge computing with energy harvesting devices[END_REF]. In order to present the proposed solution, we rstly dene the Lyapunov function as follows:

L (B (t)) = 1 2 i∈N B i 2 (t), (20)
where

B(t)= [B 1 (t), • • • , B i (t), • • • B N (t)].
Thus, the conditional Lyapunov drift can be expressed as

∆ (B (t)) =E [L (B (t + 1)) -L (B (t)) |B (t) ] . ( 21
)
The Lyapunov drift-plus-penalty function can be given as follows:

∆ V (B (t)) = ∆ (B (t)) + V E [Γ total (t) |B (t) ] , (22)
where V ∈ (0, +∞) is a control parameter. Then we will nd an upper bound of ∆ (B (t)) under any feasible set of V (t), which can be found in the following lemma. lemma 1. For any feasible set of V (t), which satises ( 18) and ( 19), the Lyapunov drift-plus-penalty function ∆ V (B (t)) is upper bounded, i.e.,

∆ V (B (t)) ≤ κ + i∈N {B i (t) [e i (t) -E i,total (t)]} + V E [Γ total (t) |B (t) ] , ( 23
)
where κ is a constant, which is denoted as Algorithm 1 Proposed online algorithm

Step 1: at the beginning of the time slot t, obtain B (t).

Step 2: through solving the problem P2, determine the system decision set V (t) = p (t) , ρ (t) , p up (t) , to minimize the P2. min (

V (t) i∈N {Bi (t) [ei (t) -E i,total (t)]} + V E [Γ total (t
) 24
Due to the space limitation, we omit the proof here. The key idea of the proposed algorithm is to minimize the upper bound of ∆ V (B (t)) in the righthand side of (23). The proposed algorithm is displayed in Algorithm 1.

Due to the high complexity of the the considered problem, in the next section, we will divide it into several sub-problems to obtain the optimal system decision.

Optimal Execution Strategy

Firstly, we seek the optimal execution strategy at each time slot t, while taking the other pending variables as constants, then the problem is translated into the following sub-problem SP1, which is denoted as follows:

min p(t) i∈N -B i (t) E i,total (t) + V i∈N ω i D i (t) + α i C D i (t) (25) s.t.
(17a) -(17g), (17g), (19) It can be found that (17c) is a coupled constraint, which includes various decision variables of dierent MDs. Similarly to the ones in [START_REF] Liu | Socially-aware dynamic computation ooading scheme for fog computing system with energy harvesting devices[END_REF], we can formulate the proposed problem as a Generalized Nash Equilibrium Problem (GNEP). The exponential penalty function method is applied to transform the original GNEP into a classical NEP and address it by semi-smooth Newton method with Armijo line search.

Optimal Power Allocation and Subcarrier Assignment

Similarly, the optimal transmit power p up (t) and subcarrier assignment matrix ρ(t) can be obtained by solving the following sub-problem SP2 through removing some irrelevant parameters from P2, which is denoted as follows:

min {ρ(t),p(t)} i∈N -B i (t) E up i (t) + V i∈N ω i p F i (t) D up i (t) , (26) s
.t. 0 < p i,k (t) < p i,max , (27a)
i∈N ρ i,k (t) ≤ 1, ρ i,k ∈ {0, 1} , (27b)
E up i (t) < E max i (t) , (27c)
i ∈ N , k ∈ K.

(27d) By substituting the specic expressions of E up i (t) and D up i (t) into the above problem, we can get an equal form of SP2, as shown in SP2'. The constraints are the same as those in (27). We can nd that the SP2' is a mixed-integer programming problem, which involves the joint optimization of both continuous variables p i,k (t) and integer variables ρ i,k (t). Next, we will propose an algorithm to solve the problem. Firstly, we introduce an average ooading priority function [START_REF] You | Energy-ecient resource allocation for mobile-edge computation ooading[END_REF], and it is dened as follows: SP2' : min

{ρ(t),p(t)} i∈N -Bi (t) k∈K ρ i,k (t) p i,k (t) p F i (t) Ai (t) θiτ k∈K ρ i,k (t) Blog 2 1 + p i,k (t)h i,k (t) N 0 B + V i∈N ωip F i (t)     p F i (t) Ai (t) θiτ k∈K ρ i,k (t) Blog 2 1 + p i,k (t)h i,k (t) N 0 B     (28)
ψ i,k,t (ω i , τ, h i,k (t)) = ωiN0B h i,k (t) [v i (t) ln v i (t) -v i (t) + 1] , v i (t) ≥ 1, 0, v i (t) < 1, (29)
where the constant v i (t) is dened as

v i (t) = Bh i,k (t)τ c0 N0 ln 2
and c 0 is a predened constant. Specically, with the dened average ooading priority function ψ i,k,t (ω i , τ, h i,k (t)) (for simplify, we assume that any two values of ψ i,k,t (ω i , τ, h i,k (t)) are not the same), we denote the ooading priority order as Ψ (t) at time slot t, which is composed by {ψ i,k,t } , i ∈ N , k ∈ K, and displayed in the descending manner. We denote the sets of assigned and unassigned subcarriers as K 1 (t) and K 2 (t) at the beginning of time slot t. The average channel gain hi (t) is dened

as hi (t) = k∈K 2 (t) h i,k (t) |K2(t)|
, where |K 2 (t)| is the number of unassigned subcarriers during the time slot t. For each MD, such as MD i, the assigned subcarrier set is denoted as Z i (t) during the time slot t, initialized as Z i (t) =∅. Additionally, the subcarrier assignment indicators are set as {ρ i,k (t) = 0} at the beginning of time slot t. By these denitions, we proposed a subcarrier allocation algorithm, which is displayed in Algorithm 2.

In the proposed algorithm, we need to nd the optimal power allocation, which involves addressing the following SP2 , which is

Z i (t) = Z i (t) ∪ {k },K1 (t) = K1 (t) ∪ {k }, K2 (t) = K2 (t) \ {k }; (3) if |Z i (t)| = ñ * i (t
{n i (t), pi (t)} i∈N -Bi (t) pi (t) p F i (t) Ai (t) θiτ Blog 2 1 + pi (t) hi (t) N 0 B + V ωi p F i (t) 2 Ai (t) θiτ ni (t) Blog 2 1 + pi (t) hi (t) N 0 B , (30) s.t.
i∈N

n i (t) ≤ |K 2 (t)| , ( 31a
) pi (t) ≤ p i,max , (31b) pi
(t) p F i (t) A i (t) θ i τ Blog 2 1 + pi(t) hi(t) N0B ≤ E max i (t) , (31c)
where n i (t) is the total integer number of subcarriers that allocated to MD i at time slot t. We can also nd that SP2'' is a mixed integer programming including a coupled constraint (31a). Thus, we can address it with semi-smooth Newton method, which is similar with [START_REF] Liu | Socially-aware dynamic computation ooading scheme for fog computing system with energy harvesting devices[END_REF]. Then with the branch-and-bound procedure, we can obtain the integer solution n * i (t).

We denote the set of MDs that still require subcarriers as Ñ , where Ñ = {i |n * i (t) > 0 }.

We allocate subcarriers for each MD with the highest ooading priority principle. After searching for the highest ooading priority ψ i ,k ,t over unassigned subcarriers K 2 (t) for the remaining ooading-required users Ñ and then allocates subcarrier k to user i . Such a sequential subcarrier assignment follows the descending ooading priority order. Then the remaining sets can be updated until all subcarriers are assigned. At last, the optimal transmit power for MD i

i,k (t),k ∈Z i (t) k ∈Z i (t) -Bi (t) p i,k (t) p F i (t) Ai (t) θiτ k ∈Z i (t) Blog 2 1 + p i,k (t)h i,k (t) N 0 B + V ωi p F i (t) 2 Ai (t) θiτ k ∈Z i (t) Blog 2 1 + p i,k (t)h i,k (t) N 0 B , (32)
s.t.

0 < p i,k (t) ≤ p i,max , k ∈ Z i (t), (33a)
k ∈Zi(t)

p i,k (t) p F i (t) A i (t) θ i τ k ∈Zi(t) Blog 2 1 + p i,k (t)h i,k (t) N0B ≤ E max i (t) , (33b)
We can see that the formulated problem SP2 ' is similar with the problem investigated in [START_REF] Liu | Multi-objective optimization for computation ooading in fog computing[END_REF]. Then, we can solve it with Interior Point Method (IPM), the details of which can be found in [START_REF] Liu | Multi-objective optimization for computation ooading in fog computing[END_REF].

Performance Evaluations

In this section, extensive simulations are conducted to illustrate the eectiveness of the proposed algorithm. The simulation parameters are similar to the one used in [START_REF] Liu | Multi-objective optimization for computation ooading in fog computing[END_REF] and [START_REF] Liu | Socially-aware dynamic computation ooading scheme for fog computing system with energy harvesting devices[END_REF]. First, we illustrate the relationship of the average execution cost of the system versus the number of subcarriers with 6 MDs in Fig. 1. It can be observed that with the optimal subcarrier allocation strategy, the average execution cost of the system is the smallest among all three schemes. Moreover, as shown in this gure, with the increasing of the number of subcarriers, the average execution cost becomes smaller, as the MDs have sucient choices to ooad the requests to the EN to reduce the execution delay. In this way, the dropped requests would also be reduced.

Then we show the total execution cost of the system versus the number of MDs in the system when the number of subcarriers is xed in Fig. 2. It can be Fig. 2. The eect of the number of MDs observed that the average execution costs are increasing when the number of MDs increases, which means that the execution delay or the punishment cost become larger under the condition of xed number of subcarriers. As more and more users compete for the radio and computational resources with each other, longer transmission time and fog execution delay can be induced. Thus, the MDs have to execute more requests locally or drop them, which leads to a larger execution cost.

conclusion

In this paper, we propose a dynamic optimization scheme for an edge computing system with multiple users, where the radio and computational resources, and ooading decisions, can be dynamically allocated with the variation of computation demands, radio channels and the computation resources. Specically, with the objective to minimize the energy consumption of the considered system, we propose a joint computation ooading, radio and computational resource allocation algorithm based on Lyapunov optimization. Through minimizing the derived upper bound of the Lyapunov drift-plus-penalty function, the main problem is divided into several sub-problems at each time slot and are addressed separately. The simulation results demonstrate the eectiveness of the proposed scheme.

Fig. 1 .

 1 Fig. 1. The eect of subcarrier allocation

  p

  Step 3: set t = t + 1, update B (t) , repeat Step 1 and Step 2, until obtain the system decisions of all the time slots.

					) |B (t)|]
	s.t. (18), (19)
	κ =	(e max i	(t))	2 + (E max i	(t))
	i∈N

2

2

.

  Let ρ k ,n = 1, where {i , k } = arg max

	Algorithm 2 Subcarrier allocation algorithm
	1: Input: At beginning of time slot t, obtain Ψ (t), h i,k (t),K1 (t), K2 (t), and hi (t);
	2: Obtain the total integer number of subcarriers:
	Solving the optimal solution {n * i (t) , p * i (t)} of the SP2'';
	3: Subcarrier allocation: 4: while Ñ = ∅, do
	5: (1) i ∈N,k ∈K	ψ i,k,t ;
	(2) Update sets:


Agorakis Bompotas
email: mpompotas@ceid.upatras.gr

Aristidis Ilias

Andreas Kanavos
email: kanavos@ceid.upatras.gr

Christos Makris
email: makri@ceid.upatras.gr

Gerasimos Rompolas
email: robolas@ceid.upatras.gr

Alkiviadis Savvopoulos

A Sentiment-based Hotel Review Summarization using Machine Learning Techniques

Keywords: Classification, Machine Learning, Neural Networks, Opinion Mining, Sentiment Analysis

With the advent of social media, there is a data abundance so that analytics can be reliably designed for ultimately providing valuable information towards a given product or service. In this paper, we examine the problem of classifying hotel critiques using views expressed in users' reviews. There is a massive development of opinions and reviews on the web, which invariably include assessments of products and services, and beliefs about events and persons. In this study, we aim to face the problem of the forever increasing amount of opinionated data that is published in a variety of data sources. The intuition is the extraction of meaningful services despite the lack of sufficient existing architectures. Another important aspect that needs to be taken into consideration when dealing with brand monitoring, relates to the rapid heterogeneous data processing, which is vital to be implemented in real-time in order for the business to react in a more immediate way.

Introduction

In the emergent field of Web 2.0, users reviews, comments and reports have constituted a crucial area of interest for tourism businesses. As an escalating number of consumers are inclined to share as well as exchange their personal experiences in social networks, forums and websites, the tourism industry has radically altered the way of increasing and influencing customers engagement with tourism brands [START_REF] Harrigan | Customer engagement with tourism social media[END_REF]. In this new era of e-tourism, businesses, in order to keep up with the upsurging competition, have to develop innovative marketing strategies and techniques focused on customers needs and satisfaction. Subsequently, in the last years, there has been a wide interest in extracting actionable insights on customers behaviour and sentiment by leveraging user-generated content, that will enable businesses to identify and in following predict the usefulness of online reviews [START_REF] Gavilan | The influence of online ratings and reviews on hotel booking consideration[END_REF].

The widespread use of social media platforms has significantly contributed to the growth of the electronic word-of-mouth (eWOM) communication, which has notable impact on the tourism industry. This textual kind of communication is encapsulated in online reviews and has attracted researchers' interest in various domains. In particular, text and opinion mining systems have been proposed in the literature in order to analyse and classify customers reviews, providing thus businesses with the capability of monitoring their online brand reputation [START_REF] Kasper | Sentiment analysis for hotel reviews[END_REF][START_REF] Sun | Exploring ewom in online customer reviews: Sentiment analysis at a fine-grained level[END_REF]. Moreover, due to the large volume of user-generated data, text summarization techniques have also been proposed in order to effectively and efficiently identify the top-k most informative sentences of hotel reviews [START_REF] Hu | Opinion mining from online hotel reviews -A text summarization approach[END_REF].

In general, despite the textual information, reviews consist of a score rating mechanism, which can reflect the overall customer satisfaction in a very explicit way. Although customers ratings have been found to be highly correlated with the sentiment polarity of the corresponding textual content of the reviews [START_REF] Geetha | Relationship between customer sentiment and online customer ratings for hotels -an empirical analysis[END_REF], there is still a strong interest in further examining and evaluating the textual content under specific technical attributes, which can influence customer ratings [START_REF] Zhao | Predicting overall customer satisfaction: Big data evidence from hotel online textual reviews[END_REF]. In any case, it is obvious that customers reviews are a vital source of information for the tourism industry, as they enable businesses to have a clear view of the most important aspects deriving from them and thus they can better prioritize and optimize their marketing strategies.

The vast amount of user-generated content has led to the need of NoSQL databases in order to manipulate them in a scalable and productive way [START_REF] Vonitsanos | A nosql database approach for modeling heterogeneous and semi-structured information[END_REF]. Therefore, in this paper, a NoSQL system with an automated tool that generates an intelligent mechanism for analysing data and exporting useful knowledge and insights to tourism traders, is proposed. As a result, businesses will be able to adjust their marketing strategies and adapt to the customer needs in time, and simultaneously reducing their human resource requirements.

The contribution of this work lies in the design of a new approach for analyzing hotel reviews using Latent Dirichlet Allocation (LDA) for aspect mining and Neural Networks (NN) for sentiment analysis. A dynamic architecture, which receives the data stream, on-line or off-line in order not to overload the systems of the participating hotels or their service providers, is proposed. It extracts the aspects along with the sentiment of the hotel reviewers by applying LDA and NN modules accordingly, then stores the data and finally, attempts to correlate the data with the reviewers. The process is not obvious, given the anonymity of the reviewers, but the attempt to correlate them can be implemented with extensive training of the NN. Our architecture proposes a novel platform utilizing the benefits of both algorithms, so that it can be used in an effective way in data forecasting.

The paper is organized as follows. Section 2 describes related work. The key design ideas and concepts of the architecture of the proposed Sentiment Analysis system are presented in Section 3. In Section 4 we present implementation details regarding the system infrastructure, while in Section 5 we provide our conclusions and thoughts relating to future work.

Related Work

Due to the growing available data that are generated on a daily basis from hotels worldwide, a turn of attention has been observed in academic literature in adopting new ways of managing the insightful hotel data, and extrapolate important and valuable information, which can later be used for sustainable economic growth. The nature of most of these data are mainly in the form of text, accompanied by a certain numerical grading. These two characteristics constitute a modern review regarding the user's accommodation. Such reviews contain in their main body the reviewer's opinion of the hotel as well as a grade that indicates the polarity or the sentiment towards the accommodation, and wholly characterizes the experience itself.

In [START_REF] Kasper | Sentiment analysis for hotel reviews[END_REF], an overview of a review management tool is shown where a variety of hotel comments were collected, in order to hark the visitors' points and views of the hotel quality. At the same point, the work presented in [START_REF] Hu | Mining opinion features in customer reviews[END_REF] introduces a more general and non context-specific approach for opinion mining, based on customer reviews. More specifically, authors performed a summarizing of the numerous comments and reviews regarding particular products, and in following extracted a comprehensive polarity percentage that represents the sentiment of the buyers as a whole. Altogether, the sentiment of a review as well as the general sentiment that hotel reviews accumulate, can produce a meaningful abstraction and pinpoint either problems that the management can solve or aid potential customers in choosing their next hotel [START_REF] Liu | A survey of opinion mining and sentiment analysis[END_REF].

Social media compose platforms that welcome a vast amount of product and service reviews, which have an unbeatable advantage over classic comments under the designated product; more to the point, the graph representation and the links between reviews can provide deeper latent connections between sentiment and review. One such corresponding work has been implemented in [START_REF] Kanavos | Emotional community detection in social networks[END_REF], where authors demonstrated numerous academic researches that concentrate on consequential sentiment analysis through the scope of social media. Coauthoring an extension of their previous work, authors in [START_REF] Kanavos | Large scale implementations for twitter sentiment classification[END_REF] also showed the scalability of their methodologies, where massive collections of review data were processed with the aid of distributed computing frameworks, while maintaining robustness in terms of velocity of processing and accuracy of sentiment prediction.

However, the process of analyzing the sentiment in general and in retrospect, the sentiment polarity of reviews is not straightly performed into the raw collected data. A number of pre-processing layers must be beforehand executed so in the work presented in [START_REF] Haddi | The role of text pre-processing in sentiment analysis[END_REF], this importance is greatly highlighted. Before advancing to the classification and performance evaluation steps, two important layers take place; data transformation and filtering. Data were cleaned and stripped of useless tags, and in following, stemming and lemmatization procedures occurred. During the filtering step, a statistical analysis to measure the dependency between word and category that the word is included, was performed with the aid of the Chi-square test. As shown in the performance evaluation step, all measurements were improved when considering the pre-processing procedure in comparison to completely avoiding that step, in terms of the three basic evaluation metrics, namely F 1-measure, accuracy and recall.

As a result, the review management is immediately dependent on the aforementioned nature of the reviews, which is none other than a text collection. Thus, the branch of text mining as a tool to aid this process is deemed essential. There has been much academic literature throughout the latest decades regarding text mining and opinion mining techniques, either of probabilistic nature or not [START_REF] Blei | Probabilistic topic models[END_REF][START_REF] García | Data Preprocessing in Data Mining[END_REF]. As a previous work on opinion clustering emerging in reviews, one can consider the setup presented in [START_REF] Gourgaris | Review-based entity-ranking refinement[END_REF]. Other existing works that deal with customers' buying habits is presented in [START_REF] Iakovou | Customer behaviour analysis for recommendation of supermarket ware[END_REF][START_REF] Kanavos | Large scale product recommendation of supermarket ware based on customer behaviour analysis[END_REF] The machine learning algorithms have the advantage of dealing with high dimensional and nonlinear relationships, which is especially suitable for establishing train dynamic model and train speed prediction on account of the dynamic and nonlinear nature [START_REF] Savvopoulos | LSTM accelerator for convolutional object identification[END_REF]. One of the most classic text mining techniques that composed the foundation for modern opinion mining is the Latent Dirichlet Allocation (LDA) [START_REF] Blei | Latent dirichlet allocation[END_REF][START_REF] Griffiths | Gibbs sampling in the generative model of latent dirichlet allocation[END_REF][START_REF] Griffiths | Finding scientific topics[END_REF]. LDA is a probabilistic algorithm that can discover the latent topics that may exist within the reviews of the collection. More specifically, LDA extracts the top N topics that are most common in a review, based on the representations of the most frequent words with the input being a term document matrix, whereas two distributions are considered as output; one for document-topic relations and the other for topic-word ones.

System Architecture

In this section, we will elaborate on the key design ideas and concepts regarding the architecture of the proposed Sentiment Analysis platform. As depicted in Figure 1, our system consists of an Application Programming Interface (API) that serves as the gateway to an online hotel booking platform (or a channel manager), a NoSQL database and the Sentiment Analysis Infrastructure which in turn is divided into five different modules.

The flow of data within the system is relatively simple. Initially, hotel reviews are inserted in the database through the corresponding API, where they become available to the Sentiment Analysis Infrastructure. The Natural Language Processing module initially parses the stored reviews, transforms them into the appropriate form and eventually passes them to the Aspect Mining and Sentiment Analysis modules. Subsequently, the intermediate results are given as input to the Results Combiner module, which produces the final outputs and stores them back to the database. Finally, both the initial reviews and the results of the analysis are easily accessible through the API.

Hotel Reviews Sentiment Analysis API

For exposing the Sentiment Analysis Infrastructure to the systems that will access it, a RESTful web service was implemented. Concretely, it supports both GET and POST requests and the data exchanged over the API are expected to Fig. 1. Hotel Reviews Sentiment Analysis Platform Architecture be in the form of JavaScript Object Notation (JSON). The API allows the user to insert new hotel reviews to the system and update or simply retrieve information about the old ones. The aforementioned functionality can be extended as well to the authors of the reviews. The access to the API is restricted and an authentication method is utilized for avoiding illwanted visiting. Regarding the API implementation, Python programming language in combination with the popular Flask microframework were selected, because of their lightweight and powerful properties.

Storage

For storing the hotel reviews along with the intermediate and final results produced by the Sentiment Analysis Infrastructure, a fast but flexible database system was required. Furthermore, the risk that the number of reviews can grow exponentially created the additional need for scale-out, which dictated us to swift away from the traditional RDBMs and to seek a NoSQL alternative. As no join operations were compulsory for our analysis, a document-based database was deemed as the best suited solution. More specifically, we opted to use the MongoDB, because of its maturity level along with the robustness it provides.

Sentiment Analysis Infrastructure

Natural Language Processing Module

The first module of the Sentiment Analyzer is responsible for processing the raw text of the hotel reviews with the aim of producing the vectors that will be used as input for the next modules. This process, which is also known as feature extraction, can be further analyzed into four separate stages: Sentence Splitting, Tokenization, Stopwords Removal and Tf/Idf Calculation.

In most cases, the importance of a review content is condensed within the first few sentences of a text. Therefore, tokenization of sentences is deemed as crucial, as well as extracting the sentences where the necessary information resides. Often, a simple split of the text string on every dot will suffice. However, there are many cases in the English language, where the period punctuation is used for reasons other than ending a sentence such as timestamp depiction (a.m., p.m.). That is why the sentence splitting module must be context-aware.

Regarding the tokenization of the text body, the first step is splitting the sentence into separate words by using the space string to perform the splitting. These words are generally referred to as tokens, which is no other than a sequence of characters grouped together to form a semantic unit. However, not all terms or units are useful for the final analysis, since there are words that are deemed trivial or others that contribute to the general context far more heavily.

A useful technique to apply to the extracted tokens is the stemming and lemmatization technique. Many words contained in the same document correlate, since they belong to similar derivational families and have similar meanings. Thus, it is deemed useful to extract a general lemma that applies to all words with similar prefixes, and remove the corresponding suffix. This procedure allows any Natural Processing Module to work faster, since it handles exceptionally less words in a smaller vocabulary, without sacrificing any percentage of context or meaningful information.

After the application of the above mentioned procedures, Tf/Idf weighting can be performed. There the term frequency definition is combined with the inverse document frequency, in order to produce a specific weight for every word that exists inside each document. This assigned weight takes higher values when the terms occur many times inside a few documents, and lower when the term occurs less times in a document or generally occurs in various documents. When the word exists in every document, it is deemed borderline meaningless.

Each stage is assigned to a sub-module designed and developed specifically for the corresponding task. In addition, these sub-modules are connected in order to form a pipeline that receives as input the collection of the reviews and produces the final vectors.

Aspect Mining Module

The Aspect Mining Module aims to detect the aspect where each sentence of the review refers to. In order to achieve this goal, both a supervised and an unsupervised learning approach are employed. Initially, each sentence is labeled by a Multiclass Classifier. The aspects are simply considered as the predefined labels, which are commonly found in hotel reviews (e.g., cleanliness, facilities, etc.) with the addition of an "undefined" class. However, some extra analysis is required in order to discover potential aspects that were omitted. This analysis is performed by the second submodule of the Aspect Mining Module, which employs Latent Dirichlet Allocation (LDA). LDA is considered a generative probabilistic model of a collection of composites, made up of parts. It is designed based on the idea that each document in a collection can be described by a distribution of topics and simultaneously, each topic can be described by a distribution of words. In our scenario, where hotel reviews are in place of documents and the aim is to discover the aspects that characterize them, it is evident why LDA constitutes a perfect fit to our problem.

Sentiment Analysis Module

In the proposed system, there are two Sentiment Analysis Modules; the first one characterizes the whole review based on the polarity of the sentiment that expresses, while the second one attempts to do the same but for every aspect mentioned. The sentiments are both detected with the use of predefined rule-based sentiment annotators as well as machine learning models. The output of these modules constitutes a vector of sentiment scores that are then passed to the Results Combiner Module.

Regarding the training of the aforementioned models, a number of classifiers was employed and the Long Short Term Memory Neural Networks (LSTMs) emerged as the most efficient solution. Compared to the standard Neural Networks, which only allow information flowing forward from the input nodes to the output nodes, LSTMs are equipped with feedback connections. More to the point, based on this feature, LSTMs are able to effectively handle entire sequences of data and are best suited in fields such as speech recognition and text processing. Furthermore, LSTMs use "exploit" for regulating the flow of data within their cells in order to deal with the exploding and vanishing gradient problems that are the most common shortcomings of the traditional Recurrent Neural Networks (RNN).

Results Combiner Module

As derived from its name, the Results Combiner Module gathers the information about the extracted sentiment of reviews by the previous modules and attempts to produce an insight useful to the end user. It consists of two different sub-modules; the first one calculates a score of the review in order to quantify the overall customer satisfaction, whereas the second one issues warnings that might help the hoteliers to understand their shortcomings.

Implementation

The functionality of each aforementioned module is widely enhanced through the advancements of machine learning algorithms, whereas their efficiency, robustness and velocity of training have been proved throughout the scientific literature of the last decade. In this experimental work, the detection of the sentiment in each hotel review, as well as their polarity related to aspects that pertain them, is made feasible with the use of the following algorithms.

Long Short Term Memory (LSTM) Neural Networks

Neural Networks' capability has made possible the successful supervised training of classifiers on collections of data big enough; this training can ensure a wide captivation of patterns in the corresponding dataset. Given well structured data, the Long Short Term Memory Neural Networks (LSTM) can provide consequential classifications, especially when sequences must be managed. The case at hand can be directly associated with sequences since hotel review collections consist of text data, whilst their labels are the polarized sentiments of the document that need to be detected.

LSTMs' architecture is based on "cell state" and "gates" through which the input information is propagated. More accurately, there are three gates and two states in LSTMs: the forget gate (f t ) whose responsibility is to remove unnecessary information from the cell state taking as input the hidden state of the previous cell h t-1 and data record x t . Next, the input gate (i t ) adds new information on the cell state by creating a vector of all possible values and multiplying them with the tanh function. In following, the output gate (o t ) transfers a percentage of information to the hidden state, so that the LSTM can maintain its robustness by preserving the long-term dependencies. Finally, regarding the two states, the cell state (c t ) represents the internal memory of the cell and the hidden state (h t ) decides the time frame of the recalled dependency. These characteristics are presented in the following Equation 1.

f t = σ(W f (x t + h t-1 ) + b f ) i t = σ(W i (x t + h t-1 ) + b i ) o t = σ(W o (x t + h t-1 ) + b o ) c t = f t c t-1 + i t σ(W c (x t + h t-1 ) + b c ) h t = o t tanh(c t ) (1)

Latent Dirichlet Allocation (LDA)

The fundamental functionality of Latent Dirichlet Allocation (LDA) resides in the idea that each document has a number of words (terms as a subset of the total word collection), which are partially involved in the said document as well as a number of topics, which are elaborated in this document. The detection of topics that the document consists of as well as the correlation of its words with those topics, can be considered as the utmost goal of LDA.

In this work, the hotel reviews can be seen as documents, whereas the aspects as topics, which the review is meant to analyze. LDA will parse each document and allocate each review word to a specific topic through a parameterized Dirichlet allocation, allowing thus a degree of initial randomness. Afterward, two calculations are performed: initially the number of words in the review that were assigned a specific topic divided by the number of words in any topic, as well as the percentage of allocations given a topic that were derived through a given word.

As a result, the probability of a word belonging to a topic is updated by the multiplication of the two aforementioned values. The re-assignment of documents to words and topics takes place until convergence and a stable mixture of topics are produced.

Conclusions and Future Work

The aim of the current study is the design of a new schema based on NoSQL databases for the manipulation of hotel reviewers' comments along with the appropriate modules based on LDA in terms of aspect mining as well as Neural Networks for hotel reviewers' sentiment. In this schema, the data stream is initially received, then the aspects along with the sentiment of the hotel reviewers are extracted and finally, the data with the reviewers are correlated. We proposed a novel architecture utilizing the benefits of Neural Networks along with LDA algorithm so that it can be used in an effective way in data forecasting.

For further work, we would like to compare the effectiveness of our architecture in larger sample. In addition, new classifiers can be considered in order to be compared with the current ones, such as Random Forest, Support Vector Machines, etc.

Acknowledgement

Agorakis Bompotas, Aristidis Ilias, Andreas Kanavos, Christos Makris, Gerasimos Rompolas and Alkiviadis Savvopoulos have been co-financed by the European Union and Greek national funds through the Regional Operational Program "Western Greece 2014-2020", under the Call "Regional Research and Innovation Strategies for Smart Specialisation -RIS3 in Information and Communication Technologies" (project: 5038701 entitled "Reviews Manager: Hotel Reviews Intelligent Impact Assessment Platform").


Konstantina Iliopoulou
email: k.iliopoulou1@gmail.com

Andreas Kanavos
email: kanavos@ceid.upatras.gr

Aristidis Ilias

Christos Makris
email: makri@ceid.upatras.gr

Gerasimos Vonitsanos
email: mvonitsanos@ceid.upatras.gr

Improving Movie Recommendation Systems Filtering by Exploiting User-based Reviews and Movie Synopses

Keywords: Recommendation Systems, Movie Recommendation Systems, Collaborative Filtering, Content-based Filtering, Text Analysis

This paper addresses the subject of Movie Recommendation Systems, focusing on two of the most well-known filtering techniques, Collaborative Filtering and Content-based Filtering. The first approach proposes a supervised probabilistic Bayesian model that forms recommendations based on the previous evaluations of other movies the user has watched. The second approach composes an unsupervised learning technique that forms clusters of users, using the K-Means algorithm, based on their preference of different movie genres, as it is expressed through their ratings. Both of the above approaches are compared to each other as well as to a basic method known as Weighted Sum, which makes predictions based on the cosine similarity and the euclidean distance between users and movies. In addition, Content-based Filtering is implemented through K-Means clustering techniques that focus on identifying the resemblance between movie plots. The first approach clusters movies according to the Tf/Idf weighting scheme, applying weights to the terms of movie plots. The latter identifies the likeness between movie plots, utilizing the BM25 algorithm. The efficiency of the above methods is calculated through the Accuracy metric.

Introduction

Rapid Internet growth continually creates an immense amount of data, as well as the need to find more productive ways to handle it. Users daily have to face the process of choosing between overwhelming varieties of different products during their interaction with any digital platform, a pursuit often tiring and disorienting.

As one of the most popular research issues, one can consider the subject of improving the quality of ranking in Information Retrieval results. To this extent, information need is expressed through the form of queries submitted to a search engine or platform with the intention of receiving any available fact regarding the inquiry [START_REF] Baeza-Yates | Modern Information Retrieval: The Concepts and Technology Behind Search[END_REF][START_REF] Manning | Introduction to Information Retrieval[END_REF]. Effective retrieval techniques and methodologies have been mostly derived from the class of probabilistic models, and several approaches have been successfully implemented in this direction [START_REF] Baeza-Yates | Modern Information Retrieval: The Concepts and Technology Behind Search[END_REF][START_REF] Croft | Search Engines: Information Retrieval in Practice[END_REF].

Recommendation Systems provide a sound solution for the information flood each user has to face daily during their interaction with online platforms. Aiming to provide users with the ability to find products that may be of their interest, make up the target of these systems in an automatic, fast and efficient way. Their recommendations are based on the analysis of previous user behavior, with respect to the evaluation of products as well as the recognition of the similarity between different users and products. This occurs, in order to derive a prediction of which products a user will consider interesting. Due to their wideranging scope of application, the research community takes an active interest in the field.

This paper addresses the subject of Movie Recommendation Systems, focusing on two of the most well-known filtering techniques, Collaborative Filtering, and Content-based Filtering. Specifically, Collaborative Filtering is implemented through two different approaches. The first approach proposes a supervised probabilistic Bayesian model that forms recommendations based on the estimation of the probability a user gives a specific rating to some movie, by examining either the rating given to that movie by the rest of the users or the rating the user gave to other movies he/she has watched. The second approach is an unsupervised learning technique that forms clusters of users using the K-Means algorithm, based on their preference of different movie genres, as it is expressed through their ratings. Both of the above approaches are compared to each other and also to a basic method known as Weighted Sum that makes predictions based on the cosine similarity and the euclidean distance between users and movies. Content-based Filtering is implemented through K-Means clustering techniques that focus on identifying the similarity between movie plots. The first approach clusters movies according to the Tf/Idf weighting scheme, applying weights to the terms of movie plots. The second approach identifies the similarity between movie plots utilizing the BM25 algorithm.

The rest of the paper is organized as follows. Section 2 presents the related work. Section 3 overviews the basic concepts and algorithms used in this paper. Section 4 and 5 detail the implementation and evaluation respectively. Finally, in Section 6, our concluding remarks and future work are presented.

Related Work

In [START_REF] Ganesan | Opinion-based entity ranking[END_REF], authors depict the setup for an opinion-based entity ranking system. The intuition behind their work is that each entity can be represented by all the review texts and that the users of such a system can determine their preferences on several attributes during the evaluation process. Thus, we can expect that a user's query would consist of preferences on multiple attributes. Authors in [START_REF] Makris | Improving opinion-based entity ranking[END_REF] further improved the setup by developing schemes, which take into account sentiment and clustering information about the opinions expressed in reviews; also authors propose the naive consumer model as an unsupervised schema that utilizes information from the web to yield a weight of importance to each of the features used for evaluating the entities.

In addition, in [START_REF] Kanavos | Ranking web search results exploiting wikipedia[END_REF], the authors propose a novel probabilistic network scheme that employs a topic identification method, in order to modify the ranking of results as the users select documents. Also, a novel framework aiming to provide the necessary tools for the refinement of search results, taking into account feedback provided by the user, is introduced in [START_REF] Kanavos | Employing query disambiguation using clustering techniques[END_REF]. More specifically, the corresponding approach examines query-independent document processing and representation resulting in a lexical based inter-document similarity, that allows clusters to be formed.

Bayesian networks are known to perform well in the recommendation problem, as shown in the studies of [START_REF] Jiang | A bayesian recommender model for user rating and review profiling[END_REF][START_REF] Miyahara | Improvement of collaborative filtering with the simple bayesian classifier[END_REF][START_REF] Pomerantz | Context dependent movie recommendations using a hierarchical bayesian model[END_REF]. The main difference between what we propose and the research in [START_REF] Miyahara | Improvement of collaborative filtering with the simple bayesian classifier[END_REF] is that we aim to predict the actual rating given by a user on a scale of 1-5, and not simply predict whether users will like or dislike an item. We can clearly observe that the authors of this work propose a hierarchical, Bayesian, content-based approach that aims to improve the current recommendation systems by incorporating context-related information when building the user profiles. Similar is the work presented in [START_REF] Pomerantz | Context dependent movie recommendations using a hierarchical bayesian model[END_REF], where a collaborative filtering technique based on a simple Bayesian classifier as a solution to the recommendation problem, is introduced. Related to the above contributions is [START_REF] Jiang | A bayesian recommender model for user rating and review profiling[END_REF], as authors propose a Bayesian model that incorporates user preference information expressed in their reviews; the research uses collaborative techniques and topic modeling to solve the recommendation problem. Furthermore, K-Means algorithm, being one of the most applicable clustering algorithms, often fits in the recommendation scheme. The research presented in [START_REF] Sarwar | Recommender systems for largescale e-commerce: Scalable neighborhood formation using clustering[END_REF] aims to improve the scalability of collaborative filtering recommendation systems by exploiting the bisecting K-Means clustering algorithm. The key idea is to apply the clustering algorithm in the user-item matrix and utilize the formed clusters as user neighborhoods. In order to form predictions for a specific user, the system implements the collaborative filtering algorithm by examining only the users' neighborhood. The approach in [START_REF] Byström | Movie Recommendations from User Ratings[END_REF] exploits K-Means clustering, in order to form user clusters based on their ratings and a softmax regression classifier to predict the cluster each user belongs to. What is aimed here, is for the system to recommend the highest-rated movies from that cluster. In addition, the study in [START_REF] Lydia | Document clustering based on text mining k-means algorithm using euclidean distance similarity[END_REF] discusses the clustering of similar documents by using the K-Means clustering algorithm and the Tf/Idf representation of the documents.

The research conducted in [START_REF] Marlin | Modeling user rating profiles for collaborative filtering[END_REF] centers on rating-based collaborative filtering. Its onus is to build user profiles and predict all missing values by developing a generative latent variable model, which extends already existing models such as the multinomial mixture model and LDA and is called the User Rating Profile model (URP). As a previous work on opinion clustering emerging in reviews, one can consider the setup presented in [START_REF] Gourgaris | Review-based entity-ranking refinement[END_REF]. Authors propose a probabilistic network scheme, e.g., inference network, which consists of four component levels, in following takes as input the belief of the user for each query (initially, all entities are equivalent) and produces a new ranking for the entities as output.

The work presented in [START_REF] Phorasim | Movies recommendation system using collaborative filtering and k-means[END_REF] proposes a scheme for user clustering so as to identify similar tastes in movies; also, the clustering techniques are prone to discovering relationships between movie plots and movie genres. Our work however differentiates from this study since we focus on capturing similarities between movie plots regardless of the genre they ultimately belong to.

Preliminaries

The representation of a text in a comprehensible form for data mining and text pre-processing is the first important and critical task, considering tokenization, stop-words removal, punctuation and number removal, POS tagging, lower case as well as stemming. Text representation is based on the assumption that any text is described through its constituent words and is essential about replacing words with a numerical value, making the text editable by standard methods of analysis.

Text Representation

There are two main categories of text representation:

-Tuples, where the text is represented by a plurality of fields. The number of fields is equal to the size of the vocabulary and each field corresponds to a different word. -Vector, where the text is represented by a vector. Each different word in the vocabulary corresponds to a component of the vector and defines one of the dimensions of the vector space. Representing a text document using vectors, is the most common approach, as it allows for more efficient calculations.

Tf/Idf

Tf/Idf constitutes one of the most popular algorithms to weigh a keyword in any content, assigning the importance to that keyword based on the combination of term frequency (Tf) and inverted document frequency (Idf) weights. It developed for Information Retrieval, however it is also widely used in Data Mining in combination with classification and clustering algorithms. Specifically, given a term k i of the document d j , the weight w ij defined by the Tf/Idf, is denoted as T f /Idf i,j so as to apply:

T f /Idf i,j = T f i,j × Idf i (1)

BM25

The word retrieval function BM25 is known due to ranking sets of documents based on query terms appearing in the documents of interest, regardless of their proximity within the document. Specifically, BM is a family of scoring functions with slightly different components and parameters, while various variants of the basic equation of the BM25 are encountered. In our work, a variant of the basic equation of BM25 was used, in which Idf is normalized to avoid negative values of the ranking function.

Principal Component Analysis

Principal Component Analysis (PCA) is one of the most commonly used methods for dimensionality reduction and feature extraction. It creates uncorrelated linear combinations of the original possibly correlated variables, and by utilizing the eigenvalues and eigenvectors of the variance/covariance matrix, it projects the data on a space of different dimensions transforming them in a way they can be adequately described by fewer dimensions.

Similarity Metrics

In this paper, vectors represent users or movies, and the similarity is expressed by the distance of these vectors. The two metrics used in the movie recommendation system are Cosine Similarity, which measures the similarities between two vectors, calculating its cosine of the angle between them, and Euclidean Distance, which expresses the similarity of two vectors, estimating the Euclidean distance between them. The similarity between all users or movies in the dataset can be represented by an array whose rows and columns correspond to users or movies. The value of each cell is the similarity between the elements in the corresponding row and column.

User Based Collaborative Filtering

User-based collaborative filtering makes predictions and suggestions based on the similarities among users. The movies suggested to the user are similar to those users have found interesting, that is, they have rated them highly. For example, assuming two users (U A and U B ) who have seen the same movies and have both scored them with high ratings, as well as a new movie that U A is watching and enjoying, the question will be: will this movie be suggested to U B ? A positive response occurs; judging by the past behavior of the two users, it is concluded that they have similar preferences.

Item Based Collaborative Filtering

Item-based collaborative filtering implements predictions and suggestions based on similarity among movies. The movies suggested to the user are similar to the ones they have found interesting in the past. The similarity among movies arises by examining the scores received by other users of the system. For example, let us assume three users U A , U B and U C who have seen two movies M 1 and M 2 and have rated them with roughly the same ratings, which makes these movies quite alike. If a fourth user U D watches the first movie M 1 and scores it high the system will also propose the second movie M 2 to this viewer.

Weighted Sum

The simplest way of predicting user ratings is known as Weighted Sum and results from the inner product of the user-movie matrix along with the similarity matrix. User preferences can be modeled by a M xN matrix, known as user-item matrix, where M is the total number of users and N is the total number of items available in the system. In this paper, movies are considered items, each cell contains the rating of a specific user for a concrete movie (or is empty in case that they have not provided with an evaluation). Therefore, each user is represented by a vector, whose components are the ratings of the movies they evaluated. Similarly, movies are represented by vectors containing the ratings assigned to them by the users. The aim is to fill the missing values of the matrix with the predicted ratings.

Implementation

Dataset

The dataset used in this study is called ml-latest-small and is available on the MovieLens research site run by GroupLens Research at the University of Minnesota1 . It consists of 9742 movies and 610 users, and describes the rating given to the movies by the users on a scale of 1 to 5. Each user has rated at least 20 movies, and each movie is rated by at least one user.

The dataset was extended in order to include also the movie plots by using the identifiers available in the dataset for gaining access to the content of the imdb and tmdb web pages. For each movie, the plots from these two sites were concatenated, and text pre-processing techniques were used with the NLTK Python tool, namely tokenization, lowercase conversion, numbers, and punctuation removal as well as stemming.

The ratings and number of users before and after the removal of low ratings, are presented in Table 1. It is worth noticing that after the removal of ratings with values lower than 3, 5, the mean rating per genre is greater than 4, 5; before the removal, this rating was in the range of 3, 5 to 3, 8. In addition, concerning the number of users per genre, it is shown that the same genres are considered as popular before and after the removal of low ratings.

Input Data for the Clustering Algorithm

In following, the construction of the matrices given as input to the clustering algorithm for the cases of user clustering and movie clustering, was implemented. Concretely, BM25, Tf/Idf and User Preference scores are taken into consideration for our proposed implementations.

Scores

Matrices BM25 scores can be utilized in a 1863x1863 matrix, where its rows and columns correspond to the different movies of the dataset. Each cell holds the BM25 ranking score for the plot of the movie as the column defines the query, and the row defines the plot of the movie. On the other hand, Tf/Idf scores can be utilized in a 1863x5432 matrix. Specifically, each row corresponds to a different movie, and the columns correspond to the stemmed terms of all the movie plots. Each cell holds the Tf/Idf weight of the column term for the movie plot in the corresponding row.

User Preference Matrix

The user preference matrix represents the users' preferences for the different genres of movies. Since our goal is to provide the user with movie recommendations, the first step was to remove all ratings less than 3, 5. If a user has not rated any movies with a rating greater or equal to 3, 5, the user is excluded from the procedure. For every user, the total number of movies being watched, belonging to a particular genre, was counted. In following, this count was divided by the total number of movies the user has watched. Specifically, each matrix row represents a different user, each column corresponds to a different movie genre, and each cell defines the percentage of preference of that user towards that particular genre.

Clustering

Our approach regarding the implementation of a recommendation system utilizing the K-Means clustering algorithm is two-fold, namely, user clustering and movie clustering.

Regarding the user clustering approach, the examination of users' ratings, the percentage calculation of their different genres preference, as well as the clustering based on these percentages, are implemented. The movie clustering approach is utilized in two different cases, namely focusing on the plot of each movie and implementing content-based filtering. In the first case, each movie is represented by a vector containing the Tf/Idf weights of the terms of the movie plots, while in the second case, by a vector containing the corresponding BM25 scores. In both implementations, each user is assigned to the cluster containing the highest number of movies being watched by this user. In order for the proposed method to recommend a movie to a user, the movies being watched by other users of the same cluster are initially examined. In following, the mean rating of those movies, by considering only the ratings given by the users of the cluster, is calculated and finally, the movies with the highest ratings are recommended.

The data is given as input in the form of the matrices, as mentioned above. Dimensionality reduction is considered to be an essential step before executing the K-Means clustering, and the technique utilized for this purpose is Principal Component Analysis (P CA).

Classification

The aim of recommendation systems is to calculate the probability of the movie rating given to a movie by a user while taking into consideration the ratings given by other users. Thus, a user-based and item-based collaborative filtering, as well as a combination of these two methods, are implemented. In the user-based case, each movie is represented by a vector containing all users' ratings given to that movie. Similarly, in the item-based case, users are considered as observations, and the movies form the observation features. The combinatorial filtering results from the mean of the predicted ratings, are derived from the user-based as well as the item-based filtering.

A user id, representing the user to whom movies will be recommended, and the user-movie matrix are given as input. Moreover, the missing values of each row of the user-movie matrix were filled by the mean rating of the user corresponding to that row. For the probability calculation, the multinomial Naive Bayes algorithm is utilized where we have set a = 1 for Laplace Smoothing. The specific algorithm is chosen because the possible ratings are on a scale of 1 to 5, meaning they are not binary values and their distribution is not known.

Regarding the data splitting, in the case of user-based filtering, 70% was randomly used for training and 30% for testing. On the other hand, when considering the item-based filtering, the users to whom recommendations will be made are defined as test set whereas training set includes the rest of the users.

Evaluation

For the evaluation of our proposed methods, we have used Accuracy, which is one of the most commonly used metrics for the evaluation of a system prediction. Since our goal is to compare the different approaches presented in our work, we have converted the ratings to binary values using a unified manner, in a way that high ratings (>= 3, 5) are replaced by the value 1 and the lower ratings (< 3, 5) are replaced by the value 0. In the case of Bayesian classifier, high ratings are considered the ones with value equal to or greater than 3.

For our experiments, 10 users were randomly chosen, with the only requirement having watched and rated at least 100 movies. The accuracy was calculated for each user by examining their actual ratings in relation to the predicted ratings for the movies they have watched. In following, the mean of the predictions accuracy for the different methods is calculated.

The first two principal components were the ones carrying the largest amount of information, as depicted in Table 2. In the case of movie clustering, even though the first two components held a small percentage of the total variance, our experiments showed that using more components in the clustering phase did not significantly improve the clustering results.

In order to determine the optimal number of clusters to be formed, the elbow curve method has been used. The optimal number of clusters k, in the user clustering is set as 5, and in the case of movie is set as 4. Even for the case of movie clustering, the elbow curve method provided ambiguous results, and after testing the algorithm numerous times, it was observed that high values of k lead to uneven distribution of points inside the clusters, as presented in Table 3. Furthermore, by examining the most frequent words of the movie plots in each cluster, it was found that for values bigger than 4, the formed clusters had in Tf/Idf Matrix BM25 Matrix 0 0,34391 0,00394 0,06221 1 0,24211 0,00370 0,01613 2 0,09896 0,00334 0,01260 3 0,06825 0,00313 0,01207 4 0,05264 0,00303 0,01166 5 0,04318 0,00284 0,01114 6 0,02570 0,00279 0,00972 7 0,02316 0,00262 0,00931 8 0,02169 0,00261 0,00856 9 0,01582 0,00248 0,00769 10 0,01369 0,00245 0,00731 11 0,01183 0,00238 0,00724 12 0,00943 0,00236 0,00693 13 0,00888 0,00232 0,00664 14 0,00794 0,00227 0,00630 common the most frequent words, indicating that there was no clear separation regarding the content of the movie plots. Furthermore, Tables 4, 5 and 6 introduce the experimental results in terms of Clustering, Classification using Bayesian model and Weighted Sum, respectively. Regarding clustering, the Tf/Idf movie method yields the best accuracy results. It is worth mentioning that the accuracy of the user clustering method is equal to 66.17%, and even though it is lower than the movie clustering method accuracy, it outperforms the basic Weighted Sum approaches.

In addition, regarding the classification experimental evaluation, the best result was derived from the movie based probabilistic Bayesian approach. Specifically, the Bayesian model outperforms the basic Weighted Sum model with a difference approximately 24% for the user-based case and about 20% for the movie-based case. The low accuracy score of the combinational Bayesian approach is due to the fact that the system examined only the first 1000 movies for the movie-based method.

Finally, the high similarity of the Weighted Sum results can be considered because of the low dimensionality of the user vectors utilized in our experiments.

Conclusions and Future Work

This paper offers an extensive analysis of different approaches for the implementation of Movie Recommendation Systems, providing an integrated solution to the recommendation problem. On one hand, it proposes the Bayesian Collaborative filtering approach that renders the best results, outweighing the other models discussed in this paper. On the other hand, it proposes a Content-based technique based on movie clustering according to their plots through the Tf/Idf weighting scheme, which yields a solution to the movie recommendation problem when user preference information is not available. Furthermore, the three different implementations are introduced, namely, K-Means for users and movies clustering, Naive Bayes classification and Weighted Sum for user-based, itembased and both in combination collaborative filtering.

Future work is bound to include the construction of a hybrid model combining the Bayesian and clustering techniques. The user clustering approach, despite not being the most accurate one, provides an adequate way of detecting similarities between users concerning their preferences towards the different genre of movies. It could serve as a base for the probabilistic approach, i.e., only the users belonging to the same cluster would be considered for the calculation of the probabilities of each prediction. Furthermore, it is deemed appropriate to test different techniques for dimensionality reduction, other than the PCA method. Finally, an interesting approach would be to give, as query, one term at time in the BM25 plot clustering.

Table 1 .

 1 Ratings and Number of Users Before and After Removal of Low Ratings

		Number of	Rating	Rating	Number of Users	Number of Users
	Genres	Movies	Before	After	Before	After
	Adventure	1263	3,61	4,24	606	588
	Animation	611	3,63	4,21	527	458
	Children	664	3,48	4,2	559	482
	Comedy	3756	3,56	4,24	609	603
	Fantasy	779	3,57	4,26	583	528
	Romance	1596	3,63	4,24	606	588
	Drama	4361	3,75	4,3	610	606
	Action	1828	3,55	4,23	608	596
	Crime	1199	3,75	4,31	603	581
	Thriller	1894	3,62	4,25	609	599
	Horror	978	3,45	4,24	535	472
	Mystery	573	3,75	4,29	580	542
	Sci-Fi	980	3,53	4,23	605	570
	War	382	3,87	4,33	551	513
	Musical	334	3,58	4,21	470	397
	Documentary	440	3,77	4,21	223	191
	IMAX	158	3,8	4,25	458	415
	Western	167	3,64	4,23	420	357
	Film-Noir	87	3,84	4,26	239	209
	no genres listed	34	3,61	4,22	26	20

(a) Ratings Per Genre (b) Users Per Genre Fig. 1. Ratings and Number of Users Before and After Removal of Low Ratings

Table 2 .

 2 Principal Component Variance

	PCA	User Preference
	Features	Matrix

Table 3 .

 3 Sum of Squared Errors

	Number of	User	Tf/Idf Movie	BM25 Movie
	Clusters	Clustering	Clustering	Clustering
	1	130.5	1840.6	72655490
	2	101.3	1835.8	69883117
	3	86.9	1831.6	68966348
	4	79.1	1827.7	68471660
	5	73.8	1825.3	68207625
	6	69.9	1822.2	67713490
	7	66.5	1820.1	67586018
	8	63.3	1816.8	67131015
	9	61.4	1817.3	66882121
	10	59.4	1811.1	66828590
	11	57.6	1810.3	66513930
	12	56.3	1809.5	66236101
	13	54.7	1808.3	66236317
	14	53.7	1805.7	66045114
	15	52.3	1804.9	65882937
	16	50.6	1802.1	65557487
	17	49.6	1801	65666520
	18	49.2	1801.2	65355018
	19	48.1	1797	65455797

Table 4 .

 4 Clustering

	User Clustering	66,17%
	Tf/Idf Movie Clustering 67,96%
	BM25 Movie	63,86%

Table 5 .

 5 Classification (Bayes)

	User Based	80,96%
	Movie Based	83,64%
	User and Movie Based 30,45%

Table 6 .

 6 Weighted Sum for Cosine Similarity and Euclidean Distance

		Cosine Similarity		Euclidean Distance
	User	Movie	User and Movie	User	Movie	User and Movie
	Based	Based	Based	Based	Based	Based
	56,21% 64,14%	60,45%	56,21% 64,14%	60,21%

https://grouplens.org/datasets/movielens/

Acknowledgement

Andreas Kanavos, Aristidis Ilias and Christos Makris have been co-financed by the European Union and Greek national funds through the Regional Operational Program "Western Greece 2014-2020", under the Call "Regional Research and Innovation Strategies for Smart Specialisation -RIS3 in Information and Communication Technologies" (project: 5038701 entitled "Reviews Manager: Hotel Reviews Intelligent Impact Assessment Platform").


Miznah H Alshammary
email: [miznah.alshammary@kcl.ac.uk

Costas S Iliopoulos
email: c.iliopoulos@kcl.ac.uk

Mujibur R Khan
email: md.khan]@kcl.ac.uk

Fingerprints Recognition System-Based on Mobile Device Identification using Circular String Pattern Matching Techniques

Keywords: Mobile Device Fingerprinting, Fingerprint Recognition, Rotation, Circular String Matching

As fingerprint recognition systems have become increasingly adopted within a range of technology applications over the last decade, so too has their attention within emerging research. However, although this increased attention has led to an enhancement of the software and algorithms behind this recognition process, the majority of research has still not addressed the issues of incorrect rotation or proximity between the finger and the device. Current systems assume that the direction of the imprinted finger will align with that of the target fingerprint image; this decreases the accuracy of fingerprint recognition across a variety of finger orientations and scenarios.

In response to this use-case dilemma, this paper proposes a new technique of pattern matching that can account for this natural range of fingerprint orientations. This is achieved first through a preliminary stage of orientation identification, whereby the fingerprint image can be stored under multiple permutations by using approximate circular string-matching algorithms.

This enables the database of images for each approximate permutation of orientation to be stored in advance. It can then be matched against the strong information of the fingerprint at its exact relative rotation of input. The improved accuracy of recognition demonstrated through the results of this study may enable the functionality of fingerprint recognition to adapt to challenging device formfactors and provide the accuracy needed for military and medical applications. .

Introduction

With modern devices becoming increasingly configured for the high-speed transmission and sharing of data across mobile networks [START_REF] Miznah | A Review of Recent Developments in NOMA and SCMA Schemes for 5G Technology[END_REF], this in turn has led the volume of information shared with unknown entities to rise. This has made the sharing of personal data through recognition systems a fundamental concern and is consequently pressuring manufacturers to increase recognition accuracy. With precursors to fingerprint recognition dating back to the 19 th century, the conceptual functionality of this technology has long since become attractive for tracking and managing criminal records. However, as demonstrated by the case of criminal records in Argentina [START_REF] Unar | A review of biometric technology along with trends and prospects[END_REF], it also improves forensics and the effectiveness of local police. Furthermore, the unique profile of minutiae and ridge patterns that vary in fingerprints from one individual to the other have long made fingerprint recognition a highly accurate method of confirming and tracking identity. Moreover, past analogue methodsand even contemporary methods in the algorithm formathave refined the capacity to target this static structure, and then compare the imprint against past image records [START_REF] Sebastian | Literature survey on automated person identification techniques[END_REF].

However, as this functionality has emerged as an authentication method for a range of computing devices whereby the rotation and direction of imprints has varied dramatically to match the mobile form-factor, this removes the traditional security advantage of fixed devices. In turn, this compromises the accuracy of fingerprint recognition in devices that require flexible finger orientation, many of which are used today for crucial functions such as communication and financial transactions.

Building on this dilemma, this study will explore past algorithms that have in part addressed this issue of relative proximity. It will then highlight contributions from the results which may constitute a recognition system that is prepared for these modern scenarios.

Literature Review

With traditional systems primarily focused on comparing the topographical similarity between an imprint and past stored images from the same user, past research has developed increasingly accurate systems of modelling the static structure of fingerprint minutiae. More recent models adopt a 3D structure that can account for pressure and depth [START_REF] Tan | Fingerprint matching by genetic algorithms[END_REF], [START_REF] Kovacs-Vajna | A fingerprint verification system based on triangular matching and dynamic time warping[END_REF], [START_REF] Jain | an identity-authentication system using fingerprints[END_REF], [START_REF] Tan | Robust fingerprint identification[END_REF]. However, although the contemporary recognition systems for minutiae-based matching enable more flexible user scenarios by predicting how the minutiae structure may morph in response to varying levels of pressure [START_REF] Kai | A novel ant colony optimization algorithm for large-distorted ngerprint matching[END_REF], this approach to matching still assumes that the finger is placed vertically. It is thus less accurate for devices held in a variety of orientations. Furthermore, in addition to lacking this flexibility for fingerprints other than in the vertical orientation, past methods also appear to experience reduced accuracy in a number of applications. These include comparing biological systems; the recovery of information and correlation of data from different files; and signal processing. The most significant algorithms explored in this study are the Landauand-Vishkin and the Needleman-Wunsch algorithms [START_REF] Landau | Fast String Matching with k Differences*[END_REF], both of which are incorporated into our proposed solution.

Our Contribution

Building on the lack of methods for accounting for orientation in previous studies, this paper proposes a pattern-matching process for mobile fingerprint authentication that uses classification to match fingerprint profiles. This is achieved by deriving the information of the minutiae by intercepting the fingerprint with a series of scan circles. This information is then translated into a string.

Following this initial stage, the string information of the fingerprint is then matched in a local image database. This matching process is conducted by a pattern-matching algorithm that is tolerant to topographical error and it thus enables the identification process of the minutiae to be done in linear time, according to the combined length of all the searched strings. Furthermore, as this finger identification method leverages the efficiency of circular string matching, the accuracy of our identification method could be separated from the topographical similarity of the placed fingerprint relative to the vertical orientation. In addition, as our method utilised approximation rather than exact matching of the minutiae features, the distortion of the input image was significantly decreased.

However, in addition to the advantage of targeting circular strings rather than static features of the minutiae bound to a vertical orientation, our process also incorporated minutiae extraction, whereby the speed of the overall recognition process would be significantly impacted by this extraction speed. Moreover, in order to maximise the speed of extraction, we have aimed to improve the performance of minutiae extraction so that the overall execution time of the process is reduced.

Our developed alternative of Fast Minutiae Extraction saw a significant speed increase over Novel Minutiae Extraction-2 presented in [START_REF] Oluwole | Identication of Fingerprints using Circular String Approximation for Mobile Devices[END_REF] and Novel Minutiae Extraction presented in [START_REF] Ajala | Fast Fingerprint Recognition Using Circular String Pattern Matching Techniques[END_REF].

In addition, the series of scan circles, precise location and rotation of the input fingerprint captured by our method can be translated into a string. This information can then be stored as images within the fingerprint database for later matching. Moreover, this was achieved by using rapid circular string-matching algorithms, which enabled the total lengths of the strings to be searched in linear time, accelerating and enhancing the accuracy of the recognition process.

In this paper, our proposed algorithm not only aims to enhance minutiae extraction to improve the accuracy and flexibility of the fingerprint recognition process. It also reduces the overall time of execution. In order to outline our process, the following subsections detail the proposed algorithm in its two underlying components: Fast Novel Minutiae Extraction and our algorithm outline.

Fast Novel Minutiae Extraction

As our process repeatedly introduced minutiae extractions, this meant that the speed of this extraction process would significantly impact the overall time required for successful fingerprint recognition. Consequently, this project developed an alternative extraction method we refer to as Fast Novel Minutiae Extraction. This alternative saw a significant speed increase over Novel Minutiae Extraction-2 presented in [START_REF] Oluwole | Identication of Fingerprints using Circular String Approximation for Mobile Devices[END_REF] and Novel Minutiae Extraction presented in [START_REF] Ajala | Fast Fingerprint Recognition Using Circular String Pattern Matching Techniques[END_REF].

The outline of Fast Novel Minutiae Extraction is presented below:

Outline of the Algorithm

Our algorithm was structured to identify the circular strings from the saved fingerprint and input at the longest length: asmf/acdm was used to check that the relative rotation of the circular string of the input matched that of the saved fingerprint image. Furthermore, the Needleman-Wunsch approximation algorithm was used to check the exactness of the alignment.

The main component that dominates the speed of execution is the extraction of minutiae from the image and constructing the circular string, which is repeatedly invoked throughout the whole process.

We have outlined the complete process of Fingerprint matching as below:

1. Database formation: A database of circular strings was constructed, with the centre of the image classed as the effective centre. 2. Concentric Circle-to-Strings Formation: Concentric circles were drawn, and then (using Fast Novel Minutiae Extraction) converted into strings comprising of 0's and 1's. For example, assuming that Cir is the circular string of the ith image with a radius of r, all rotations of each of the circular strings are saved to the database. By letting DbRir be the collection of rotated strings from Cir; a Cir = "0111" would mean that DRir would hold values of "0111", "1011", "1101", "1110". Conversely, by letting DbRir be the collection of rotated strings from Cir; Cir = " 0111" would mean that DRir would hold values of be "0111", "1011", "1101", "1110". 3. Binary String Formation: After the previous phase, Fast Novel Minutiae Extraction was repeated in order to construct circular binary strings for each circle. 4. CsR List Formation: After binary string formation, the process then proceeded to create a sorted CsR list of radius pairs and circular strings (< CStr,Radius >) in a descending order of the CStr length. 5. Rotation Comparison: Following list formation, the asmf/acdmf method was then applied along with the Needleman-Wunsch algorithm. This enabled the rotations to be compared, whereby a percentage of matched strings recorded as higher than a certain threshold (tS) would result in the sum of the match percentage being saved.

The ith image was marked as the 'candidate image' and then the (i+1) th image was selected until all images within the databased had been utilised. Following this process, this stage could be repeated after choosing a different centre point. 6. Image Matching: After the previous stages, the process finally returns to the match images for verification.

Experimental Results

We coded the program in C# using an Intel Pentium processor (CPU 4415U) with 2.30 GHz, the random-access memory was 4.00 GB, the Operating System was 64-bit Windows 10, and the platform was MS.Net Framework 4.5. We aimed to improve the performance of minutiae extraction so that the overall execution time of the process is reduced.

Comparing the time required in milliseconds for each method, it is clear that our solution algorithm provides better results for the overall execution time of extracting minutiae from the image and constructing the circular string, which is repeatedly invoked throughout the whole process. This is presented in Table I and Figure 2.

Table I shows that there are two main factors that ensure the accuracy and performance of the proposed algorithm. These are the size of the database and the time required for extracting minute details from an image and creating a circular chain that is invoked repeatedly throughout the entire process. Table 1 shows the results for two different database sizes. For all inputs, we captured the time required for each method and the results are compared in Fig 1.

Conclusion

With an increasing volume of devices adopting fingerprint recognition, this will pressurise manufacturers to re-evaluate existing minutiae-matching techniques and to explore enhanced models that are better adapted to the non-vertical orientations of input that are becoming prevalent among mobile devices. Consequently, in response to the recent increase in algorithms and string-matching techniques, this paper explored this barrier of orientation flexibility, and how our proposed solution may lead to faster mobile user scenarios. As demonstrated by the results, our proposed solution offers an enhanced version of previous algorithms used for extracting topographical features of minutiae from the input image. This increases the overall efficiency of the identification process.

Overall, this study stands as an example of how mathematical algorithms can be used to enhance the functionality of a computing-based function in order to more accurately model a device's surrounding environment. Furthermore, in addition to accounting for a more realistic variety of user orientations in fingerprint recognition, this proposed system may also be able to enhance models beyond bioinformatics, which face a similar rise in device mobility and range of handheld orientation.

Fig. 1 .

 1 Fig. 1. Fig 1. Fast Methods VS Novel Methods

Table 1 .

 1 Table I. Summary of findings

	Data-	Time required Time re-
	base		quired
	size	for	for
		Novel Meth-	Fast Meth-
		ods	ods
		(Milliseconds)	(Millisec-onds)
	50	881300	67765
	100	3276930	1290428