A method of A-BAT algorithm based query optimization for crowd sourcing system

Published Online March 2018 in MECS

Data mining is one of the meaningful processes of extracting and mining facts from huge volumes of data. Gold mined from rock or sand is equal as the knowledge mined from data. Data mining is also named as knowledge discovery [18], [19]. Data preprocessing represents any type of processing performed on uncommon data to equip it for a different processing strategy [16], [17]. Preprocessing methods convert the information into a design. For the user convenience, the data are efficiently and successfully processed with the help of preprocessing methods. Crowd sourcing is a tale of team work, agreement, cooperation aggregation and originality. Crowd sourcing is a call to all the people in the crowd to create, discuss, refine meaningful ideas or tasks or help via the web. Crowd sourcing has an important online distributed problem-solving and construction model. Crowds of public can solve some problems faster than an individual or small groups. Crowd sourcing has pulled in developing interest in recent years as a successful device for saddling human knowledge to take care of issues that PCs can't achieve well, for example, reading, penmanship acknowledgment, sound translation and photograph labeling. In 2006, Jeff defined the term Crowdsourcing in his article wired magazine [25]. Jeff explained crowd sourcing as an idea of outsourcing a task that is frequently performed by an employee to a huge crowd of population in the form of an open call. Crowd and outsourcing combined together to make the phrase crowd sourcing. The concept is to take the work and develop it by a crowd of workers. Collect the information quickly and efficiently through the crowd sourcing.

A Structured Query Language like declaratory part is modified to improve the complexities of dealing with the crowd and supply the crowd sourcing complex structure an interface that is familiar to many database clients. According to the search query, a declaratory system must compile the query first, produce the plan of execution and subsequently finally post the human intelligence tasks (HITs) to the crowd. In relevance to the given plan, it gathers the answers, hold errors and subsequently identifies the results.

• A. Query Optimization

Many relational database systems have query optimization function. Selecting the most relevant query plan is the process of query optimization. The query optimizer works out to decide the most active way to carry out a given query by considering the probable query strategy. In terms of estimated monetary cost, query optimization is mainly used to find out the quality query plan.

Nature has always been a brainwave for researchers. Certain years ago much new nature inspired algorithms were created and modified to solve some critical problems in optimization. This paper is proposed to extract the information from the CROWDOP by using preprocessing technique. Data preprocessing describes any type of processing performed on rare data to organize it for a different processing method. Data preprocessing method is used to convert the information into a format that may be very simple and effective for the client. Sub categories of data preprocessing techniques are Data cleaning, data integration, data transformation and data reduction. The system used the information and extracts the required information based on the parameters. In the database administration query, optimization is the refining process. One of the main reasons of slow speed of execution could be excess normalization leading to single table. Additionally the number of tables, further the unpredictable way of joins, and therefore, take more execution times. So to retrieve data quickly, there is a need to optimize the query [31] [32]. In order to optimize the queries, Meta heuristic techniques are used.

The basic organization of the paper is as follows: Section II presents the related works and the System Architecture is described in section III. Section IV presents the Overview of the BAT Algorithm. Section V presents the Overview of the ABC Algorithm. Results and Analysis part are discussed in section VI. In section VII, Conclusion and Future work are discussed.

• II.    Related Works

Many authors have tried to develop crowd sourcing algorithm to reduce cost and latency. Some highlights of the related work are outlined here. Ju Fan et al [1] formally studied the problem of cost and latency. They found, query plan that is suitable for balance between cost and latency. They proposed query optimization algorithm that generates a query plan and evaluates in the market place, Amazon Mechanical Turk. It is used to generate a query Plan, and also it is a good one for balance between the cost and Latency. Sai Wu et al [2] proposed the problem of privacy of published data. Published records in Human Intelligence Task (HIT) may contain sensitive or secret's attributes that cause the privacy leakage. They proposed K-Anonymity algorithm, which is to control the information loss and the accuracy of crowd sourcing. K-anonymity methods are used to secure the protection of published data. The tradeoff between the privacy and the accuracy are resolved by K-anonymity approaches. K-Anonymity can be used to reduce crowd cost and maintain high accuracy [27]. Beth Trushkowsky et al [3] converse on the query progress. Monitoring the query progress is extremely troublesome due to non-consistent appearance of data. They studied about the problem of non-uniform arrival of data.

Statistical tools are used to drive query execution and crowd sourcing approaches. Species estimation algorithm helps to execute the set enumeration queries. Crowd sourcing database systems are used to expand the accuracy of cardinality estimation. Eleonora Ciceri et al [4] states that the issue of Top-K queries over indeterminate data. An eminent class of utilizations generally allowed to as Top-K queries. The main target of Top-K queries is finding the best k-objects. Online, offline and incremental algorithms are used to find out the uncertain data. In the minimal set questions presented, uncertainty resolution is the issue for trust-based intrusion detection determines the optimal trust threshold for minimizing false positive and false negative.

G.Archana et al [5] explained about the problem of extracting the data from the crowd. In that paper, proposed preprocessing method, which is used to extracting information from the crowd. Preprocessing strategies are classified into data cleaning, data integration, data transformation and data reduction. Crowd optimization algorithms named optimization structure, optimization select, optimization joins, create parse tree, latency. Bound optimization is used to extract the information. User select the latency rated product. Customer can purchase the best product with the help of proposed method. Akshay.S.Patil et al [6] studied about the problem of best query that proposed novel improvement approach, which is used to find out the most effective query. Crowd sourcing structures can be extensively set up into the principle based, and expense based. From this principle based, approach is difficult to actualize. Bere searching, Mane Kush [7] proposed a new approach to social Science. Human experience needed to select the best information. Participants are motivated to find out the correlations of some human behavior result. Here two models are implemented. The first model forecast user's monthly electric charge consumption, the second one is the user's body mass index. This method is useful to answer many difficult questions. Tarek Ali, Eman Nasr [8] proposed a CrowdCE model. CrowdCE is an SDLC model intended for use by crowds. SDLC using the mesh style model. A collaboration model structurally decomposes the overall computing element into human based computing elements and atomic machine computing elements. CrowdCE is a model for managing the collaboration and coordination of MBCE and HBCE.

Christian Nieke et al [9] studied about the problem of incomplete Data. A top crowd, a novel and efficient algorithm works on incomplete data further more controlling query processing cost as a response point in time and money. This algorithm drastically reduced number of crowd access. The building crowd enabled query processing operators for Top-K query processing with assist the top crowd algorithm. Correct query results are generated by Safe pruning rules. Real and synthetic data set shows the benefit of Technique. Nature has constantly been a motivation for young researchers.

In order to manage difficult and complex problems in optimization, few years ago, several natures inspired algorithms have been developed. Uma et al [10] studied about the problem of discovering an interaction pattern in the semantic knowledge. Author enhanced the ABC algorithm using the partial least square mechanism (PLS).The frequent interactions made in the algorithm are used to reduce the execution time. The enhanced ABC algorithm is used for interpretation of human behavior.

Priya et al [11] deliberates on the issue of information recovery. Authors try to enhance the searching efficiency using the Hybrid Genetic algorithm-Particle swarm optimization. The searching results are enhanced using the new HGAPSO algorithm. The fitness function used in the algorithm gives the more sophisticated results.

Ruphashini et al [12] try to find out the drawbacks of a single query system. Decrease the delay time to perform the question author develops the Ant colony optimization algorithms. Using the single queries handled a huge amount of data can be stored and retrieved.

Constrained optimization problems [30] are discussed by Soudeh et al [13]. In order to overcome the problem of insufficiencies in ABC algorithm author has developed an efficient constrained artificial bee colony algorithm. In that algorithm, special operator that is smart flight utilized as a part of the scout bee phase. Several constrained benchmark problems are verified by eABC algorithm. EABC algorithm is very viable one.

Yun Feng Xu et al [14] concentrating a simple and skillful Artificial bee colony algorithm. The employed and onlooker bee phases are modified to a new ABC algorithm. Author tested 12 bench mark functions. Author proposed another ABC algorithm to balance the exploration and exploitation of ABC. The NABC algorithm is simpler and easier to execute, and it also improves accuracy.

Sandeep et al [15] focused the search procedure in ABC Algorithm. In the Population-based algorithm, ABC algorithms are important one. Some draw backs will happen in the search procedure in the ABC algorithm. In order to improve the stability of convergence capability and diversity this paper introduces a new search method. The memetic algorithm is used to improve the phase of employed bee an onlooker bee, that method is used for fitness calculation and probability calculation. Author proposed improved memetic ABC algorithm that is superiority than other ABC algorithms.

• III.    System Architecture

Fig.1 illustrates the planning, design of query processing in crowdop. The Crowdsourcing user provides a structured query language like query.

Fig.1. A-BAT implementation in Crowdsourcing

The query optimizer takes the accountability to process the question, firstly, which analyses the query and makes an optimized query plan.

Here applying A-BAT algorithm is used to find out the optimized product. The Crowdsourcing executor executes the query arrangement and produces a Human Intelligence Task (HIT) the HITs are published on the crowd sourcing market places like Amazon Mechanical Turk. Taking into account the HIT answers are gathered from the crowd. Crowd sourcing executor calculates the query and yields the gained answers to the client.

The results are retrieved based on the user query. The maximum visited product has been calculated using the A-BAT Algorithm. It easily acquires the result from the crowd based on the maximum visited of the products depend on cost. Based on the maximum visited a product will be displayed by the user result. To minimize the cost and latency using the A-BAT Algorithm used to find an out maximum visited a product. CROWDOP backings expense based enhancement for all the three administrators, upgrades the general cost of all administrators included in an arrangement.

• IV.    Overview of the Bat Algorithm

  Difficult optimization problems are solved by Xin. She Yang in 2010, based on the echolocation behaviour of the bats; Yang produced an interesting optimization procedure called Bat Algorithm [20].

Procedure:

Step1 :Function of the Bat Agorithm f(X),X=(X1,Xd)T.

Step 2 :The Value of Bat population is adjusted as Xi(i=1,2,n)and vi. Pulse frequency value allocated fi at Xi.

Step 3 :Pulse rates ri and the Loudness Ai are iniialized.

Altering frequency value,generated a new solutions

,and changing velocities and locations/solutions.

Step 5 :if (random>pulse rate).Choose the best solutions.

Step 6 :Generate a local solution nearby the selected best solution end if.

Step 7 :Create a new solution(Flying random)

Step 8 :if(random loudness Ai & f(Xi)f(X*)) Agree the new solutions.

Step 9:Increase Pulse rate and reduce loudness Ai end if

Step 10 :Find out the bats rank and choose the current best X* end while

Step 11 :Post procedure output and picturing

Bat use echolocation to detect prey. In the full darkness, bat has a skill to discover its prey and diagnoses different kinds of insects. In most of the cases they exploit, short frequency signals to evaluate the object [29].

Echolocation of bat's works as sonar in bats, emits a loud and short pulse sound, and it kicks a piece after a small amount of time, the echo returns to their bats ears [21], [22]. A bat can decide an object’s dimensions, form, path, period, and movement with the help of echo. Bat algorithm is considered as a new Meta heuristic algorithm based on Bat behavior.

• V.    Abc Algorithm

  To resolve optimization glitches Dervis Karaboga predictable an artificial bee colony algorithm in 2005. ABC as an optimization tool provides a population-based search procedure. In the ABC algorithm, the groups of artificial bees are sub-characterized into employed bees, observers and watches bees [15]. The conversation of information among bees is the most significant incidence in the creation of collective knowledge, and this be contingent on communication. Sharing information

among bees associated with the quality of food happens in the dancing area of the hive [26]. This dance is characterized as round dance or waggle dance. The direction of the waggle run encompasses about the direction of nutrition. In the bee colony crowd, haphazard search carrying out bee is identified as scout or watcher bee. The bee which is going to the food source which is visited by it earlier is employed bee. The bee waiting on the dance area is an onlooker bee [27]. The onlooker bee with scout also called unemployed bee. In the ABC algorithm, first 50 % of the honey bee colony entails of employed artificial bees, and the second half establishes the onlookers [23]. For every food source, there is separable only one employed bee.

Procedure:

Step 1 : Bee Population value initialized

Step 2 : Check the fitness of the Population value

Step 3 : While (Termination not met)

Step 4 : Choose the largest points of fitness (Visited by the bees)

Step 5 : Send bees to the selected points of fitness and evaluate

Step 6 : From the each patch select the bee with higher fitness.

Step7 : Randomly allocate remaining bees to the search apace

Step 8 : End While.

In other words, the number of employed bees is equivalent to the amount of food sources around the hive. The employed bee whose food source is exhausted by the employed and onlooker bees becomes a scout. The main stages of the unique ABC algorithm are given above:

The standard ABC algorithm [24] had disadvantages of hastily falling into local optima and slow convergence rate in later stage [10], [13], and [14]. So that we are using random walk step in this place. The New Algorithm is named as A-BAT Algorithm. The initial food sources are produced randomly in the search space due to dissimilar problems. In the employed bee stage, worker bees search for the local optimization value in the neighborhood of food source. Generally, different local food hunt strategies are utilized for various issues. In our paper, Random walk of BAT algorithm is applied in the place of onlooker bee phase. In the onlooker bee phase, the random selection process will be utilized here to search for local optimization value in the neighborhood of food source, and the higher probability solution will be prey and recognize different A random walk with direct exploitation is used for the local search that corrects the current best solution. ε denotes path and intensity of random-walk that is known as scaling factor. The process for updating the position of the bats and the velocity is same as to that of the PSO (Particle Swarm Optimization) algorithm. In this manner, the BAT algorithm can be understood as a well-known balance between the   standard  particle swarm optimization algorithms. The intensive local search is controlled by the loudness and pulse rate. The local search is propelled with the proximity relying upon the rate ri of pulse emission for the, i-th bat. When the bat discovered its prey decrease loudness and raising the pulse emission. The loudness can be preferred as any value of convenience. The A-BAT Algorithm has three stages. They are initialization of food sources, optimization phase, and Random walk phase.

Procedure of A-BAT:

The input control parameters of ABC are set as:

Colony Size, CS=5, and

Dimension of the problem, D = 2

Limit of scout is calculated as

LS =

sizeof colony x d ₌ 5 x 2 ₌ 5

Control parameters of BAT is set as:

Pulse rate r_i^t and

Loudness A_i^t

Calculation of the objective function:

obj ⁽ г ) =

min{(x     (i ))2 + (x - (i ))2} max       min

In the above equation (1), x   (i) -Maximum of the confidence value max xmin (i) -Minimum of the confidence value

The A-BAT consists of four main phases:

Step 1: Initialization of population

First, Three food sources will be initialized the positions of 3 food sources (CS/2) of employed bees, haphazardly using uniform distribution in the range (50, 500).

x j = x mmin ⁺ rand [0,1] ^{x (} x m x - x mn )      (2)

Where i = 1,2, — , N and j = 1,2, — , D .

x ^j - i^th employed bee on the dimension j of the Ddimensional space.

N - Number of employed bee.

x j -Upper bound forxj . max                          i x j -Lower bound forx j .

Step 2:Calculation of the fitness function:

F ( i ) = ^ (1 + obj ( i ))

1 + abs ( obj ( i ))

if ( obj ( i ) >  0)

if ^{( obj (} i ) <  ⁰⁾

obj ( i ) Is separate objective functions

Step 3: Employed bee phase (Update new position)

For each employed bee produce new solution (food source position)

v ij   ^xij ⁺ ^ ij ^{( x}ij   ^xkj ) ’           ⁽⁴⁾

Where, j = 1,2, — , D and k = 1,2, — , N .

In the above equation (4)

x ^j - is the i ^th employed bee, v ^j is the new solution for x ^j , x ^j - is the neighbor bee of x ^j in employed bee population, ф -Randomly selected in the range [-1, 1],

D - is the dimension of the problem and

N denotes the number of employed bee.

In the above equation j and k values are nominated randomly. Best Solution will be memorized.

Step 4: Random Walk Phase

A solution is chosen among the best solution and random walk is applied in order to increase exploration. Thus a new candidate solution is produced.

^xnew = ^xold ^{+ £} A          ⁽⁵⁾

Where Ɛ [-1, 1] is a random number that indicates the path and intensity of random walk, while A^t is the average loudness of all the bats at this time step.

Loudness and pulse emission rate must be altered as reiterations continued. When the bat gets closer to its prey the loudness normally decreases and pulse emission rate r increases. By the resulting equations loudness and pulse emission rate are modernized.

A ; ^{+ 1} = a a                (6)

r i ^{+ 1} = r ⁰[1 - e ( -^Y ) ]                  (7)

Where α and γ are constants and is set to 0.9 in our simulation. Here the initial loudness can typically be [1, 2], while the initial emission rate can be normally [0, 1].

The A-BAT pseudo-code is illustrated here,

The detailed pseudo code for A-BAT Algorithm is given below,

• VI. Proposed Algorithm

Step 1 : Generate the initial population Xi where i=1,2,3,…..N

Step 2 : Estimate the fitness value of the Crowd.

Step 3 : Gen=1

Step 4 : Gen ≤ Gen max (Recap)

Step 5 : For each employed bee yield new solution(Food source position)

v u = x u + V ij ( x u - x kj ) ,

Calculate the value fi

Apply greedy selection process between Xi and Vi.

Step 6 : Select a solution amongst the best solutions.

Step 7 :Solution updating using random walk

Apply greed selection process for the random walk between Xi and Vi.

If(ran

Accept new Solutions Increase ri reduce Ai Ranks the bats and Find current best X*

End While

Display results

Step 8:If there is an abandoned Solution then replace by with a new random formed solution Xi for the Scout.

Memorize the best food source position

Step 9:Gen-Gen+1

Until cycle=Maximum cycle number

Step 10:End.

As mentioned above, in this article we propose a new Hybrid ABC-BAT that is named as A-BAT Algorithm. It was obtained by hybridizing the original ABC and BAT algorithms using the Random strategies. As a result, A-BAT from the original ABC and BAT in step 7, where solution is modified using Random walk phase.

Fig.2. Comparison between the proposed method Latency with ABC and BAT Algorithm

The above fig.2 shows the Latency of the proposed methodology by varying iterations. Here, x-axis represents the Bio-inspired Methods and y-axis represents the Latency. The proposed work runs with totally 1000 iterations. From the above graph, it is well clear that A-BAT algorithm has Low Latency in the crowdsourcing Environment compared with other algorithms. Then we compare the Accuracy of the algorithm. When analyzing figure 2, our proposed approach achieves the minimum Latency of 64 which is 69 for using BAT based Query Processing and 78 for using ABC-based Query Processing. Next we compare the Accuracy of the algorithm.

Fig.3. Comparison between the proposed method Accuracy with ABC and BAT Algorithm

Fig.3 represents the Accuracy of a proposed algorithm with ABC and BAT algorithm. From the figure.3 it is clear that the artificial bee Colony Algorithm has lower accuracy while the proposed algorithm i.e. A-BAT has better accuracy. Even then when we consider the BAT algorithm has better accuracy compared with ABC Algorithm. From the graph we can clearly understand Proposed algorithm have 97 % Accuracy. Next we compare the Time of the algorithm.

Fig.4. Comparison between the proposed method Time with ABC and BAT Algorithm

Fig.4 described Time of the proposed algorithm with ABC and BAT algorithm. Here, the x-axis represents the Bio inspired Methods and y-axis represents the Response time. From the above graph, it is well clear that A-BAT algorithm has Less Response Time in the crowdsourcing Environment compared with other algorithms. Then we

Fig.5. Comparison between the proposed methods Cost with ABC and BAT Algorithm

• VIII. Conclusion and Future Work

Using crowd optimization algorithms, Optimization select; optimization joins, and finds out the Optimized product using the A-BAT algorithm. Analyze the customer requirements evaluation process implemented based on the customer analysis. Our research on each simulated and real crowd validates the effectiveness of our question optimizer and validates our value model and latency model. In this paper, an efficient A-BAT algorithm is proposed, our future algorithm used to develop the performance of basic ABC and BAT algorithms. Experimental results have shown that, this algorithm improves convergence speed and accuracy. The suggested A-BAT algorithm performed extremely well. In the upcoming days, we might desire to study the way to incorporate correlations between select/join conditions into the optimizer for compound queries, and that we additionally arrange to extend CROWDOP to support a lot of advanced SQL operators, such as to sort and aggregation.