Browsing by Author "Tosun, Umut"

Now showing 1 - 6 of 6

Distributed Database Design: A Case Study
(2014) Tosun, Umut
Data Allocation is an important problem in Distributed Database Design. Generally, evolutionary algorithms are used to determine the assignments of fragments to sites. Data Allocation Algorithms should handle replication, query frequencies, quality of service (QoS), cite capacities, table update costs, selection and projection costs. Most of the algorithms in the literature attack one or few components of the problem. In this paper, we present a case study considering all of these features. The proposed model uses Integer Linear Programming for the formulation of the problem. (C) 2014 The Authors. Published by Elsevier B.V.
A New Recombination Operator for the Genetic Algorithm Solution of the Quadratic Assignment Problem
(2014) Tosun, Umut
The Quadratic Assignment Problem (QAP) is a well known combinatorial optimization problem with a diverse set of applications. It can be transformed into many problems such as the travelling salesman, weapon target assignment, and query optimization in distributed databases. Exhaustive search methods are inadequate to solve large data sets. Genetic algorithms and tabu search meta-heuristics may provide near optimal solutions for large QAP instances taking a reasonable time to complete. In this paper, we present a new recombination operator based on Order-1 crossover algorithm. The suggested approach runs quick sort partitioning algorithm to generate different chromosomes from partitions. The minimum cost partition produces offsprings with the other chromosome. The proposed approach shows outstanding performance especially for instance sizes smaller than 50 with respect to the optimal results proposed in QAPLIB. (C) 2014 Published by Elsevier B.V.
A New Set of Pivot Elimination Schemes for Increasing the Query Performance
(2016) Tosun, Umut; AAH-9472-2020
M-Tree, Slim-Tree, DF-Tree, and Omni-Tree are some of the popular dynamic structures which can grow incrementally by splitting overflowed nodes, and adding new levels to the tree very much like the B-tree variants. Unfortunately, they have been shown to perform very poorly compared to flat structures such as AESA, LAESA, Spaghettis, and Kvp that use a fixed set of global pivots. HKvp index structure is an extension of Kvp allowing the elimination of pivots as well as the database objects. The number of pivots can be easily increased to provide more selectivity and query performance. However, there is an optimum number of pivots for a given query radius, and using too many pivots increases the costs of queries and index initialization. In this paper, a new set of pivot elimination mechanisms is proposed to determine the right number of pivots for different query radii. The suggested pivot elimination schemes perform significant cost reduction in terms of number of distance computations, and they estimate the drop rate value for HKvp on query time.
A Novel Indexing Scheme for Similarity Search in Metric Spaces
(2015) Tosun, Umut; AAH-9472-2020
Sparse spatial selection (SSS) allows insertions of new database objects and dynamically promotes some of the new objects as pivots. In this paper, we argue that SSS has fundamental problems that result in poor query performance for clustered or otherwise skewed distributions. Real datasets have often been observed to show such characteristics. We show that SSS has been optimized to work for a symmetrical, balanced distribution and for a specific radius value. Our main contribution is offering a new pivot promotion scheme that can perform robustly for clustered or skewed distributions. We show that our new indexing scheme performs significantly better than tree based dynamic structures while having lower insertion costs. (C) 2015 Elsevier B.V. All rights reserved.
On the Performance of Parallel Hybrid Algorithms for the Solution of the Quadratic Assignment Problem
(2015) Tosun, Umut; AAH-9472-2020
The quadratic assignment problem (QAP) is a combinatorial optimization problem, which is computationally demanding, and considered to be NP-hard. Therefore, the problem cannot be solved in polynomial time. The known sequential algorithms can solve small problem instances within long computational times; moreover, parallelization may provide only a linear speed-up. Near-optimal solutions can be obtained in feasible times using heuristics like genetic algorithms and tabu search. The QAP algorithms can be modified to solve various problems like the travelling salesman problem, the data allocation problem, and the file allocation problem. In this paper, a parallel hybrid algorithm (PHA) with three stages was proposed. In the first stage, a genetic algorithm was used to obtain a high quality seed. Later, a diversification phase was run on the initial seed. Finally, a robust tabu search was run on the intermediate solution to find a near-optimal result. Parallel computing was used to increase the seed quality, and a considerable speed-up was obtained in the diversification phase of the tabu search. The QAPLIB benchmark instances were used to conduct the experiments. The PHA is quite competitive with respect to the best-performing algorithms in the literature in terms of solution quality and execution time. It achieves results on average within 0.05% of the best solutions given in the QAPLIB. The PHA was able to solve even the largest problem instance size of 256 within 11 h, and with a higher accuracy than the best-known solutions. It was also observed that the solution quality improved considerably especially for larger instances, when the degree of parallelism increased. (C) 2014 Elsevier Ltd. All rights reserved.
Policy Misuse Detection in Communication Networks with Hidden Markov Models
(2014) Tosun, Umut
With the recent advances in computer networking applications, Intrusion Detection Systems (IDS) are widely used to detect the malicious connections in computer networks. IDS provide a high level security between organizations while preventing misuses and intrusions in data communication through internet or any other network. Adherence to network usage policies is crucial since a system or network administrator needs to be informed whether the information is compromised, if the resources are appropriately used or if an attacker exploits a comprised service. Server flow authentication via protocol detection analyzes penetrations to a communication network. Generally, port numbers in the packet headers are used to detect the protocols. However, it is easy to re-map port numbers via proxies and changing the port number via compromised host services. Using port numbers may be misleading for a system administrator to understand the natural flow of communications through network. It is also difficult to understand the user behavior when the traffic is encrypted since there is only packet level information to be considered. In this paper, we present a novel approach via Hidden Markov Models to detect user behavior in network traffic. We perform the detection process on timing measures of packets. The results are promising and we obtained classification accuracies between %70 and %100. (C) 2014 Published by Elsevier B.V.