DSpace Collection:
http://hdl.handle.net/10889/24
2020-01-06T11:18:33ZEffective algorithms and improved high-volume data analysis techniques
http://hdl.handle.net/10889/12795
Title: Effective algorithms and improved high-volume data analysis techniques
Authors: Λιαπάκης, Ξενοφών
Abstract: Behind the buzzword big data lays a challenge which is very true and very important both for
academia and industry. Efficiently handling an overwhelming volume of data, possibly coming from a large number of sources abiding to vastly different functionality protocols, coding conventions, sampling rates, and quality standards, is very important from engineering, algorithmic, economic, and even social perspective. However, no matter how challenging the technical part is, it is nonetheless only a fraction of the entire challenge. This happens because harnessing new, non-trivial knowledge from literally an entire data ocean is even more challenging given the additional constraint that the value of this newly obtained knowledge must at least equal the total extraction it, including factors such as power, storage cost, equipment procurements, and data collection cost. And this is the marginal case, which cannot be maintained indefinitely. On the contrary, the knowledge value must be a multiple of the total effort cost in order for any big data pipeline to be viable from a business perspective.
The twofold objective of this PhD dissertation is to:
To explore the applications of parallelism to accelerating critical computations in challenging
problems from various fields. One very concrete example comes from the emerging field of
computational combinatorics. Specifically, a novel graph structural resilience metric based
on triangles and paths is proposed. Since this metric is purely structural, namely function
oblivious, it can be applied to virtually any graph as long as the patterns it relies on have a
physical meaning.
To show how parallelism can be part of very efficient and wide applicable computational
kernels, such as those found in the BLAS library for basic linear algebra operations, which
can be applied to various engineering and financial problems, the proposed algorithms are
examined from a computational kernel perspective. It is shown that they can be applied to
other problems as well, increasing thus their usefulness.Efficient wireless power transfer protocols in rechargeable sensor networks
http://hdl.handle.net/10889/12643
Title: Efficient wireless power transfer protocols in rechargeable sensor networks
Authors: Μάδια, Αντελίνα
Abstract: In this thesis, we study problems related to the efficient energy management of sensor networks and propose protocols that exploit the Wireless Power Transfer (WPT) technology using magnetic resonant coupling. A common, realistic assumption of all problems that we investigate is that the amount of available energy supplies is finite; hence, it is crucial to manage it in the most efficient way in order to prolong the network lifetime, and achieve other required network properties as well. The problems on which we focus in this thesis can be classified in two main categories. In the first one, special network entities (called chargers) are required to store large amount of energy supplies and appropriately transfer it to the network devices. In the second category, we study different network models where no special devices are used for the energy management; in contrast, the ordinary network devices are capable to charge each other in a peer-to-peer manner.
In particular, we first study wireless rechargeable sensor networks using multiple mobile chargers. In such a setting, the most crucial questions that we aim to answer are the following two. How can the mobile chargers coordinate in order to partition the network area amongst them in fair way, based on the energy supplies they have? Further, what trajectory should each of them follow in order to traverse its assigned subregion and charge the sensor nodes therein? To answer these questions, we propose both centralized and distributed coordination solutions that exploit different levels of knowledge. Moreover, we propose a hierarchical collaborative charging scheme where the chargers are partitioned in two types, the mobile chargers, which are responsible for replenishing the energy of the sensor nodes, and the special chargers, which are responsible for recharging the mobile chargers. In this setting, we investigate how the special chargers must coordinate with each other, which trajectories they should follow, and how much energy must be transferred to each mobile charger. We also focus on the problem of selecting the appropriate power of a single static charger over time in mobile ad hoc networks in order to adapt to the mobility and energy consumption characteristics of the mobile nodes, as these are revealed in an online manner. Finally, we study the problem of designing interaction protocols for networks that consist of computationally weak devices, which are able to exchange energy in a peer-to-peer manner, thus eliminating the need for special entities, like the chargers. The objective is to let the devices distributively construct specific network structures (such as star and tree networks) and achieve appropriate energy distributions. For each of these problems we propose and analyze the properties (both theoretically and experimentally) of various protocols, which utilize different levels of knowledge about the network.Design, development and evaluation on decision making algorithms, based on innovative smart energy networks
http://hdl.handle.net/10889/12498
Title: Design, development and evaluation on decision making algorithms, based on innovative smart energy networks
Authors: Μαμουνάκης, Ιωάννης
Abstract: The use of renewable energy sources across Europe and many other parts of the world has been largely supported by government and economic incentives in recent years. Taking into account European Union climate change legislation requiring EU Member States to produce 20% of their electricity from renewable sources by the year 2020, it is clear that few European countries will be able to achieve this objective. The only way in which the majority of EU countries can get closer to the goal is to make use of excess capacity from domestic Renewable Energy Sources (RES). This thesis examined the need to involve small and medium-sized producers and consumers in the energy market with the aim both of economic benefit and of changing their energy behavior. Initially, the current techniques / algorithms were studied regarding the grouping of producers and consumers as well as the pricing process. It was proposed to create a new smart grid architecture with the contribution of a new aggregator that organizes all small and medium-sized producer-consumers in clusters that act on the same policy. Studies have been made using already known algorithms (spectral, genetic, and adaptive) to find the appropriate producer-consumer cluster that will reduce their energy costs.
The study was enriched with the use of prediction techniques, offering even greater accuracy in the end result. Clustering methods based on correlation were then proposed to find the appropriate producer / consumer groups to serve current demand for both real-time and post-day markets. The pricing of the energy supply on the market was an important part of this dissertation, for which purpose the following algorithms were proposed.
Initially, a pricing algorithm was developed and implemented in flexible markets for the economic benefits and smooth operation of the market. An algorithm of producer-consumer grouping in smart power networks was then studied and implemented with the aim of reducing consumption and changing energy behavior. All of the above-mentioned technical algorithms were evaluated using experiments from anonymous user data over the last five years. The integration of the algorithms into two platforms VIMSEN Decision Support System (VIMSEN-DSS) platform and the Researchers Algorithm Toolkit (RAT) platform has demonstrated both the correct operation of the outputs and the smooth operation of the proposed techniques within an integrated information system.Rank aggregation of partial rankings : algorithms and applications
http://hdl.handle.net/10889/12329
Title: Rank aggregation of partial rankings : algorithms and applications
Authors: Κριμπάς, Γεώργιος
Abstract: In the last few years, more and more applications on the internet exploit the power that users (or agents) have, in order to rate, grade, vote, review, and rank sets of services, local businesses, software, etc. (or, more generally, alternatives). Of course, the aim of these applications is to provide better information, and services to the general public. Put it simply, users have knowledge upon different aspects, and internet applications want to use this knowledge which needs to be aggregated. Voting and in general Social Choice Theory from Microeconomics equips us with methods and procedures in order to aggregate this information.
In this thesis, we study the application of aggregation methods upon rankings in order to recover a ground truth. We make use variations of simple voting rules that are very well-known in Social Choice Theory, which help us aggregate small in size partial or incomplete rankings, into a global one. An immediate application comes from peer grading in Massive Open Online Courses (MOOCs). These platforms are used extensively from students all around the world, and in most cases, the grading is performed by the students that are enrolled in a course themselves. The idea behind peer grading in MOOCs is that every student gets a small in size bundle of exam papers (of other students) to grade with the restriction that no student will get its exam paper to grade. We are particularly interested in grading where students do not use numerical scores, but they provide a ranking of the exam papers in their bundle from the best to the worst. Then voting rules are applied so as to aggregate these rankings in order to come up with a full ranking of all exam papers. The efficiency objective requires this full ranking to be as close as possible to the ground truth. We prove that a very simple voting rule, specifically Borda count, can recover a large fraction of the true ranking.
We also define and study a large class of simple aggregation rules, which we call Type-Ordering Aggregation Rules. We present a theoretical framework for assessing the performance of each member of this class. We infer statistical information about the grading behaviour of students and then our framework can serve as an optimization toolkit for selecting the optimal Type-Ordering Aggregation Rule. This requires an exact solution to an instance of the feedback arc set problem which, albeit NP-hard in general, can be solved exactly for the instances that do arise in practice. Our theoretical framework allows us to obtain a series of results. We prove that Borda rule is the optimal Type-Ordering Aggregation Rule when students act as perfect graders, and its performance is always extremely close to optimality. Furthermore, the decision of the optimal aggregation rule strongly depends on the information about the grading behaviour of the students.
Finally, we design and analyse algorithms for the aggregation of incomplete rankings that are useful in rating applications. Applications of this kind can be found in recommendation systems and platforms. Here, every user can provide us with an incomplete ranking of the restaurants, hotels, or movies that she has used as a product. Then we design algorithms to find the best scoring rule in order to aggregate the individual rankings. The assumption here is that we have some knowledge about the correct comparisons a priori, which are used as constraints. Given these constraints and the individual rankings, the optimisation problem is to find the best positional scoring rule OptPSR) which is NP-hard.
We design an algorithm which is exact and solves OptPSR in time that depends exponentially only on the parameter d, where d is the number of alternatives that each user ranks. Hence, our algorithm runs in polynomial time when d is constant. Then we seek to approximately solve OptPSR, and we prove that a simple combination of t-approval voting rules yields a 1/d-approximate solution. Then, we design a more sophisticated approximation algorithm, which is parameterized by a positive integer k and yields a k/d-approximate solution. Last, we prove that OptPSR is hard to approximate and present an explicit inapproximability bound of 23/24.
In addition to theoretical results, the thesis contains simulation and experiments that aim to test the simplicity and the performance of our algorithms in practical scenarios. We use synthetic data that we have generated, and more importantly, we have designed real-world experiments (or field experiments), in which we managed to extract specific information from real users in order to create datasets that we use in extensive simulations to verify or complement our theoretical results.