Skip to main content
main-content
Top

About this book

This volume contains a subset of the papers presented at the 10th Panhellenic Conference in Informatics (PCI 2005), which took place at the City of Volos, Greece, during November 11–13, 2005. After an international call for papers, 252 full papers were submitted. The number of the submitted papers constitutes a record number for the conf- ence and reveals its growing dynamics. The authors represented universities and institutes from the following countries: Algeria, Bulgaria, China, Cyprus, Czech Republic, Finland, Greece, The Netherlands, Hungary, Italy, Japan, Korea, The Kingdom of Saudi Arabia, Lebanon, Lithuania, Malaysia, Poland, Romania, Spain, Taiwan, Turkey, Ukraine, UK, and USA. Of the submitted papers, 81 were accepted for inclusion in this volume, giving an acceptance ratio of appr- imately 32. 2%. The papers are classi?ed into 17 thematic sections as follows: – data bases and data mining – algorithms and theoretical foundations – cultural and museum information systems – Internet-scale software/information systems – wearable and mobile computing – computer graphics, virtual reality and visualization – AI, machine learning and knowledge bases – languages, text and speech processing – bioinformatics – software engineering – educational technologies – e-business – computer and sensor hardware and architecture – computer security – image and video processing – signal processing and telecommunications – computer and sensor networks We would like to thank all the ProgramCommittee members and the additional reviewers for devoting time, e?ort and expertise so bounteously.

Table of Contents

Frontmatter

Data Bases and Data Mining

Closest Pair Queries with Spatial Constraints

Given two datasets

$\mathcal{D}_{A}$

and

$\mathcal{D}_{B}$

the closest-pair query (CPQ) retrieves the pair (

a

,

b

), where

$a \epsilon \mathcal{D}_{A}$

and

$b \epsilon \mathcal{D}_{B}$

, having the smallest distance between all pairs of objects. An extension to this problem is to generate the

k

closest pairs of objects (

k

-CPQ). In several cases spatial constraints are applied, and object pairs that are retrieved must also satisfy these constraints. Although the application of spatial constraints seems natural towards a more focused search, only recently they have been studied for the CPQ problem with the restriction that

$\mathcal{D}_{A}$

=

$\mathcal{D}_{B}$

. In this work we focus on constrained closest-pair queries (CCPQ), between two distinct datasets

$\mathcal{D}_{A}$

and

$\mathcal{D}_{B}$

, where objects from

$\mathcal{D}_{A}$

must be enclosed by a spatial region

R

. A new algorithm is proposed, which is compared with a modified closest-pair algorithm. The experimental results demonstrate that the proposed approach is superior with respect to CPU and I/O costs.

Apostolos N. Papadopoulos, Alexandros Nanopoulos, Yannis Manolopoulos

Database Support for Data Mining Patterns

The need of extracting useful knowledge from large collections of data has led to a great development of data mining systems and techniques. The results of data mining are known as patterns. Patterns can also be found in other scientific areas, such as biology, astronomy, mathematics etc. Today requirements impose the need for a system that efficiently manipulates complex and diverse patterns. In this work, we study the problem of the efficient representation and storage of patterns in a so-called pattern-base Management System. Towards this aim we examine three well known models from the database domain, the relational, the object-relational and the semi-structured (XML) model. The three alternative models are presented and compared based on criteria like generality, extensibility and querying effectiveness. The comparison shows that the semi-structure representation is more appropriate for a pattern-base.

Evangelos Kotsifakos, Irene Ntoutsi, Yannis Theodoridis

Visual Techniques for the Interpretation of Data Mining Outcomes

The visual senses for humans have a unique status, offering a very broadband channel for information flow. Visual approaches to analysis and mining attempt to take advantage of our abilities to perceive pattern and structure in visual form and to make sense of, or interpret, what we see. Visual Data Mining techniques have proven to be of high value in exploratory data analysis and they also have a high potential for mining large databases. In this work, we try to investigate and expand the area of visual data mining by proposing a new 3-Dimensional visual data mining technique for the representation and mining of classification outcomes and association rules.

Categories:

I.2.4, I.2.6

Research Paper:

Data Bases, Work Flow and Data mining

Ioannis Kopanakis, Nikos Pelekis, Haralampos Karanikas, Thomas Mavroudkis

Towards In-Situ Data Storage in Sensor Databases

The advances in wireless communications along with the exponential growth of transistors per integrated circuit lead to a rapid evolution of

Wireless Sensor Devices (WSDs)

, that can be used for monitoring environmental conditions at a high fidelity. Following the current trends, WSDs are soon expected to automatically and continuously collect vast amounts of temporal data. Organizing such information in centralized repositories at all times will be both impractical and expensive. In this paper we discuss the challenges from storing sensor readings

In-situ

(at the generating sensor). This creates a network of tiny databases as opposed to the prevalent model of a centralized database that collects readings from many sensors. We also discuss some of the inherent problems of such a setting, including the lack of efficient distributed query processing algorithms for handling

temporal

data and the lack of efficient access methods to locally store and retrieve large amounts of sensor data. The presented solutions are in the context of the

RISE (Riverside Sensor)

hardware platform, which is a wireless sensor platform we developed for applications that require storing in-situ many MBs of sensor readings.

D. Zeinalipour-Yazti, V. Kalogeraki, D. Gunopulos, A. Mitra, A. Banerjee, W. Najjar

Algorithms and Theoretical Foundations

A Primal-Dual Algorithm for Online Non-uniform Facility Location

In the online version of Facility Location, the demand points arrive one at a time and must be irrevocably assigned to an open facility upon arrival. The objective is to minimize the sum of facility and assignment costs. We present a simple primal-dual deterministic algorithm for the general case of non-uniform facility costs. We prove that its competitive ratio is no greater than 4log(

n

+1) + 2, which is close to the lower bound of

$\Omega(\frac{log n}{log log n})$

.

Dimitris Fotakis

Routing and Wavelength Assignment in Generalized WDM Tree Networks of Bounded Degree

The increasing popularity of all-optical networks has led to extensive research on the routing and wavelength assignment problem, also termed as the

Routing and Path Coloring problem

(RPC). Here we present a polynomial time algorithm that solves RPC exactly in

generalized tree networks

of bounded degree. This new topology is of practical interest since it models tree-like backbone networks connecting bounded-size LANs of any form. Tree-like backbone structure is very common in practice and bounded size LANs is a reasonable assumption, since LANs are by nature networks unable to sustain a large number of hosts.

Stratis Ioannidis, Christos Nomikos, Aris Pagourtzis, Stathis Zachos

Maximum-Size Subgraphs of P4-Sparse Graphs Admitting a Perfect Matching

In this paper, we address the problem of computing a maximum-size subgraph of a

P

4

-sparse graph which admits a perfect matching; in the case where the graph has a perfect matching, the solution to the problem is the entire graph. We establish a characterization of such subgraphs, and describe an algorithm for the problem which for a

P

4

-sparse graph on

n

vertices and

m

edges, runs in

O

(

n

+

m

) time and space. The above results also hold for the class of complement reducible graphs or cographs, a well-known subclass of

P

4

-sparse graphs.

Stavros D. Nikolopoulos, Leonidas Palios

Boundary Labelling of Optimal Total Leader Length

In this paper, we consider the

leader length minimization problem

for

boundary labelling

, i.e. the problem of finding a legal leader-label placement, such that the total leader length is minimized. We present an

O

(

n

2

log

3

n

) algorithm assuming

type-opo

leaders

(rectilinear lines with either zero or two bends) and labels of uniform size which can be attached to all four sides of rectangle

R

. Our algorithm supports

fixed

and

sliding ports

, i.e., the point where each leader is connected to the label (referred to as

port

) may be fixed or may slide along a label edge.

M. A. Bekos, M. Kaufmann, K. Potika, A. Symvonis

Successive Linear Programs for Computing All Integral Points in a Minkowski Sum

The computation of all integral points in Minkowski (or vector) sums of convex lattice polytopes of arbitrary dimension appears as a subproblem in algebraic variable elimination, parallel compiler code optimization, polyhedral combinatorics and multivariate polynomial multiplication. We use an existing approach that avoids the costly construction of the Minkowski sum by an incremental process of solving Linear Programming (LP) problems. Our main contribution is to exploit the similarities between LP problems in the tree of LP instances, using duality theory and the two-phase simplex algorithm. Our public domain implementation improves substantially upon the performance of the above mentioned approach and is faster than

porta

on certain input families; besides, the latter requires a description of the Minkowski sum which has high complexity. Memory consumption limits commercial or free software packages implementing multivariate polynomial multiplication, whereas ours can solve all examined data, namely of dimension up to 9, using less than 2.7 MB (before actually outputting the points) for instances yielding more than 3 million points.

Ioannis Z. Emiris, Kyriakos Zervoudakis

The Contribution of Game Theory to Complex Systems

We address several recent developments in non-cooperative as well as evolutionary game theory, that give a new viewpoint to Complex Systems understanding. In particular, we discuss notions like the anarchy cost, equilibria formation, social costs and evolutionary stability. We indicate how such notions help in understanding Complex Systems behaviour when the system includes selfish, antagonistic entities of varying degrees of rationality. Our main motivation is the Internet, perhaps the most complex artifact to date, as well as large-scale systems such as the high-level P2P systems, where where the interaction is among humans, programmes and machines and centralized approaches cannot apply.

Spyros Kontogiannis, Paul Spirakis

Estimated Path Selection for the Delay Constrained Least Cost Path

The development of efficient Quality of Service (QoS) routing algorithms in high speed networks is very difficult since divergent services require various quality conditions. If the QoS parameter we concern is to measure the delay on that link, then the routing algorithm obtains the Least Delay (LD) path. Meanwhile, if the parameter is to measure of the link cost, then it calculates the Least Cost (LC) path. The Delay Constrained Least Cost (DCLC) path problem of the mixed issues on LD and LC has been shown to be NP-hard. The path cost of LD path is relatively more expensive than that of LC path, and the path delay of LC path is relatively higher than that of LD path in DCLC problem. In this paper, we propose Estimated Path Selection (EPS) algorithm for the DCLC problem and investigate its performance. It employs a new parameter which is probabilistic combination of cost and delay. We have performed empirical evaluation that compares our proposed EPS with the DCUR in various network situations. It significantly affects the performance that the normalized surcharge is improved up to about 105%. The time complexity is

O

(

l

+

n

log

n

) which is comparable to well-known previous works.

Moonseong Kim, Young-Cheol Bang, Hyunseung Choo

Finding Feasible Pathways in Metabolic Networks

Recent small-world studies of the global structure of metabolic networks have been based on the shortest-path distance. In this paper, we propose new distance measures that are based on the structure of feasible metabolic pathways between metabolites. We argue that these distances capture the complexity of the underlying biochemical processes more accurately than the shortest-path distance. To test our approach in practice, we calculated our distances and shortest-path distances in two microbial organisms,

S. cerevisiae

and

E. coli

. The results show that metabolite interconversion is significantly more complex than was suggested in previous small-world studies. We also studied the effect of reaction removals (gene knock-outs) on the connectivity of the

S. cerevisiae

network and found out that the network is not particularly robust against such mutations.

Esa Pitkänen, Ari Rantanen, Juho Rousu, Esko Ukkonen

One-Dimensional Finger Searching in RAM Model Revisited

In the particular case we have insertions/deletions at the tail of a given set S of

n

one-dimensional elements, we present a simpler and more concrete algorithm than the one presented in [12] achieving the same worst-case upper bounds for fin ger searching queries in

$\Theta(\sqrt{{\rm log} d/ {\rm log log} d} )$

time. Furthermore, in the general case where we have insertions/deletions anywhere we present a new simple randomized algorithm achieving the same time bounds with high probability.

S. Sioutas, Y. Panagis, E. Theodoridis, A. Tsakalidis

How to Place Efficiently Guards and Paintings in an Art Gallery

In the art gallery problem the goal is to place guards (as few as possible) in a polygon so that a maximal area of the polygon is covered. We address here a closely related problem: how to place paintings and guards in an art gallery so that the total value of guarded paintings is a maximum. More formally, a simple polygon is given along with a set of paintings. Each painting, has a length and a value. We study how to place at the same time: i) a given number of guards on the boundary of the polygon and ii) paintings on the boundary of the polygon so that the total value of guarded paintings is maximum. We investigate this problem for a number of cases depending on: i) where the guards can be placed (vertices, edges), ii) whether the polygon has holes or not and iii) whether the goal is to oversee the placed paintings (every point of a painting is seen by at least one guard), or to watch the placed paintings (at least one point of a painting is seen by at least one guard). We prove that the problem is NP-hard in all the above cases and we present polynomial time approximation algorithms for all cases, achieving constant ratios.

Christodoulos Fragoudakis, Euripides Markou, Stathis Zachos

Cultural and Museum Information Systems

Virtual Reality Systems and Applications: The Ancient Olympic Games

This paper presents the virtual reality systems, interaction devices and software used at the Foundation of the Hellenic World (FHW). The applications that FHW has produced, associated with the Olympic Games in ancient Greece, are then detailed. The separate virtual reality shows are presented in terms of interactivity and educational value. Technical aspects of the productions are explained, with an emphasis on surround screen projection environments. These techniques were mostly utilized in the recent production regarding the ancient Olympic Games, where much effort has been made to recreate the feeling of the games and help the user/spectator be an interacting part of the edutainment activity.

A. Gaitatzes, D. Christopoulos, G. Papaioannou

Auction Scenarios of Cultural Products over the WWW

Nowadays, every country faces the necessity of the demonstration of its cultural heritage over the WWW due to its increasing role in national economy through tourism. This paper studies ways of achieving this goal through electronic auctions over the WWW. More specifically, we present an electronic auction system along with several brokerage scenarios depending on different customer needs for the mediation of transactions and product searching.

D. K. Koukopoulos

Exploring Cultural Information Interaction Design: A Case Study of a Multimedia Exhibition Based on Customizable User Interfaces

The study of cultural content promotion methods, through an interdisciplinary approach, suggests new ways of information management, as well as new representation practices, which constitute the basis of new negotiation methodologies. Cultural Information Systems through a variety of possible interfaces, formed according to each given promotion strategy, suggest the study, within a broader research field, of new ways of information structure management, introducing new kinds of knowledge formation and consequently new interpretation tools of awareness. As a result of the interdisciplinary approach regarding cultural heritage management and subsequently of the possibility of parameterization regarding the forms of scientific fields and the practices of the specialities involved, a new design field is defined, the Cultural Information Interaction Design field. Under the framework of Cultural Information Interaction Design, this paper presents a case study of a multimedia exhibition implementing a method for interactive exhibit design based on Customizable User Interfaces, depended on given design problems and focused on parameterized sensorial approaches and presentation techniques. The exhibition design strategy was focused on the design of interactive exhibits with a sensorial emphasis on tangibility, proposing in that way novel forms of cultural representation practices.

George Pehlivanides

Using Personal Digital Assistants (PDAs) to Enhance the Museum Visit Experience

This paper addresses the design and evaluation of a Personal Digital Assistants’ (PDAs) application to enhance the visit experience at the Museum/Library Stratis Eleftheriadis Teriade in Lesvos, Greece. The paper reviews the use of new technologies to enhance Museum visit experiences, and focuses on the use of PDAs for providing information and interpretation, keeping visitors interest and attention, as well as promoting various museum facilities. The paper describes the design process of the "Fables" application with the use of NaviPocket v. 2.4 by ORPHYS SYSTEMES (an authoring tool for PDA applications), includes an evaluation of the application and the authoring tool’s effectiveness, and concludes with directions to further work on this area of research.

Katy Micha, Daphne Economou

Trial Evaluation of Wireless Info-communication and Indoor Location-Based Services in Exhibition Shows

Exhibition shows are essentially information exchange hubs. Their success relies on the quantity and quality of interaction of the involved parties: exhibitors, visitors, and organizers. The introduction of advanced wireless applications in the exhibition industry is a major opportunity for improving interaction and communications, thus leveraging the value proposition of exhibition services. This paper discusses the development and commercial trial of a Wireless Exhibition Guide that employs mobile terminals, wireless networks, and indoor location positioning technologies integrated through a set of software components, to introduce sophisticated information, communication, and navigation services for exhibition environments. Results indicate acceptance of the Wireless Exhibition Guide amongst the stakeholders of the exhibition industry, organizers, exhibitors, and visitors alike, and provide guidance towards the future of portable personalized location-sensitive information systems in information-rich environments, such as museums, conference centers, and art shows.

Adamantia G. Pateli, George M. Giaglis, Diomidis D. Spinellis

Internet-Scale Software/Information Systems

Epidemic Collaborative Geocast for Reliable Segmented File Sharing in Mobile Peer-to-Peer Devices

The dual problem of searching resources in the network and that of disseminating with reliability resources selectively in an infrastructureless wireless network is yet unexplored. This paper proposes an approach based on the advantages of epidemic selective dissemination through mobile Infostations. The proposed scheme combines the strengths of both proactive multicast group establishment (flexible Geocasting) and hybrid Infostation concept and attempts to fill the gap between mobility and reliable file sharing for mobile peer to peer users. This method faces the flooding problem and enables end to end reliability by forwarding requested packets to epidemically ‘selected’ mobile users in the network. Examination through simulation is performed for the response and reliability offered by epidemic collaborative Geocast method showing a significant robustness in reliable file sharing among mobile peers.

Constandinos X. Mavromoustakis, Helen D. Karatza

Investigating Factors Influencing the Response Time in ASP.NET Web Applications

Distributed systems and network applications play an important role in computer science nowadays. The most common consideration is performance, because these systems have to provide cost-effective and high availability services in the long term, thus they have to be scaled to meet the expected load. The performance of a web application is affected by several factors. The goal of our work is to analyze how some of them affect the response time. The paper presents the result of performance measurements of an ASP.NET web application. We measured the average response time of a test web application while changing the parameters of the application server. The results are analyzed using statistical methods: (i) independence tests to investigate which factors influence principally the performance, (ii) in addition certain plots and hypothesis tests to determine the distribution of the response time.

Ágnes Bogárdi-Mészöly, Zoltán Szitás, Tihamér Levendovszky, Hassan Charaf

Storing and Locating Mutable Data in Structured Peer-to-Peer Overlay Networks

Structured peer-to-peer overlay networks or Distributed Hash Tables (DHTs) are distributed systems optimized for storage and retrieval of read-only data. In this paper we elaborate on a method that allows them to manage mutable data. We argue that by altering the retrieval algorithm of DHTs, we can enable them to cope with data updates, without sacrificing their fundamental properties of scalability and fault-tolerance. We describe in detail and analyze an implementation of a Kademlia network capable of handling mutable data. Nevertheless, the corresponding protocol additions can easily be applied to any DHT design. Experimental results show that although the process of managing and propagating data updates throughout the network adds up to the total cost of the lookup operation, the extra network utilization can be exploited in favor of overlay resilience to random node joins and failures.

Antony Chazapis, Nectarios Koziris

Performance Analysis of Overheads for Matrix – Vector Multiplication in Cluster Environment

This paper presents the basic parallel implementation and a variation for matrix – vector multiplication. We evaluated and compared the performance of the two implementations on a cluster of workstations using Message Passing Interface (MPI) library. The experimental results demonstrate that the basic implementation achieves lower performance than the other variation. Further, we analyzed the several classes of overheads contribute to lowered performance of the basic implementation. These analyses have identified cost of reading of data from disk and communication cost as the primary factors affecting performance of the basic parallel matrix – vector implementation. Finally, we present a performance model for estimating the performance of two proposed matrix – vector implementations on a cluster of heterogeneous workstations.

Panagiotis D. Michailidis, Vasilis Stefanidis, Konstantinos G. Margaritis

Wearable and Mobile Computing

Middleware for Building Ubiquitous Computing Applications Using Distributed Objects

Ubiquitous systems are characterized by multi-fold complexity, stemming mainly from the vast number of possible interactions between many heterogeneous objects and services. Devices ranging from simple everyday objects populated with sensing, actuating and communication capabilities to complex computer systems, mobile or not, are treated as reusable “components” of a dynamically changing physical/digital environment. As even an individual object with limited functionality, may present advanced behavior when grouped with others, our aim is to look at how collections of such distributed objects can collaborate and provide functionality that exceeds the sum of their parts. This paper presents GAS-OS, a middleware that supports building, configuring and reconfiguring ubiquitous computing applications using distributed objects.

Nicolas Drosos, Eleni Christopoulou, Achilles Kameas

A Suffix Tree Based Prediction Scheme for Pervasive Computing Environments

Discrete sequence modeling and prediction is a fundamental goal and a challenge for location-aware computing. Mobile client’s data request forecasting and location tracking in wireless cellular networks are characteristic application areas of sequence prediction in pervasive computing, where learning of sequential data could boost the underlying network’s performance. Approaches inspired from information theory comprise ideal solutions to the above problems, because several overheads in the mobile computing paradigm can be attributed to the randomness or uncertainty in a mobile client’s movement or data access. This article presents a new information-theoretic technique for discrete sequence prediction. It surveys the state-of-the-art solutions and provides a qualitative description of their strengths and weaknesses. Based on this analysis it proposes a new method, for which the preliminary experimental results exhibit its efficiency and robustness.

Dimitrios Katsaros, Yannis Manolopoulos

Factors That Influence the Effectiveness of Mobile Advertising: The Case of SMS

Mobile advertising takes the case of one-to-one marketing one step further, since it allows companies to send personalized offers regardless of time and space boundaries. By employing all the characteristics of one-to-one marketing and augmenting them with features such as location awareness, ubiquitous customer reach, direct response and time independence, mobile advertising is emerging as a promising advertising channel. However, little is known regarding the factors that may influence the effectiveness of a mobile advertising campaign. In this paper we attempt to identify such factors in the field of SMS advertising through an empirical survey of advertisers. Factor analysis is employed for model generation and the outcome provides four main categories that may impact the effectiveness of the SMS advertising communication: campaign strategy, targeting, creative development, and source.

Dimitris Drossos, George M. Giaglis

An Improved HCI Method and Information Input Device Using Gloves for Wearable Computers

Input to small device is become an increasingly crucial factor in development for the ever-more powerful wearable computers. In this paper, we propose glove-based human-computer interaction method and information input device for wearable computers. We suggest an easy and effective alphanumeric input algorithm using gloves and conduct efficiency test. The key factor for the proposed algorithm and device is the use of unique operator-to-key mapping method, key-to-symbol mapping method. The strong points of the proposed algorithm and device is using simple and easy algorithm. As a result, users can easily learn how to use. We list and discuss traditional algorithm and method using a glove, then describe an improved newly proposed algorithm using gloves. We conducted efficiency test with 20 subjects and compared the results with 12 similar systems. We set 11 key factors as performance evaluation parameters, and then compared performance of each system using these 11 key factors.

Jeong-Hoon Shin, Kwang-Seok Hong

Computer Graphics, Virtual Reality and Visualization

Efficient Parameterization of 3D Point-Sets Using Recursive Dynamic Base Surfaces

Modelling a three-dimensional (3D) point cloud with smooth mathematical surfaces or high-quality triangle meshes is an essential component of many applications in Computer Graphics, Visualization and Computer-Aided Design/Engineering. A vital prerequisite for that is the construction of a

parameterization

for a given 3D point-set; this problem is the focus of the present paper. The proposed method employs ideas and tools from “point-based geometric modelling” in order to construct a set of continuous surfaces locally-fitted to a point set. Then parameterization is achieved by orthogonally projecting the point set onto these surfaces.

Philip Azariadis, Nickolas Sapidis

Interactive Dynamics for Large Virtual Reality Applications

Recent commercial virtual reality shows have become very demanding in terms of interactive credibility and visual realism. In an effort to push further the immersive quality and the sense of ’being there’ in the most recent VR production of the Foundation of the Hellenic World “A Walk through Ancient Olympia”, the user, apart from virtually visiting the historical site, becomes an interacting part of the edutainment activity. Described in this paper is a new script-controlled generic dynamics system devised for heavy interactive VR applications and used in the above commercial production, which utilises the notion of force-fields and also simulates aerodynamic effects in a real-time, computationally efficient manner. The impact of the interactive dynamics system on the usability and virtual presence is also discussed, in the context of a fully immersive stereoscopic surround-screen virtual reality environment and a role-playing interactive show.

Georgios Papaioannou

A Pictorial Human Computer Interaction to Query Geographical Data

This paper proposes an extension of the Pictorial Geographical Query Language GeoPQL, that allows the user to express queries pictorially. Topological and metrics operators are already presented in a previous work. This extension refers to queries in which the user uses concepts that the system implicitly interprets and transforms. In particular, the paper adds the oriented polyline to the classic three objects (point, polyline, and polygon) and defines a set of cardinal and positional operators. In order to maintain non-ambiguity in the query’s visual representation, GeoPQL uses three different working spaces, the first for topological and metrics operators, the second for cardinal operators, and the third for positional operators.

Fernando Ferri, Patrizia Grifoni, Maurizio Rafanelli

AI, Machine Learning and Knowledge Bases

Bagging Model Trees for Classification Problems

Structurally, a model tree is a regression method that takes the form of a decision tree with linear regression functions instead of terminal class values at its leaves. In this study, model trees are coupled with bagging for solving classification problems. In order to apply this regression technique to classification problems, we consider the conditional class probability function and seek a model-tree approximation to it. During classification, the class whose model tree generates the greatest approximated probability value is chosen as the predicted class. We performed a comparison with other well known ensembles of decision trees, on standard benchmark datasets and the performance of the proposed technique was greater in most cases.

S. B. Kotsiantis, G. E. Tsekouras, P. E. Pintelas

On the Utility of Incremental Feature Selection for the Classification of Textual Data Streams

In this paper we argue that incrementally updating the features that a text classification algorithm considers is very important for real-world textual data streams, because in most applications the distribution of data and the description of the classification concept changes over time. We propose the coupling of an incremental feature ranking method and an incremental learning algorithm that can consider different subsets of the feature vector during prediction (what we call a feature based classifier), in order to deal with the above problem. Experimental results with a longitudinal database of real spam and legitimate emails shows that our approach can adapt to the changing nature of streaming data and works much better than classical incremental learning algorithms.

Ioannis Katakis, Grigorios Tsoumakas, Ioannis Vlahavas

Gossip-Based Greedy Gaussian Mixture Learning

It has been recently demonstrated that the classical EM algorithm for learning Gaussian mixture models can be successfully implemented in a decentralized manner by resorting to gossip-based randomized distributed protocols. In this paper we describe a gossip-based implementation of an alternative algorithm for learning Gaussian mixtures in which components are added to the mixture one after another. Our new Greedy Gossip-based Gaussian mixture learning algorithm uses gossip-based parallel search, starting from multiple initial guesses, for finding good components to add to the mixture in each component allocation step. It can be executed on massive networks of small computing devices, converging to a solution exponentially faster than its centralized version, while reaching the same quality of generated models.

Nikos Vlassis, Yiannis Sfakianakis, Wojtek Kowalczyk

A Knowledge Management Architecture for 3D Shapes and Applications

In this paper, we present a knowledge-based approach to 3D shape management and service composition, exploiting and extending Web Services and Semantic Web technologies. Semantic Web technology fosters semantic interoperability, while Web Services technology is utilized to construct loosely coupled components, which, combined with workflow technology enrich the processing capabilities needed for e-Science and e-Engineering. We propose an open system architecture for the formalization, processing and sharing of shape knowledge in order to efficiently support key activities: from shape creation, retrieval, post-processing and composition, to the categorization and transparent invocation of algorithms, to the automated construction and execution of complex process flows, to capturing metadata for accurate searching of shape and algorithmic resources. Two representative scenarios have been chosen, 3D shape geometry processing and 3D product development, which will demonstrate the potential of the platform in terms of establishing novel, knowledge-based and semantically enriched solutions dealing with the automation of the knowledge lifecycle.

Marios Pitikakis, Catherine Houstis, George Vasilakis, Manolis Vavalis

Using Fuzzy Cognitive Maps as a Decision Support System for Political Decisions: The Case of Turkey’s Integration into the European Union

In this paper we use Fuzzy Cognitive Maps (FCMs), a well-established Artificial Intelligence technique that incorporates ideas from Artificial Neural Networks and Fuzzy Logic, to create a dynamic model of Turkey’s course towards its integration into the European Union, after the decision of December 18, 2004, according to which in October 3, 2005, Turkey will start negotiating its access to the European Union. FCMs create models as collections of concepts and the various causal relations that exist between these concepts. The decision capabilities of the FCM structure are examined and presented using a model developed based on the beliefs of a domain expert in the political situation in Turkey & European Union. The model is examined both statically using graph theory techniques and dynamically through simulations. Scenarios are introduced and predictions are made by viewing dynamically the consequences of the corresponding actions.

Athanasios K. Tsadiras, Ilias Kouskouvelis

Languages, Text and Speech Processing

Developing a Robust Part-of-Speech Tagger for Biomedical Text

This paper presents a part-of-speech tagger which is specifically tuned for biomedical text. We have built the tagger with maximum entropy modeling and a state-of-the-art tagging algorithm. The tagger was trained on a corpus containing newspaper articles and biomedical documents so that it would work well on various types of biomedical text. Experimental results on the Wall Street Journal corpus, the GENIA corpus, and the PennBioIE corpus revealed that adding training data from a different domain does not hurt the performance of a tagger, and our tagger exhibits very good precision (97% to 98%) on all these corpora. We also evaluated the robustness of the tagger using recent MEDLINE articles.

Yoshimasa Tsuruoka, Yuka Tateishi, Jin-Dong Kim, Tomoko Ohta, John McNaught, Sophia Ananiadou, Jun’ichi Tsujii

Weaving Aspect-Oriented Constraints into Metamodel-Based Model Transformation Steps

Graph rewriting is a widely used approach to model transformation. In general, graph rewriting rules parse graphs only by topological concerns, but they are not sophisticated enough to match a graph with a node which has a special property. In case of diagrammatic languages, such as the Unified Modeling Language (UML), the exclusive topological parsing is found to be not enough. To define the transformation steps in a more refined way additional constraints must be specified, which ensures the correctness of the attributes among others. Dealing with OCL constraints provides a solution for the unsolved issues. Often, the same constraint is repetitiously applied in many different places in a transformation. It would be beneficial to describe a common constraint in a modular manner, and to designate the places where it is to be applied. This paper presents the problem of the crosscutting constraints in graph transformation steps, provides an aspect-oriented solution for it, and introduces the weaving algorithms used to propagate aspect-oriented constraints to graph transformation steps.

László Lengyel, Tihamér Levendovszky, Hassan Charaf

A Graphical Rule Authoring Tool for Defeasible Reasoning in the Semantic Web

Defeasible reasoning is a rule-based approach for efficient reasoning with incomplete and inconsistent information. Such reasoning is useful for many applications in the Semantic Web, such as policies and business rules, agent brokering and negotiation, ontology and knowledge merging, etc. However, the syntax of defeasible logic may appear too complex for many users. In this paper we present a graphical authoring tool for defeasible logic rules that acts as a shell for the DR-DEVICE defeasible reasoning system over RDF metadata. The tool helps users to develop a rule base using the OO-RuleML syntax of DR-DEVICE rules, by constraining the allowed vocabulary through analysis of the input RDF namespaces, so that the user does not have to type-in class and property names. Rule visualization follows the tree model of RuleML. The DR-DEVICE reasoning system is implemented on top of the CLIPS production rule system and builds upon an earlier deductive rule system over RDF metadata that also supports derived attribute and aggregate attribute rules.

Nick Bassiliades, Efstratios Kontopoulos, Grigoris Antoniou, Ioannis Vlahavas

Bioinformatics

Initial Experiences Porting a Bioinformatics Application to a Graphics Processor

Bioinformatics applications are one of the most relevant and compute-demanding applications today. While normally these applications are executed on clusters or dedicated parallel systems, in this work we explore the use of an alternative architecture. We focus on exploiting the compute-intensive characteristics offered by the graphics processors (GPU) in order to accelerate a bioinformatics application. The GPU is a good match for these applications as it is an inexpensive, high-performance SIMD architecture.

In our initial experiments we evaluate the use of a regular graphics card to improve the performance of RAxML, a bioinformatics program for phylogenetic tree inference. In this paper we focus on porting to the GPU the most time-consuming loop, which accounts for nearly 50% of the total execution time. The preliminary results show that the loop code achieves a speedup of 3x while the whole application with a single loop optimization, achieves a speedup of 1.2x.

Maria Charalambous, Pedro Trancoso, Alexandros Stamatakis

Improving the Accuracy of Classifiers for the Prediction of Translation Initiation Sites in Genomic Sequences

The prediction of the Translation Initiation Site (TIS) in a genomic sequence is an important issue in biological research. Although several methods have been proposed to deal with this problem, there is a great potential for the improvement of the accuracy of these methods. Due to various reasons, including noise in the data as well as biological reasons, TIS prediction is still an open problem and definitely not a trivial task. In this paper we follow a three-step approach in order to increase TIS prediction accuracy. In the first step, we use a feature generation algorithm we developed. In the second step, all the candidate features, including some new ones generated by our algorithm, are ranked according to their impact to the accuracy of the prediction. Finally, in the third step, a classification model is built using a number of the top ranked features. We experiment with various feature sets, feature selection methods and classification algorithms, compare with alternative methods, draw important conclusions and propose improved models with respect to prediction accuracy.

George Tzanis, Christos Berberidis, Anastasia Alexandridou, Ioannis Vlahavas

A New Test System for Stability Measurement of Marker Gene Selection in DNA Microarray Data Analysis

Microarray gene expression data contains informative features that reflect the critical processes controlling prominent biological functions. Feature selection algorithms have been used in previous biomedical research to find the “marker” genes whose expression value change corresponds to the most eminent difference between specimen classes. One problem encountered in such analysis is the imbalance between very large numbers of genes versus relatively fewer specimen samples. A common concern, therefore, is “overfitting” the data and deriving a set of marker genes with low stability over the entire set of possible specimens. To address this problem, we propose a new test environment in which synthetic data is perturbed to simulate possible variations in gene expression values. The goal is for the generated data to have appropriate properties that match natural data, and that are appropriate for use in testing the sensitivity of feature selection algorithms and validating the robustness of selected marker genes. In this paper, we evaluate a statistically-based resampling approach and a Principal Components Analysis (PCA)-based linear noise distribution approach. Our results show that both methods generate reasonable synthetic data and that the signal/noise rate (with variation weights at 5%, 10%, 20% and 30%) measurably impacts the classification accuracy and the marker genes selected. Based on these results, we identify the most appropriate marker gene selection and classification techniques for each type and level of noise we modeled.

Fei Xiong, Heng Huang, James Ford, Fillia S. Makedon, Justin D. Pearlman

Protein Classification with Multiple Algorithms

Nowadays, the number of protein sequences being stored in central protein databases from labs all over the world is constantly increasing. From these proteins only a fraction has been experimentally analyzed in order to detect their structure and hence their function in the corresponding organism. The reason is that experimental determination of structure is labor-intensive and quite time-consuming. Therefore there is the need for automated tools that can classify new proteins to structural families. This paper presents a comparative evaluation of several algorithms that learn such classification models from data concerning patterns of proteins with known structure. In addition, several approaches that combine multiple learning algorithms to increase the accuracy of predictions are evaluated. The results of the experiments provide insights that can help biologists and computer scientists design high-performance protein classification systems of high quality.

Sotiris Diplaris, Grigorios Tsoumakas, Pericles A. Mitkas, Ioannis Vlahavas

Computational Identification of Regulatory Factors Involved in MicroRNA Transcription

MicroRNAs (miRNAs) are non-coding RNA molecules that bind to and translationally repress mRNA transcripts. Currently ~1345 miRNAs have been identified in at least twelve species through experimental and computational approaches. Here, we report on a field not yet thoroughly investigated: the transcriptional regulation of miRNAs. Adequately locating miRNA promoter regions will provide a reasonable search space for computational and experimental studies to determine regulatory factors that drive miRNA transcription. Insight in to the factors that control miRNA transcription may provide clues regarding more complicated mechanisms of miRNA expression control in a developing organism. We use a novel Expressed Sequence Tag (EST) based approach to approximate promoter regions for intergenic miRNAs in order to detect specific and over-represented regulatory elements. We find that miRNA promoter regions may be enriched for binding sites that recruit transcription factors (TFs) involved in development, including several homeobox TFs such as HOXA3 and Ncx. Additionally, we use clustering techniques to cluster miRNAs according to tissue specificity to find tissue-specific regulatory elements. We find a few over-represented binding sites in brain-specific miRNA promoter regions, some of which recruit TFs involved specifically with the development of the nervous system. Based on the results we suggest an interesting mechanism for in vivo miRNA expression control. The EST-based pri-miRNA assembly program will be made available at the website of the DIANA-group by the time of publication (http://diana.pcbi.upenn.edu).

Praveen Sethupathy, Molly Megraw, M. Inmaculada Barrasa, Artemis G. Hatzigeorgiou

Web Service-Enabled Grid-Based Platform for Drug Resistance Management

HIV Drug Resistance testing has been established as a routine test in several cases. Estimation of genotypic resistance is a laborious task consisting of experimental procedure and complicated algorithmic interpretation of mutational pattern (sequence data). Since the sequencing procedure is not error free, it is often necessary to proceed into quality checking and manual editing of the raw data (chromatograms). This paper presents the design and development of a grid-based platform that assists the storage and analysis of HIV nucleotide sequences both for clinical practice and research purposes. Modular software components were implemented for sequence uploading, quality verification, mutation identification, genotypic resistance interpretation, phylogenetic analysis, multiple-sequence alignment and sophisticated mutation querying. Moreover these services have been exported as web services in order to provide a high layer of abstraction and enhanced collaboration among researchers. The platform has been validated and tested with more than 500 HIV sequences.

P. Gouvas, G. Magiorkinis, A. Bouras, D. Paraskevis, D. Alexandrou, A. Hatzakis, G. Mentzas

Software Engineering

The Enhancement of Class Model Development Using Business Rules

Paper deals with the principles of model-driven UML Class model enhancement using business rules (BR) as a source of domain knowledge. Business rules are stored in BR repository which is defined by the business rules meta-model. Templates for business rules formalization are presented. Co-relations between BR meta-model and extended UML Class meta-model are also presented and discussed in this paper. Basic steps of the algorithm for the extended UML Class model enhancement are presented and illustrated with example.

Tomas Skersys, Saulius Gudas

Scenario Networks: Specifying User Interfaces with Extended Use Cases

In this paper, we present the rationale and the baseline of a notation which can be used on its own or as an extension to standard UML to facilitate specification of an interactive system’s global execution context (GEC). The GEC graph is a visual construction consisting of (a) nodes, which represent interaction scenarios, and (b) directed links, which represent scenario relationships designating alternate execution, concurrency, ordering, and set-oriented relationships between two scenario nodes. The technique is particularly useful for specifying adaptable and adaptive behaviours across interaction platforms, contexts of use and target user communities. In the paper, we demonstrate the application of the technique using a file-exchange application which runs on a portable device such as a PDA and implements a lightweight ftp process to connect to a server wirelessly and offer standard ftp functionality (get/put/delete).

Demosthenes Akoumianakis, Ioannis Pachoulakis

Educational Technologies

Teaching Programming with Robots: A Case Study on Greek Secondary Education

The teaching of programming in the Greek education system begins at the secondary level. The aims of the programming syllabus include the attainment of knowledge and skills, which are related to problem solving and the design of algorithms. In order to acquire the students knowledge and skills, the usual approach that is followed is: the use of a programming language of general aim (Pascal, Basic, etc), the use of a professional environment for this programming language, the development of programs that solve problems which treat numbers and symbols. According to researches that have been realized, this approach of teaching programming to beginners constitutes important factor that complicates its learning. In this work we propose a framework of teaching the programming fundamentals to beginners that is based on using LEGO Mindstorms technology. This paper analyzes the results from a pilot research that was carried out on Greek secondary school students.

Maya Sartatzemi, Vassilios Dagdilelis, Katerina Kagani

ASPIS: An Automated Information System for Certification and Analysis of Examination Process

One of the innovations that the usage of Internet has introduced is distance learning. Along with distance learning came the requirement for distance certification. While there are organizations that support the certification process, the provided support in Greece is relatively limited inflexible. In this paper we describe the first to our best knowledge, system that automates the certification process. The proposed system takes into account various learning parameters and makes use of the feedback of the process, along with the help of the data mining on the certification results. In this paper, we describe processes necessary for distance certification, the system itself and we present some results of the data mining we applied on the systems preliminary data.

Georgios Katsikis, Naoum Mengoudis, Alexandros Nanopoulos, Ioannis Samoladas, Ioannis Stamelos

Bridging the Contextual Distance: The e-CASE Learning Environment for Supporting Students’ Context Awareness

Supporting students’ awareness of the complex way that contextual issues affect knowledge application in authentic situations is a critical instructional mission and can lead to improved problem solving in the workplace. In this work we present the design of e-CASE (Context Awareness Supporting Environment), which is a case based learning environment for supporting instruction in the domain of software development. In designing e-CASE we employ a model for context which further guides the use of script and narrative control techniques as external representations for enhancing students’ context awareness. Our system applies an appropriate metadata scheme for connecting various pieces of information and creating crossing paths for the learner, in the web of authentic application cases. It also provides functionality for updating and extending its content allowing people from the workplace to become content providers. Thus, we argue, e-CASE can help bridging the contextual distance, supporting the development of an extended learning community by establishing flexible and instructionally efficient links between the traditional educational settings and the workplace.

Stavros N. Demetriadis, Pantelis M. Papadopoulos, Ioannis A. Tsoukalas

Designing Mobile Learning Experiences

This paper reviews existing applications of mobile learning, and discusses some design issues for the development of mobile learning experiences.

Giasemi Vavoula, Charalampos Karagiannidis

E-Business

From e-Business to Business Transformation

Now that the first wave of excitement on e-commerce has subsided, and after the sobering experience of the dot-com bubble burst, there is a growing understanding that e-commerce is not about a different way of doing commerce, and e-business is not about a different way of doing business. E-Business is about doing business – in a better, more competitive and productive way. To improve business, one has to transform business and the processes that it uses.

Christos Nikolaou, Jakka Sairamesh, Markus Stolze

Trust, Privacy and Security in E-Business: Requirements and Solutions

An important aspect of e-business is the area of e-commerce. One of the most severe restraining factors for the proliferation of e-commerce, is the lack of trust between customers and sellers, consumer privacy concerns and the lack of security measures required to assure both businesses and customers that their business relationship and transactions will be carried out in privacy, correctly, and timely. This paper considers trust privacy and security issues in e-commerce applications and discusses methods and technologies that can be used to fulfil the pertinent requirements.

Sokratis K. Katsikas, Javier Lopez, Günther Pernul

Adoption of Enterprise Resource Planning Systems in Greece

Enterprise Resource Planning Systems (ERP) comprises the dominant business information systems currently implemented in the global market. In this survey, the authors explore the adoption of these systems in enterprises that operate in the Greek market. The scope of the adoption is focused on the level of business processes, in terms of the incentives and the real benefits, that ERP applications offer to enterprises. The survey indicated significant results in the areas of the transformation of incentives for adoption to actual benefits, and on the significance of business process reengineering before the implementation of the systems. Other interesting results are focused on the business use of those systems, the future enhancements, and their contribution in solving the issue of fragmentation of information in disparate legacy applications.

Angeliki K. Poulymenakou, Spiros A. Borotis

Supply Chains of the Future and Emerging Consumer-Based Electronic Services

This paper focuses on the supply-chain opportunities provided by emerging wireless and mobile commerce technologies coupled with automatic product identification technologies (RFID) as well as collaborative environments for sharing information. Speed and visibility have become supply chain imperatives and it is foreseen that the above technologies will transform the supply chain, delivering multiple benefits, such as improved on-self availability and customer service, reduced losses and theft, improved inventory, traceability, warehouse/ back-room, and shelf management. The paper identifies the four major supply chain transformations: sharing information to collaborate, automatic identification of individual items (RFID), product and consumer safety with traceability, and consumer value management (CVM). On these four aspects of S.C. transformations it identifies emerging electronic services with examples from the consumer goods industry.

Georgios Doukidis, Katerina Pramatari

Computer and Sensor Hardware and Architecture

A Quantum Computer Architecture Based on Semiconductor Recombination Statistics

A new architecture for the practical implementation of a quantum computer is presented in this paper. The architecture makes use of the recombination statistics that govern semiconductor devices and I particular quantum phenomena occurring inside the forbidden gap of a semiconductor filled with a controlled amount of impurities. The occupation of a single trap by an electron is used for the representation of the qubit, whereas illuminating techniques are used for the controlled transition of the electrons between gap levels. The way these transitions correspond to the logical equivalent of quantum gates is being demonstrated by the implementation of the quantum Controlled-NOT (CNOT) gate. Measuring techniques of the final computational outcome based on macroscopic properties of a semiconductor are discussed.

The above techniques are then combined for the design of a quantum circuit, which implements the Shor’s factoring algorithm. The physical model for the interconnection of quantum gates scaled to a full quantum computer is given along with the design of the algorithm. Finally, some error estimations are given together with some proposed mechanisms to reduce this error to acceptable levels using known quantum error correction techniques.

D. Ntalaperas, K. Theodoropoulos, A. Tsakalidis, N. Konofaos

TSIC: Thermal Scheduling Simulator for Chip Multiprocessors

Increased power density, hot-spots, and temperature gradients are severe limiting factors for today’s state-of-the-art microprocessors. However, the flexibility offered by the multiple cores in future Chip Multiprocessors (CMPs) results in a great opportunity for controlling the chip thermal characteristics. When a process is to be assigned to a core, a thermal-aware scheduling policy may be invoked to determine which core is the most appropriate.

In this paper we present TSIC, Thermal SImulator for CMPs, which is a fully parameterizable, user-friendly tool that allows us to easily test different CMP configurations, application characteristics, and scheduling policies. We also present a case study where the use of TSIC together with simple thermal-aware scheduling policies allows us to conclude that there is potential for improving the thermal behavior of a CMP by implementing new process scheduling policies.

Kyriakos Stavrou, Pedro Trancoso

Tuning Blocked Array Layouts to Exploit Memory Hierarchy in SMT Architectures

Cache misses form a major bottleneck for memory-intensive applications, due to the significant latency of main memory accesses. Loop tiling, in conjunction with other program transformations, have been shown to be an effective approach to improving locality and cache exploitation, especially for dense matrix scientific computations. Beyond loop nest optimizations, data transformation techniques, and in particular blocked data layouts, have been used to boost the cache performance. The stability of performance improvements achieved are heavily dependent on the appropriate selection of tile sizes.

In this paper, we investigate the memory performance of blocked data layouts, and provide a theoretical analysis for the multiple levels of memory hierarchy, when they are organized in a set associative fashion. According to this analysis, the optimal tile size that maximizes L1 cache utilization, should completely fit in the L1 cache, even for loop bodies that access more than just one array. Increased self- or/and cross-interference misses can be tolerated through prefetching. Such larger tiles also reduce mispredicted branches and, as a result, the lost CPU cycles that arise. Results are validated through actual benchmarks on an SMT platform.

Evangelia Athanasaki, Kornilios Kourtis, Nikos Anastopoulos, Nectarios Koziris

A Tool for Calculating Energy Consumption in Wireless Sensor Networks

Energy and total useful lifetime are primary design concerns of fundamental importance, in a variety of real life applications, where the deployment of a Wireless Sensor Network is desired. In this paper the authors introduce AVAKIS, a tool for calculating the energy consumption of the various components of a sensor node. The proposed tool is an architectural level simulator, in which the system building blocks are described by a high level behavioral model. The methodology used in order to estimate power consumption is based on both the characteristics of the components, and on a number of user-defined initialization parameters.

G. Dimitriou, P. K. Kikiras, G. I. Stamoulis, I. N. Avaritsiotis

Hardware Support for Multithreaded Execution of Loops with Limited Parallelism

Loop scheduling has significant differences in multithreaded from other parallel processors. The sharing of hardware resources imposes new scheduling limitations, but it also allows a faster communication across threads. We present a multithreaded processor model, Coral 2000, with hardware extensions that support Macro Software Pipelining, a loop scheduling technique for multithreaded processors. We tested and evaluated Coral 2000 on a cycle-level simulator, using synthetic and integer SPEC benchmarks. We obtained speedups of up to 30% with respect to highly optimized superblock-based schedules on loops that exhibit limited parallelism.

Georgios Dimitriou, Constantine Polychronopoulos

A Low – Power VLSI Architecture for Intra Prediction in H.264

The H.264 video coding standard can achieve considerably higher coding efficiency than previous standards. The key to this high code efficiency are mainly the Intra and Inter prediction modes provided by the standard. However, the compression efficiency of the H264 standard comes at the cost of increased complexity of the encoder. Therefore it is very important to design video architectures that minimize the cost of the prediction modes in terms of area, power dissipation and design complexity. A common aspect of the Inter and Intra Prediction modes, is the Sum of Absolute Differences (SAD). In this paper we present a new algorithm that can replace the SAD in Intra Prediction, and which provides a more efficient hardware implementation.

Georgios Stamoulis, Maria Koziri, Ioannis Katsavounidis, Nikolaos Bellas

Reducing TPC-H Benchmarking Time

Benchmarking a system can be a time consuming operation. Therefore, many researchers have developed kernels and micro-benchmarks. Nevertheless, these programs are not able to capture the details of a full application. One such example are the complex database applications.

In this work we present a methodology based on a statistical method, Principal Component Analysis, in order to reduce the execution time of TPC-H, a decision support benchmark. This technique selects a subset of queries from the original set that are relevant and may be used to evaluate the systems. We use the subsets to determine the ranking of different computer systems. Our experiments show that with a small subset of 5 queries we are able to rank different systems with more than 80% accuracy in comparison with the original order and this result is achieved with as little as 20% of the original benchmark execution time.

Pedro Trancoso, Christodoulos Adamou, Hans Vandierendonck

Computer Security

CryptoPalm: A Cryptographic Library for PalmOS

PDAs and other handheld devices are commonly used for processing private or otherwise secret information. Their increased usage along with their networking capabilities raises security considerations for the protection of the sensitive information they contain and their communications.

We present CryptoPalm, an extensible cryptographic library for the PalmOS. The library integrates a large set of cryptographic algorithms and is compatible with the IEEE P1363 standard. Furthermore, the library offers performance comparable with that of independent, application-centric implementations of the cryptographic algorithms. CryptoPalm is beneficial for PalmOS software developers, since it provides established cryptographic algorithms as an infrastructure for meeting their applications’ security requirements.

Georgios C. Alexandridis, Artemios G. Voyiatzis, Dimitrios N. Serpanos

On the Importance of Header Classification in HW/SW Network Intrusion Detection Systems

In this paper we examine the impact of various levels of (partial) hardware acceleration levels on a software based Network Intrusion Detection System. While complete hardware solutions are possible and have been studied extensively, they are costly and may suffer from scalability and flexibility limitations. The flexibility of software is attractive to address these concerns. We show in this paper that (unexpectedly) a modest amount of hardware acceleration such as simple header classification can achieve respectable and cost-effective system throughput. We also find that further acceleration in the form of approximate filtering offers very small incremental improvement.

Vassilis Dimopoulos, Giorgos Papadopoulos, Dionisios Pnevmatikatos

NGCE – Network Graphs for Computer Epidemiologists

Graphs are useful data structures capable of efficiently representing a variety of technological and social networks. They are therefore utilized in simulation-based studies of new algorithms and protocols. Inspired by the popular

tgff

(Task Graphs For Free) toolkit, which creates task graphs for embedded systems, we present the

ngce

, an easy to use graph generator that produces structures for the study of the propagation of viral agents in complex computer networks.

Designated track:

Computer Security

Vasileios Vlachos, Vassiliki Vouzi, Damianos Chatziantoniou, Diomidis Spinellis

Workflow Based Security Incident Management

Security incident management is one of the critical areas that offers valuable information to security experts, but still lacks much development. Currently, several security incident database models have been proposed and used. The discrepancies of such databases entail that worldwide incident information is stored in different formats and places and, so, do not provide any means for Computer Security Incident Response Teams (CSIRTs) collaboration. This paper presents an architecture based on advance database techniques, able to collect incident related information from different sources. Our framework enhances the incident management process by allowing the law enforcement units to (a) collect the required evidence from incident data that are spread through a number of different incident management systems; (b) transform, clean, and homogenize them; and, finally, (c) load them to a central database management system. Such architecture can also be beneficial by minimizing the mean time between the appearance of a new incident and its publication to the worldwide community.

Meletis A. Belsis, Alkis Simitsis, Stefanos Gritzalis

A Deterministic Approach to Balancedness and Run Quantification in Pseudorandom Pattern Generators

An easy method of computing the number of 1’s and 0’s (balancedness) as well as the number of runs (run quantification) in the sequence obtained from a LFSR-based pseudorandom patter generator has been developed. The procedure is a deterministic alternative to the traditional application of statistical tests. The computation method allows one to check deviation of balancedness and run distribution goodness from standard values. As a straight consequence of the above procedure, simple rules to design pattern generators with adequate pseudorandomness properties are also derived.

Amparo Fúster-Sabater, Pino Caballero-Gil

Image and Video Processing

Protecting Intellectual Property Rights and the JPEG2000 Coding Standard

The ever-increasing use of the Internet and file sharing applications based on Peer to Peer networks has alarmed content authors, providers and resellers of digital content. Techniques proposed for protecting digital media include watermarking, use of metadata and self-protection and self-authentication. In this paper we review the most important of these methods and analyse their potential use in Digital Rights Management systems. The main focus is on IPR management through watermarking for digital images coded with the new and a lot promising compression standard: JPEG2000.

B. Vassiliadis, V. Fotopoulos, A. Ilias, A. N. Skodras

Computationally Efficient Image Mosaicing Using Spanning Tree Representations

Optimal image mosaicing has large computational complexity, that becomes prohibitive as the number of sub-images increases. Two methods are proposed, which require less computation time by performing mosaicing in pairs of two sub-images at a time, without significant reconstruction losses, as evidenced by simulation results.

Nikos Nikolaidis, Ioannis Pitas

An MPEG-7 Based Description Scheme for Video Analysis Using Anthropocentric Video Content Descriptors

MPEG-7 has emerged as the standard for multimedia data content description. As it is in its early age, it tries to evolve towards a direction in which semantic content description can be implemented. In this paper we provide a number of classes to extend the MPEG-7 standard so that it can handle the video media data, in a more uniform and anthropocentric way. Many descriptors (Ds) and description schemes (DSs) already provided by the MPEG-7 standard can help to implement semantics of a media. However, by grouping together several MPEG-7 classes and adding new Ds, better results in the video production and video analysis tasks can be produced. Several classes are proposed in this context and we show that the corresponding scheme produce a new profile which is more flexible in all types of applications as they are described in [1].

N. Vretos, V. Solachidis, I. Pitas

Detecting Abnormalities in Capsule Endoscopic Images by Textural Description and Neural Networks

In this paper, a detection system to support medical diagnosis and detection of abnormal lesions by processing endoscopic images is presented. The endoscopic images possess rich information expressed by texture. Schemes have been developed to extract texture features from the texture spectra in the chromatic and achromatic domains for a selected region of interest from each colour component histogram of images acquired by the new M2A Swallowable Capsule. The implementation of an advanced neural network scheme and the concept of fusion of multiple classifiers have been also adopted in this paper. The preliminary test results support the feasibility of the proposed method.

V. S. Kodogiannis, E. Wadge, M. Boulougoura, K. Christou

Unsupervised Learning of Multiple Aspects of Moving Objects from Video

A popular framework for the interpretation of image sequences is based on the layered model; see e.g. Wang and Adelson [8], Irani et al. [2]. Jojic and Frey [3] provide a generative probabilistic model framework for this task. However, this layered models do not explicitly account for variation due to changes in the pose and self occlusion. In this paper we show that if the motion of the object is large so that different aspects (or views) of the object are visible at different times in the sequence, we can learn appearance models of the different aspects using a mixture modelling approach.

Michalis K. Titsias, Christopher K. I. Williams

The Feature Vector Selection for Robust Multiple Face Detection

This paper presents the robust feature vector selection for multiple frontal face detection based on the Bayesian statistical method. The feature vector for the training and classification are integrated by means, amplitude projections, and its 1D Harr wavelet of input image. And the statistical modeling is performed both for face and nonface classes. Finally, the estimated probability density functions (PDFs) are applied by the proposed Bayesian method to detect multiple frontal faces in an image. The proposed method can handle multiple faces, partially occluded faces, and slightly posed-angle faces. Especially, the proposed method is very effective for low quality face images. Experiments show that detection rate of the propose method is 98.3% with three false detections on SET3 testing data which have 227 faces in 80 images.

Seung-Ik Lee, Duk-Gyoo Kim

Signal Processing and Telecommunications

A Low Complexity Turbo Equalizer

In this paper a new Soft Input – Soft Output (SISO) equalizer of linear complexity is developed. The algorithm can be used in the so-called Turbo Equalization scheme as a low cost solution in place of the Maximum A-Posteriori (MAP) equalization algorithm which has a prohibitive complexity for most real world applications. The proposed equalizer consists of two parts, namely, a Soft Interference Canceller (SIC) and a pre-processing part which is a new Variable-Threshold Decision Feedback Equalizer (VTDFE). The main difference in the proposed equalizer as compared to the SIC is that the input to the cancellation filter is computed not only using a-priori probabilities, but information from the received signal as well. Simulation results have shown that the proposed turbo equalizer exhibits a superior performance as compared to the turbo equalization scheme based on the conventional SIC as well as other linear complexity SISO equalizers.

Dimitris Ampeliotis, Kostas Berberidis

Bit Error Rate Calculation for DS-CDMA Systems with WDS in the Presence of Rayleigh Fading and Power-Control Error

This paper reports work in which modified expressions for the bit error rate (BER) calculation of DS-CDMA systems with weighted despreading sequences (WDS) in the presence of Rayleigh fading and power-control error are proposed. The focus of the modified expressions is based on a simple equality which was proposed in the open literature. The major benefit from using the proposed expressions which are obtained for both coherent and noncoherent receptions is that they require less definition about the spreading sequences for the BER calculation.

Ibrahim Develi, Cebrail Ciftlikli, Aytekin Bagis

Multivariate AR Model Order Estimation with Unknown Process Order

A new method for simultaneous order estimation and parameter identification of a multivariate autoregressive (AR) model is described in this paper. The proposed method is based on the well known multimodel partitioning theory. Computer simulations indicate that the method is 100% successful in selecting the correct model order in very few steps. The results are compared with another two established order selection criteria the Akaike’s Final Prediction Error (FPE) and Schwarz’s Bayesian Criterion (BIC).

Stylianos Sp. Pappas, Assimakis K. Leros, Sokratis K. Katsikas

Cortical Lateralization Analysis by Kolmogorov Entropy of EEG

Based on nonlinear dynamic method, mean Kolmogorov entropy (KE) is introduced to analyze and localize the cortical lateralization. The results indicate that: 1) the lateralization determined by Kolmogorov entropy of EEG proposed in this paper is consistent with previous known studies. But this method is more sensitive to cortical lateralization. This method can identify the differences of cortical lateralization between different brain function areas. 2) The dominant hemisphere is not always the same one for some particular task. 3) The cortical lateralization may involve in several different cortical areas synchronously and for different brain areas the lateralizations of the same mental task may be not on the same side. 4) To analyze and localize cortical lateralization, mean Kolmogorov entropy based on spontaneous EEG is a good method.

Lianyi Zhang, Chongxun Zheng

Computer and Sensor Networks

Source-Based Minimum Cost Multicasting: Intermediate-Node Selection with Potentially Low Cost

In this paper, we propose a novel heuristic algorithm for constructing a minimum cost multicast tree. Our work is based on a directed asymmetric network and shows an improvement in terms of network cost for general random topologies close to real networks. It is compared to the most effective scheme proposed earlier by Takahashi and Matsuyama (TM) [18]. We have experimented comprehensive computer simulations and the performance enhancement is up to about 4.7% over TM. The time complexity of ours is

O

(

kn

2

) for an

n

-node network with

k

members in the multicast group which is comparable to those of previous works [12,18].

Gunu Jho, Moonseong Kim, Hyunseung Choo

Efficient Active Clustering of Mobile Ad-Hoc Networks

Mobile ad hoc networks comprise a collection of wireless nodes that dynamically create a network among themselves without using any pre-existing infrastructure. Clustering of mobile nodes among separate domains has been proposed as an efficient approach to answer the organization, scalability and routing problems of mobile ad hoc networks. In this work, we propose an efficient distributed clustering algorithm that uses both location and energy metrics for stable cluster formation. Unlike existing active clustering methods, out algorithm relieves the network from the unnecessary burden of control messages broadcasting. This is achieved through adapting broadcast period according to mobile nodes mobility pattern. For relative static network topologies, broadcast period is lengthened. In contrast, broadcast period is shortened to meet the requirements of highly dynamic networks for consistent cluster configurations.

Damianos Gavalas, Grammati Pantziou, Charalampos Konstantopoulos, Basilis Mamalis

Evaluation of Audio Streaming in Secure Wireless Access Network

Advances in the Internet and multimedia technologies have spurred many research efforts in Internet-based multimedia access systems, which integrate wireline and wireless networks. Internet-based multimedia streaming services are in need of a service creation model. In this paper, we presented such a model and framework for delivering real-time traffics to a wireless access network over public Internet Protocol (IP) backbone network. We have presented a performance analysis of audio streaming when IP tunneling network using Generic Route Encapsulation (GRE) along with Internet Protocol Security (IPSec) is implemented. The impacts on performance, with particular attention to Quality of Service (QoS) characteristics have been evaluated through a series of experiments. In this paper, the effects of a compression scheme based on compressed real-time transport protocol (CRTP) and Resource Reservation protocol (RSVP) are analyzed when delivering real-time traffics to the wireless access network through secured IP Network.

Binod Vaidya, JongWoo Kim, JaeYoung Pyun, JongAn Park, SeungJo Han

Reliable Transmission Using Intermediate Sink or Source Nodes in Sensor Networks

In some critical applications, in sensor networks the most important issue is to transmit sensing information to the end user (the sink node) with reliability. Reliable information forwarding using multiple paths in sensor networks (ReInForM) can achieve desired reliability in the error-prone channel, but it needs increasing transmission overhead as the channel error rate becomes high and the number of hops between the source node and the sink node increases. In this paper, we propose reliable transmission using intermediate source nodes in sensor networks (ReTrust) to reduce packet overhead while keeping the desired reliability. Intermediate source or sink (IS) nodes are formed between the source node and the sink node. The IS nodes should be determined so that the given transmission reliability is satisfied while reducing the number of packets or multi-paths. ReTrust has been shown to provide desired reliability and reduced overhead via simulations and analysis.

Bo-Hyung Lee, Hyung-Wook Yoon, Jongho Park, Min Young Chung, Tae-Jin Lee

A Novel Heuristic Routing Algorithm Using Simulated Annealing in Ad Hoc Networks

Multi-constrained quality-of-service routing (QoSR) is to find a feasible path that satisfies multiple constraints simultaneously, as an NPC problem, which is also a big challenge for ad hoc networks. In this paper, we propose a novel heuristic routing algorithm based on Simulated Annealing (SA_HR). This algorithm first uses an energy function to translate multiple QoS weights into a single metric and then seeks to find a feasible path by simulated annealing. The paper outlines simulated annealing algorithm and analyzes the problems met when we apply it to QoSR in ad hoc networks. Theoretical analysis and experiment results demonstrate that the proposed method is an effective approximate algorithms showing good performance in seeking the (approximate) optimal configuration within a period of polynomial time.

Lianggui Liu, Guangzeng Feng

Balancing HTTP Traffic Using Dynamically Updated Weights, an Implementation Approach

In this paper we present a load balancing application for HTTP traffic that uses dynamic weights. We introduce a load balancing policy based on two criteria: “

process time

” and “

network delay

”. The former describes Web servers ability to process a forthcoming request, while the latter tries to estimate network conditions. Calculation of the two criteria is periodically updated. A

Weighted Round Robin

algorithm was implemented using the two aforementioned metrics in order to dynamically estimate the balancing weights.

We confirm that the combination of the two criteria increases sensitivity and responsiveness of the application towards network conditions and therefore the performance of the whole load balancing system. Balancing decisions should not be only “load” or “connection” dependent, but also contention dependent.

A. Karakos, D. Patsas, A. Bornea, S. Kontogiannis

Industrial Exhibition Paper

A Review of Microsoft Products, Strategy and Technologies

Recent surveys for e-business future in western European countries, show that there is a huge growth potential as the total amount spent on ebusiness (B2B and B2C) is forecasted to rise from 150BUSD in 2004 to 650BUSD in 2008 and web buyers will rise from 67M in 2004 to 94M in 2008 [source, IDC 2004]. Interestingly, Greece seems to have an even greater potential with a forecast of increasing e-business transactions from 2.861mUSD in 2004 to 13000mUSD in 2008 [source, IDC 2004]. As a result, all major software vendors are working on strategy, products and technologies in order to obtain the pole position in business-to-business and business-to-consumer commerce.

This paper discusses the e-business strategy, products and technologies of a major software vendor, which is expected to have a key role in this area during the next years, Microsoft Corporation. Firstly, an architectural and functions’ overview of Microsoft e-business servers, namely “Biztalk Server”, “Content Management Server” and “Commerce Server” is provided. Secondly, “Jupiter”, the codename for Microsoft’s e-business roadmap and vision is presented and discussed. With “Jupiter” Microsoft aims at reducing IT complexity and connect people, processes and information through an integrated, standards-based e-business infrastructure. Finally, the underlying technologies of the abovementioned products and strategy, such as XML, Web services, SOAP, .NET, are presented, together with the latest advancements in e-business facilitator standards, such as web services interoperability standards.

Fotis Draganidis

Backmatter

Additional information