University of Patras
Αποτελεσματικοί αλγόριθμοι και δομές δεδομένων με εφαρμογές στην ανάκτηση πληροφορίας και στις τεχνολογίες διαδικτύου
Abstract
dc:descriptionIn this dissertation we take an in-depth look at the use of effective and efficient data structures and algorithms in the fields of data mining and web technologies. The main goal is to develop algorithms based on appropriate data structures, in order to improve the performance at all levels of web applications. In the first chapter the reader is introduced to the main issues studied dissertation. In the second chapter, we propose novel randomized versions of the splay trees. We have evaluated the practical performance of these structures in comparison with the original version of splay trees and with their log log n-competitive variations, in the application field of compression. Moreover, we show that the Chain Splay tree achieves O(logn) worst-case cost per query. In order to evaluate performance, we utilize plain splay trees, the log log n-competitive variations, the proposed randomized version with the Chain Splay technique to compress data. It is observed experimentally that the compression achieved in the case of the log log n-competitive technique is, as expected, more efficient than the one of the plain splay trees. The third chapter focuses on hotlinks assignment techniques. Enhancing web browsing experience is an open issue frequently dealt using hotlinks assignment between webpages, shortcuts from one node to another. Our aim is to provide a novel, more efficient approach to minimize the expected number of steps needed to reach expected pages when browsing a website. We present a randomized algorithm, which combines the popularity of the webpages, the website structure, and for the first time to the best authors’ knowledge, the similarity of context between pages in order to suggest the placement of suitable hotlinks. We verify experimentally that users need less page transitions to reach expected information pages when browsing a website, enhanced using the proposed algorithm. In the fourth chapter we investigate the problem of web personalization. The explosive growth in the size and use of the World Wide Web continuously creates new great challenges and needs. The need for predicting the users’ preferences in order to expedite and improve the browsing though a site can be achieved through personalizing of the Websites. Recommendation and personalization algorithms aim at suggesting WebPages to users based on their current visit and past users’ navigational patterns. The problem that we address is the case where few WebPages become very popular for short periods of time and are accessed very frequently in a limited temporal space. Our aim is to deal with these bursts of visits and suggest these highly accessed pages to the future users that have common interests. Hence, in this paper, we propose a new web personalization technique, based on advanced data structures. The data structures that are used are the Splay tree (1) and Binary heaps (2). We describe the architecture of the technique, analyze the time and space complexity and prove its performance. In addition, we compare both theoretically and experimentally the proposed technique to another approach to verify its efficiency. Our solution achieves O(P2) space complexity and runs in k log P time, where k is the number of pages and P the number of categories of WebPages. Extending this algorithm, we propose an algorithm which efficiently detects bursts of visits to webpages. As an increasing number of Web sites consist of multiple pages, it is more difficult for the visitors to rapidly reach their own target. This results in an urgent need for intelligent systems that effectively support the users’ navigation to high demand Web content. In many cases, due to specific conditions, web pages become very popular and receive excessively large number of hits. Therefore, there is a high probability that these web pages will be of interest to the majority of the visitors at a given time. The data structure that is used for the purposes of the recommendation algorithm is the Splay tree. We describe the architecture of the technique, analyze the time and space complexity and show its performance. The dissertation’s last chapter elaborates on how to use clustering for the evaluation of a software system’s maintainability according to the ISO/IEC-9126 quality standard. More specifically it proposes a methodology that combines clustering and multicriteria decision aid techniques for knowledge acquisition by integrating groups of data from source code with the expertise of a software system’s evaluators. A process for the extraction of elements from source code and Analytical Hierarchical Processing for assigning weights to these data are provided; k-Attractors clustering algorithm is then applied on these data, in order to produce system overviews and deductions. The methodology is evaluated on Apache Geronimo, a large Open Source Application Server, results are discussed and conclusions are presented together with directions for future work.
Degree
thesis:*- Grantor dc:publisher
- University of Patras
- Year dc:date
- 2011
Author and committee
dc:creator, dc:contributor.*- Authors dc:creator
-
- Antoniou, Dimitrios
- Αντωνίου, Δημήτριος
Subjects
dc:subject × 16- Αλγόριθμοι
- Δομές δεδομένων
- Ανάκτηση πληροφορίας
- Τεχνολογίες διαδικτύου
- Algorithms
- Data structures
- Data mining
- Web technologies
- Φυσικές Επιστήμες
- Επιστήμη Ηλεκτρονικών Υπολογιστών και Πληροφορική
- Επιστήμες Μηχανικού και Τεχνολογία
- Επιστήμη Ηλεκτρολόγου Μηχανικού, Ηλεκτρονικού Μηχανικού, Μηχανικού Η/Υ
- Natural Sciences
- Computer and Information Sciences
- Engineering and Technology
- Electrical Engineering, Electronic Engineering, Information Engineering
Rights
- Language dc:language
- gre
Identifiers
dc:identifier.*- Identifier
- 10.12681/eadd/33573