Contemporary data-systems empowering the daily human activity are routinely represented with graphs. During the last decade, the volume growth of such systems has been unprece-dented. This hinders the timely analysis of the formed networks due to existing physical memory limitations and significant I/O overheads. Graph compression techniques have managed to reduce memory requirements and allow for representing such networks using a few bits-per-edge. Respective approaches offer succinct mappings for social, biological, and information networks while allowing for the efficient access of sought graph elements. Despite their success, such methods mostly focus on static graphs, and predominantly offer access to either a snapshot or an aggregated view of a network. In reality however, networks change over time and, in many instances, we are interested in capturing and studying this evolution. In this paper we propose a framework for compressing emerging temporal graphs based on a dual-representation which articulates both network structure and corresponding temporal information. We empirically establish properties exhibited by community-networks regarding their time aspect(s) and harness these features in our proposed repre-sentation. Our experimental evaluation demonstrates that our approach for compressing temporal graphs readily outperforms competing techniques, attaining compression ratios that are on average around 60% of the space required by state-of-the-art techniques. Moreover, our memory-efficient representation yields more than 70 % faster graph compression and orders of magnitude quicker retrieval of graphs' elements, especially when it comes to large-scale networks. Finally, our framework is the first effort we are aware of, that considers actual time instead of time steps. This helps us attain better control for the size of our representation and reap further memory savings.

Real-life systems involving interacting objects are typically modeled as graphs and can often grow very large in size. Revealing the community structure of such systems is crucial in helping us better understand their complex nature. However, the ever-increasing size of real-world graphs and our evolving perception of what a community is, make the task of community detection very challenging. A critical relevant challenge is the discovery of the possibly overlapping communities of a given node in a billion-node graph. This problem is very common in modern large social networks like Facebook and LinkedIn. In this work, we propose a scalable local community detection approach to efficiently unfold the communities of individual target nodes in a given network. Our goal is to reveal the clusters formed around nodes (e.g., users) by leveraging the relations within alldifferentcontexts these nodes participate in. Our approach, termed Local Dispersion-aware Link Communities or LDLC, considers the similarity of pairs of links in the graph as well as the extent of their participation in multiple contexts. Then, we determine the order in which we should group the pairs of links so that we form meaningful hierarchical communities. We are not affected by constraints existing in previous techniques such as the need for several seed nodes or the need to collapse multiple overlapping communities to a single community. Our experimental evaluation using ground-truth communities for a wide range of large real-world networks shows that our LDLC algorithm significantly outperforms state-of-the-art methods on both accuracy and efficiency. Moreover, we show that LDLC uncovers very effectively the hierarchical structure of overlapping communities by producing detailed dendrograms.

We examine the problem of uncovering communities in complex real-world networks whose elements and their respective associations manifest as streams of data. Community detection is applied in emerging computational environments and concerns critical applications in diverse areas including social computing, web analysis, IoT and biology. Despite the already expended related research efforts, the task of revealing the community structure of massive and rapidly-evolving networks remains very challenging. More specifically, there is an emerging need for online approaches that ingest graph data as a stream. In this paper, we propose a streaming-graph community-detection algorithm that expands seed-sets of nodes to communities. We consider an online setting and process a stream of edges while aiming to form communities on-the-fly using partial knowledge of the graph structure. We use space-efficient structures to maintain very limited information regarding the nodes of the graph and the sought communities, so as to effectively process large scale networks. In addition to our novel streaming approach, we develop a technique that increases the accuracy of our algorithm considerably and additionally propose a new clustering algorithm that allows for automatically deriving the size of the communities we seek to detect. Using ground-truth communities for a wide range of large real-word and synthetic networks, our experimental evaluation shows that our approach does achieve accuracy comparable, and oftentimes better, to the state-of-the-art non-streaming community detection algorithms. More importantly, we attain significant improvements in both execution time and memory requirements.

Micro-blogging and social-media platforms are now prominent forums for disseminating information, opinions and commentaries. Among these, Twitter enjoys an in-excess of 330M base of users who continually produce and consume information snippets. Users collectively create a voluminous and multi-lingual corpus in a very broad range of topics on a daily basis. The discourse generated in the blogosphere is often of prime interest and importance to individuals, organizations, and companies. These actors would certainly like to periodically receive an overall assessment of demonstrated "sentiments" on specific issues by automatically classifying tweets expressed in different languages in conjunction with big-data analytics. In this paper, we propose a scalable service platform that employs multilingual sentiment analysis to classify streamed-tweets and yields analytics for selected topics in real-time. We discuss the main component of our Spark-enabled platform as we seek to offer an effective big-data service that can: 1) dynamically handle voluminous as well as high-rate tweettraffic through a multi-component application exploiting the latest software developments, 2) accurately identify messages originated by non-genuine user-accounts, and 3) utilize the Spark machine-learning library (MLib) to successfully classify streamed multi-lingual messages in real-time, using multiple potentially distributed executors. To empower our service platform, we have adopted training sets and developed sentiment analysis (SA) models for English, French, and Greek that help classify streamed tweetswith high accuracy. While experimenting with our distributed analytical platform, we establish both accurate and real-time classification for tweetsexpressed in the above European languages.

MOTIVATION: Understanding the underlying biological mechanisms and respective interactions of a disease remains an elusive, time consuming and costly task. Computational methodologies that propose pathway/mechanism communities and reveal respective relationships can be of great value as they can help expedite the process of identifying how perturbations in a single pathway can affect other pathways. RESULTS: We present a random-walks-based methodology called PathWalks, where a walker crosses a pathway-to-pathway network under the guidance of a disease-related map. The latter is a gene network that we construct by integrating multi-source information regarding a specific disease. The most frequent trajectories highlight communities of pathways that are expected to be strongly related to the disease under study.We apply the PathWalks methodology on Alzheimer's disease and idiopathic pulmonary fibrosis and establish that it can highlight pathways that are also identified by other pathway analysis tools as well as are backed through bibliographic references. More importantly, PathWalks produces additional new pathways that are functionally connected with those already established, giving insight for further experimentation. AVAILABILITY AND IMPLEMENTATION: https://github.com/vagkaratzas/PathWalks. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

We consider the problem of uncovering communities in complex real-world networks whose nodes and their respective associations originate in streams of data. Although community detection has received much attention in centralized settings, the prevalence of online social networks has resulted in unprecedented volumes of data whose handling calls for novel streaming approaches. Moreover, bursty production of network interactions necessitates cloud-enabled techniques that can both deal with diverse data rates and deploy more computing resources on the fly for improved performance yields. We propose a distributed streaming community detection approach termed DiCeS, and implement it as a cloud application. While seeking communities, the novelty of our approach is at balancing the incoming load to a cluster of computing nodes and adjusting the cluster processing capacity in an elastic manner. We also provide fault tolerance by ensuring that temporarily suspended or failed nodes are restored and all edges of the network stream ultimately received their due processing. Lastly, DiCeS is interactive regarding i) updating the target communities, and ii) obtaining results on demand. Our experimental results demonstrate that DiCeS does handle the edges of real-world network streams at impressive rates, allows for near-linear scaling, and outperforms previous non-distributed approaches. While using ground-truth communities for a wide range of large real-word networks, we also show that DiCeS attains improved accuracy if compared to earlier centralized algorithms.

Fibrotic diseases constitute incurable maladies that affect a large portion of the population. Idiopathic Pulmonary Fibrosis is one of the most common, and thus studied, fibrotic diseases. Common ground among all fibrotic diseases is the uncontrollable fibrogenesis which is responsible for accumulated damage in the susceptible tissues. The plethora and complexity of the underlying mechanisms of fibrotic diseases account for the lack of regimens. Hence it is highly likely that a combination of drugs is required in order to counter every perturbation. In this study, we seek to identify common biological mechanisms and characteristics of fibrotic diseases, based on information acquired from biological databases, while we focus on Idiopathic Pulmonary Fibrosis. We also try to predict links between molecular data and their respective fibrotic phenotypes. We finally construct phenotypic and molecular networks, visualize them and apply a clustering algorithm on each network to identify fibrotic diseases that are close to Idiopathic Pulmonary Fibrosis.

Modern computer systems now feature memory banks whose aggregate size ranges from tens to hundreds of GBs. In this context, contemporary workloads can and do often consume vast amounts of main memory. This upsurge in memory consumption routinely results in increased virtual-to-physical address translations, and consequently and more importantly, more translation misses. Both of these aspects collectively do hamper the performance of workload execution. A solution aimed at dramatically reducing the number of address translation misses has been to provide hardware support for pages with bigger sizes, termed huge pages. In this paper, we empirically demonstrate the benefits and drawbacks of using such huge pages. In particular, we show that it is essential for modern OS to refine their software mechanisms to more effectively manage huge pages. Based on our empirical observations, we propose and implement MEGA, a framework for huge page support for the Linux kernel. MEGA deploys basic tracking mechanisms and a novel memory compaction algorithm that jointly provide for the effective management of huge pages. We experimentally evaluate MEGA using an array of both synthetic and real workloads and demonstrate that our framework tackles known problems associated with huge pages including increased page fault latency, memory bloating as well as memory fragmentation, while at the same time it delivers all huge pages benefits.

A multitude of contemporary applications heavily involve graph data whose size appears to be ever-increasing. This trend shows no signs of subsiding and has caused the emergence of a number of distributed graph processing systems including Pregel, Apache Giraph, and GraphX. However, the unprecedented scale now reached by real-world graphs hardens the task of graph processing due to excessive memory demands even for distributed environments. By and large, such contemporary graph processing systems employ ineffective in-memory representations of adjacency lists. Therefore, memory usage patterns emerge as a primary concern in distributed graph processing. We seek to address this challenge by exploiting empirically-observed properties demonstrated by graphs generated by human activity. In this paper, we propose 1) three compressed adjacency list representations that can be applied to any distributed graph processing system, 2) a variable-byte encoded representation of out-edge weights for space-efficient support of weighted graphs, and 3) a tree-based compact out-edge representation that allows for efficient mutations on the graph elements. We experiment with publicly-available graphs whose size reaches two-billion edges and report our findings in terms of both space-efficiency and execution time. Our suggested compact representations do reduce respective memory requirements for accommodating the graph elements up-to 5 times if compared with state-of-the-art methods. At the same time, our memory-optimized methods retain the efficiency of uncompressed structures and enable the execution of algorithms for large scale graphs in settings where contemporary alternative structures fail due to memory errors.

We examine the problem of effective identification of community structure of a network whose elements and their respective relationships manifest through streams. The problem has recently garnered much interest as it appears in emerging computational environments and concerns critical applications in diverse areas including social computing, web analysis, IoT and biology. Despite the already expended research efforts in detecting communities in networks, the unprecedented volume that real-world networks now reach, renders the task of revealing community structures extremely burdensome. The sheer size of such networks oftentimes makes their representation in main memory impossible. Thus, processing the developing graphs to extract the underlying communities remains an open challenge. In this paper, we propose a graph-stream community detection algorithm that expands seed-sets of nodes to communities. We consider a stream of edges and aim at processing them to form communities without maintaining the entire graph structure. Instead, we maintain very limited information regarding the nodes of the graph and the communities we seek. In addition to our novel streaming approach, we both develop a technique that increases the accuracy of our algorithm considerably and propose a new clustering algorithm that allows for automatically deriving the size of the communities we seek to detect. Our experimental evaluation using ground-truth communities for a wide range of large real-word networks shows that our proposed approach does achieve accuracy comparable or even better to that of state-of-the-art non-streaming community detection algorithms. More importantly, the attained improvements in both execution time and memory space requirements are remarkable.

Processing the full activity stream of a social network in real time is oftentimes prohibitive in terms of both storage and computational cost. One way to work around this problem is to take a sample of the social activity and use this sample to feed into applications such as content recommendation, opinion mining, or sentiment analysis. In this paper, we study the problem of extracting samples of authoritative content from a social activity stream. Specifically, we propose an adaptive stream sampling approach, termed Rhea, that processes a stream of social activity in real-time and samples the content of users that are more likely to provide influential information. To the best of our knowledge, Rhea is the first algorithm that dynamically adapts over time to account for evolving trends in the activity stream. Thus, we are able to capture high quality content from emerging users that contemporary white-list based methods ignore. We evaluate Rhea using two popular social networks reaching up to half a billion posts. Our results show that we significantly outperform previously proposed methods in terms of both recall and precision, while also offering remarkably more accurate ranking.

Live VMmigration helps attain both cloud-wide load balancing and operational consolidation while the migrating VMs remain accessible to users. To avoid periods of high-load for the involved resources, IaaS-cloud operators assign specific time windows for such migrations to occur in an orderly manner. Moreover, providers typically rely on share-nothing architectures to attain scalability. In this paper, we focus on the real-time scheduling of live VM migrations in large share-nothing IaaS clouds, such that migrations are completed on time and without adversely affecting agreed-upon SLAs. We propose a scalable, distributed network of brokers that oversees the progress of all on-going migration operations within the context of a provider. Brokers make use of an underlying special purpose file system, termed MigrateFS, that is capable of both replicating and keeping in sync virtual disks while the hypervisor livemigrates VMs (i.e., RAM and CPU state). By limiting the resources consumed during migration, brokers implement policies to reduce SLA violations while seeking to complete all migration tasks on time. We evaluate two such policies, one based on task prioritization and a second that considers the financial implications set by migration deadline requirements. Using our MigrateFS prototype operating on a real cloud, we demonstrate the feasibility of performing migrations within time windows. By simulating large clouds, we assess the effectiveness of our proposed broker policies in a share-nothing configuration; we also demonstrate that our approach stresses 24 percent less an already saturated network if compared to an unsupervised set up.

Real-life systems involving interacting objects are typically modeled as graphs and can often grow very large in size. Revealing the community structure of such systems is crucial in helping us better understand their complex nature. However, the ever-increasing size of real-world graphs, and our evolving perception of what a community is, make the task of community detection very challenging. One such challenge, is the discovery of the possibly overlapping communities of a given node in a billion-node graph. This problem is very common in modern large social networks like Facebook and Linkedln. In this paper, we propose a scalable local community detection approach to efficiently unfold the communities of individual target nodes in a given network. Our goal is to reveal the groupings formed around nodes (e.g., users) by leveraging the relations of the different contexts the nodes participate in. Our algorithm, termed Local Dispersion-aware Link Communities or LDLC, measures the similarity of pairs of links in the graph as well as the extent of their participation in multiple contexts. Then, it determines the ordering that we should group the links in order to form communities. Our approach is not affected by constraints existent in previous techniques (e.g., the need for several seed nodes or the need to collapse multiple overlapping communities to one). Our experimental evaluation using ground-truth communities for a wide range of large real-world networks show that LDLC significantly outperforms state-of-the-art methods on both accuracy and efficiency.

A multitude of contemporary applications now involve graph data whose size continuously grows and this trend shows no signs of subsiding. This has caused the emergence of many distributed graph processing systems including Pregel and Apache Giraph. However, the unprecedented scale now reached by real-world graphs hardens the task of graph processing even in distributed environments and the current memory usage patterns rapidly become a primary concern for such contemporary graph processing systems. We seek to address this challenge by exploiting empirically-observed properties demonstrated by graphs that are generated by human activity. In this paper, we propose three space-efficient adjacency list representations that can be applied to any distributed graph processing system. Our suggested compact representations reduce respective memory requirements for accommodating the graph elements up to 5 times if compared with state-of-the-art methods. At the same time, our memory-optimized methods retain the efficiency of uncompressed structures and enable the execution of algorithms for large scale graphs in settings where contemporary alternative structures fail due to memory errors.

E-voting systems have emerged as a powerful technology for improving democracy by reducing election cost, increasing voter participation, and even allowing voters to directly verify the entire election procedure. Prior internet voting systems have single points of failure, which may result in the compromise of availability, voter secrecy, or integrity of the election results. In this paper, we present the design, implementation, security analysis, and evaluation of D-DEMOS, a complete e-voting system that is distributed, privacy-preserving and end-to-end verifiable. Our system includes a fully asynchronous vote collection subsystem that provides immediate assurance to the voter her vote was recorded as cast, without requiring cryptographic operations on behalf of the voter. We also include a distributed, replicated and fault-tolerant Bulletin Board component, that stores all necessary election-related information, and allows any party to read and verify the complete election process. Finally, we also incorporate trustees, i.e., individuals who control election result production while guaranteeing privacy and end-to-end-verifiability as long as their strong majority is honest. Our system is the first e-voting system whose voting operation is human verifiable, i.e., a voter can vote over the web, even when her web client stack is potentially unsafe, without sacrificing her privacy, and still be assured her vote was recorded as cast. Additionally, a voter can outsource election auditing to third parties, still without sacrificing privacy. Finally, as the number of auditors increases, the probability of election fraud going undetected is diminished exponentially. We provide a model and security analysis of the system. We implement a prototype of the complete system, we measure its performance experimentally, and we demonstrate its ability to handle large-scale elections.

It is imperative that water is delivered clean to urban centers and towns despite its channelling through waterways, ponds and city aqueducts. Waterways are occasionally polluted by micro-organisms, landslides, pesticides, as well as by human activity and waste. In coordinated efforts to address such problems, water authorities and local governments resort to cleaning facilities whose main task is to filter the water in a timely fashion. In this regard, authorities must be forewarned of imminent or developing pollution issues, so that immediate corrective action can be taken. The installation of sensors that continuously monitor the quality of water passing through specific points in waterways, proves to be an effective way to implement legislative mandates for clean water. We use submerged sensors to gather measurements that can help characterize the quality of water in canals using parameters including temperature, conductivity, turbidity, PH, and pressure. Raw sensor-generated measurements turn out to be of limited help when it comes to monitor the overall water quality and by themselves, can be even misleading occasionally. In this paper, we discuss the main features of Tethys, a real-time water quality monitoring tool, whose aim is to help the Athens water authorities in their ongoing assessment of water quality. Tethys receives as input streams of measurements from stations in the field, detects unexpected events, visualizes the flow of information, and automatically alerts supervisors about potential dangers appearing in waterways. We outline our design choices, filtering mechanisms, and implementation effort in realizing Tethys and demonstrate its real-time use.

In high-dimensional data domains, the performance of conventional tree-based access structures is occasionally outperformed by simple sequential scans. To this end, the introduction of approximation-based methods helped speed-up queries by providing compact representations of stored data. Approximation methods exploit vector quantization to index data mainly presumed to follow a uniform distribution. In real-world environments however, we mostly encounter both skewed data and query distributions. To address this dual challenge, we propose DiVA that combines the selective use of an approximation approach with an indexing mechanism to organize data subspaces in a high fan-out hierarchical structure. Moreover, DiVA reorganizes its own elements after receiving application hints regarding data access patterns. These hints or policies trigger the restructuring and possible expansion of DiVA so as to offer finer indexing granularity and improved access times in subspaces emerging as ‘hot-spots’. The novelty of our approach lies in the self-organizing nature of DiVA driven by application-provided policies; the latter effectively guide the refinement of DiVA's elements as new data arrive, existing data are updated and the nature of query workloads continually changes. An extensive experimental evaluation using real data shows that DiVA reduces up-to 64% of the total number of I/Os if compared with state-of-art methods including the VA-file, GC-tree and A-tree.

We present a decentralized approach towards scalable and energy-efficient management of virtual machine (VM) instances that are provisioned by large, enterprise clouds. In our approach, the computation resources of the data center are effectively organized into a hypercube structure. The hypercube seamlessly scales up and down as resources are either added or removed in response to changes in the number of provisioned VM instances. Without supervision from any central components, each compute node operates autonomously and manages its own workload by applying a set of distributed load balancing rules and algorithms. On one hand, underutilized nodes attempt to shift their workload to their hypercube neighbors and switch off. On the other, overutilized nodes attempt to migrate a subset of their VM instances so as to reduce their power consumption and prevent degradation of their own resources, which in turn may lead to SLA violations. In both cases, the compute nodes in our approach do not overload their counterparts in order to improve their own energy footprint. An evaluation and comparative study of the proposed approach provides evidence of its merits in terms of elasticity, energy efficiency, and scalability, as well as of its feasibility in the presence of high workload rates.

The existing practices of the urban section of freight transport chain result in traffic congestion, air pollution and resources being wasted. We focus on the final stage of freight distribution and propose an interactive freight-pooling service, in an effort to reduce the undesirable effects and the cost of freight transport in urban areas. Our service empowers city and state authorities to orchestrate the distribution network through interactive interfaces. We break the problem into three distinct phases that collectively helps us set constraints related to the quality of service and find inexpensive routes. In this regard, our proposed freight-pooling approach becomes an attractive option for efficient distribution, that guarantees cost minimization without sacrificing the level of quality.

Earth-Science data are composite, multi-dimensional and of significant size, and as such, continue to pose a number of ongoing problems regarding their management. With new and diverse information sources emerging as well as rates of generated data continuously increasing, a persistent challenge becomes more pressing: To make the information existing in multiple heterogeneous resources readily available. The widespread use of the XML data-exchange format has enabled the rapid accumulation of semi-structured metadata for Earth-Science data. In this paper, we exploit this popular use of XML and present the means for querying metadata emanating from multiple sources in a succinct and effective way. Thereby, we release the user from the very tedious and time consuming task of examining individual XML descriptions one by one. Our approach, termed Meta-Array Data Search (MAD Search), brings together diverse data sources while enhancing the user-friendliness of the underlying information sources. We gather metadata using different standards and construct an amalgamated service with the help of tools that discover and harvest such metadata; this service facilitates the end-user by offering easy and timely access to all metadata. The main contribution of our work is a novel query language termed xWCPS, that builds on top of two widely-adopted standards: XQuery and the Web Coverage Processing Service (WCPS). xWCPS furnishes a rich set of features regarding the way scientific data can be queried with. Our proposed unified language allows for requesting metadata while also giving processing directives. Consequently, the xWCPS-enabled MAD Search helps in both retrieval and processing of large data sets hosted in an heterogeneous infrastructure. We demonstrate the effectiveness of our approach through diverse use-cases that provide insights into the syntactic power and overall expressiveness of xWCPS. We evaluate MAD Search in a distributed environment that comprises five high-volume array-databases whose sizes range between 20 and 100 GB and so, we ascertain the applicability and potential of our proposal.

Both economic reasons and interoperation requirements necessitate the deployment of IaaS-clouds based on a share-nothing architecture. Here, live VM migration becomes a major impediment to achieving cloud-wide load balancing via selective and timely VM-migrations. Our approach is based on copying virtual disk images and keeping them synchronized during the VM migration operation. In this way, we ameliorate the limitations set by shared storage cloud designs as we place no constraints on the cloud's scalability and load-balancing capabilities. We propose a special-purpose file system, termed MigrateFS, that performs virtual disk replication within specified time-constraints while avoiding internal network congestion. Management of resource consumption during VM migration is supervised by a low-overhead and scalable distributed network of brokers. We show that our approach can reduce up to 24% the stress of already saturated physical network links during load balancing operations.

Live migration is a versatile option when it comes to attain load-balancing in IaaS-cloud architectures. Liveness, reliability and conformance to SLAs may all be achieved by moving a VM that creates excessive work from its current physical machine (PM) to a less busy node. Despite its promising features, live migration is an expensive operation in terms of resources. The situation gets further exacerbated when the movement involves PMs working off different file-systems which is often the case in shared-nothing IaaS-cloud infrastructures. In this paper, we suggest an approach that adapts the migration operation based on the I/O activity of the originating-VM. We introduce LiveFS, a FUSE-file system which traps all I/Os and helps determine how to best ship virtual disk segments across PMs in a share-nothing IaaS-cloud. Through prototyping and experimentation, we show that LiveFS can improve the shipment of VMs for diverse types of workloads. In particular, LiveFS succeeds in reducing the Total Migration Time by up to 64% compared to the "pre-copy" live migration technique. Furthermore during migration, we attain up-to 19% less I/O-delay if compared to the "post-copy" live-migration approach.

Infrastructure-as-a-Service clouds offer entire virtual infrastructures for distributed processing while concealing all physical underlying machinery. Current cloud interface abstractions restrict users from providing information regarding usage patterns of their requested virtual machines (VMs). In this paper, we propose Nefeli, a virtual infrastructure gateway that lifts this restriction. Through Nefeli, cloud consumers provide deployment hints on the possible mapping of VMs to physical nodes. Such hints include the collocation and anticollocation of VMs, the existence of potential performance bottlenecks, the presence of underlying hardware features (e.g., high availability), the proximity of certain VMs to data repositories, or any other information that would contribute in a more effective placement of VMs to physical hosting nodes. Consumers designate only properties of their virtual infrastructure and remain at all times agnostic to the cloud internal physical characteristics. The set of consumer-provided hints is augmented with high-level placement policies specified by the cloud administration. Placement policies and hints form a constraint satisfaction problem that when solved, yields the final VM-to-host placement. As workloads executed by the cloud may change over time, VM-to-host mappings must follow suit. To this end, Nefeli captures such events, changes VM deployment, helps avoid bottlenecks, and ultimately, improves the quality of the rendered services. Using our prototype, we examine overheads involved and show significant improvements in terms of time needed to execute scientific and real application workloads. We also demonstrate how power-aware policies may reduce the energy consumption of the physical installation. Finally, we compare Nefeli's placement choices with those attained by the open-source cloud middleware, OpenNebula.

Speeding cars and motorcycles constantly varying their speed, changing lanes or committing other apparent traffic violations as well as police cars and ambulances responding to incidents, are examples of vehicles that demonstrate hazardous traffic patterns. We propose a detection and a broadcasting protocol that run on top of vehicular ad-hoc networks and effectively alert drivers about such hazardous vehicles in urban environments.

Modern frameworks, such as Hadoop, combined with abundance of computing resources from the cloud, offer a significant opportunity to address long standing challenges in distributed processing. Infrastructure-as-a-Service clouds reduce the investment cost of renting a large data center while distributed processing frameworks are capable of efficiently harvesting the rented physical resources. Yet, the performance users get out of these resources varies greatly because the cloud hardware is shared by all users. The value for money cloud consumers achieve renders resource sharing policies a key player in both cloud performance and user satisfaction. In this paper, we employ microeconomics to direct the allotment of cloud resources for consumption in highly scalable master-worker virtual infrastructures. Our approach is developed on two premises: the cloud-consumer always has a budget and cloud physical resources are limited. Using our approach, the cloud administration is able to maximize per-user financial profit. We show that there is an equilibrium point at which our method achieves resource sharing proportional to each user's budget. Ultimately, this approach allows us to answer the question of how many resources a consumer should request from the seemingly endless pool provided by the cloud.

Contemporary multimedia, scientific and medical applications use indexing structures to access their high-dimensional data. Yet, in sufficiently high-dimensional spaces, conventional tree-based access methods are eventually outperformed by simple serial scans. Vector quantization has been effectively used to index data that are mostly distributed uniformly. However, in real-world applications, clustered data and skewed query distributions are the norm. In this paper, we propose DiVA, an approach that selectively adapts the quantization step to accommodate varying indexing needs. This adaptation mechanism triggers the restructuring and possible expansion of DiVA so as to provide finer indexing granularity and enhanced access performance in certain “hot” areas of the search space. User-supplied policies help both identify such “hot” areas and satisfy versatile application requirements. Experimentation with our detailed prototype shows that in a real-world data set, DiVA yields up-to 64%reduced I/O compared to competing methods such as the VA-file and the A-tree.

A fundamental application in vehicular ad-hoc networks (VANETs) is the discovery of available parking spaces as vehicles navigate through urban road networks. Vehicles are now capable of finding such parking spots using their on-board sensing and computational infrastructure and then they can disseminate this information for use by other members of the travelling community in the geographic vicinity. In this context, we examine the problem of locating an available parking space for a vehicle entering an urban network of roads. Upon its entry, a vehicle has to determine the best way to visit parking spots reported to be free. In deciding this, the vehicle has to consider the time required to reach each candidate position, its distance from the final destination should the driver walk, and of course, the probability that the spot(s) will be still-free once the vehicle shows up at location. We formulate the question at hand as a Time-Varying Travelling Salesman problem and we propose an approach for computing the route that a vehicle must traverse in order to visit all parking spaces known to be available. Our method takes into account the limited computational resources of vehicles and attempts to find the best feasible trip. This is done in conjunction with a cost function that estimates the probability to find a space filled. In order to ascertain the effectiveness of our proposal, we compare it with a best-first approach and examine computational overheads. We also investigate how close to optimal results our approach comes.

Abstract Users expect applications to successfully cope with the expansion of information as necessitated by the continuous inclusion of novel types of content. Given that such content may originate from ‘not‐seen thus far’ data collections and/or data sources, the challenging issue is to achieve the return of investment on existing services, adapting to new information without changing existing business‐logic implementation. To address this need, we introduce DOLAR (Data Object Language And Runtime), a service‐neutral framework which virtualizes the information space to avoid invasive, time‐consuming, and expensive source‐code extensions that frequently break applications. Specifically, DOLAR automates the introduction of new business‐logic objects in terms of the proposed virtual ‘content objects’. Such user‐specified virtual objects align to storage artifacts and help realize uniform ‘store‐to‐user’ data flows atop heterogeneous sources, while offering the reverse ‘user‐to‐store’ flows with identical effectiveness and ease of use. In addition, the suggested virtual object composition schemes help decouple business logic from any content origin, storage and/or structural details, allowing applications to support novel types of items without modifying their service provisions. We expect that content‐rich applications will benefit from our approach and demonstrate how DOLAR has assisted in the cost‐effective development and gradual expansion of a production‐quality digital library. Experimentation shows that our approach imposes minimal overheads and DOLAR‐based applications scale as well as any underlying datastore(s). Copyright © 2011 John Wiley & Sons, Ltd.

Virtualization of computer systems has made feasible the provision of entire distributed infrastructures in the form of services. Such services do not expose the internal operational and physical characteristics of the underlying machinery to either users or applications. In this way, infrastructures including computers in data-centers, clusters of workstations, and networks of machines are shrouded in "clouds". Mainly through the deployment of virtual machines, such networks of computing nodes become cloud-computing environments. In this paper, we propose Nefeli, a virtual infrastructure gateway that is capable of effectively handling diverse workloads of jobs in cloud environments. By and large, users and their workloads remain agnostic to the internal features of clouds at all times. Exploiting execution patterns as well as logistical constraints, users provide Nefeli with hints for the handling of their jobs. Hints provide no hard requirements for application deployment in terms of pairing virtual-machines to specific physical cloud elements. Nefeli helps avoid bottlenecks within the cloud through the realization of viable virtual machine deployment mappings. As the types of jobs change over time, deployment mappings must follow suit. To this end, Nefeli offers mechanisms to migrate virtual machines as needed to adapt to changing performance needs. Using our prototype system, we show significant improvements in overall time needed and energy consumed for the execution of workloads in both simulated and real cloud computing environments.

Recent work has demonstrated that readings provided by commodity sensor nodes are often of poor quality. In order to provide a valuable sensory infrastructure for monitoring applications, we first need to devise techniques that can withstand "dirty" and unreliable data during query processing. In this paper we present a novel aggregation framework that detects suspicious measurements by outlier nodes and refrains from incorporating such measurements in the computed aggregate values. We consider different definitions of an outlier node, based on the notion of a user-specified minimum support, and discuss techniques for properly routing messages in the networkin order to reduce the bandwidth consumption and the energy drain during the query evaluation. In our experiments using real and synthetic traces we demonstrate that: (i) a straightforward evaluation of a user aggregate query leads to practically meaningless results due to the existence of outliers; (ii) our techniques can detect and eliminate spurious readings without any application specific knowledge of what constitutes normal behavior; (iii) the identification of outliers, when performed inside the network, significantly reduces bandwidth and energy drain compared to alternative methods that centrally collect and analyze all sensory data; and (iv) we can significantly reduce the cost of the aggregation process by utilizing simple statistics on outlier nodes and reorganizing accordingly the collection tree.

The predicates in a non-equi-join can be anything but equality relations. Non-equi-join predicates can be as simple as an inequality expression between two join relation fields, or as complex as a user-defined function that carries out arbitrary complex comparisons. The nature of non-equi-join calls for predicate evaluation over all possible combinations of tuples in a two-way join. In this paper, we consider the family of fragment and replicate join algorithms that facilitates non-equijoin evaluation and adapt it in a Smart Disk environment. We use Smart Disk as an umbrella term for a variety of different storage devices featuring an embedded processor that may offload data processing from the main CPU. Our approach partially replicates one of the join relations in order to harness all processing capacity in the system. However, partial replication introduces problems with synchronizing concurrent algorithmic steps, load balancing, and selection among different join evaluation alternatives.We use a processing model to avoid performance pitfalls and autonomously select algorithm parameters. Through experimentation we find our proposed algorithms to utilize all system resources and, thus, yield better performance.

Existing GRID infrastructures rely on explicit user instructions in order to replicate files for the purposes of resiliency. This human-intensive process is inefficient, error prone and, more importantly, makes file replication in GRIDs a cumbersome task. To address this problem, we introduce FlexFS - a fully automated file-system framework that seamlessly plugs into existing GRID structures providing automated file replication and transparent-to-user resilience. FlexFS breaks apart files into blocks and injects resilient information into these blocks through the use of Forward Erasure Correction codes. FlexFS employs a number of methods that facilitate the automated storage and efficient retrieval of the blocks in order to provide I/O throughput similar to that of local hard disks, all in the face of ever-changing utilization and availability of the GRID resources. Compared to currently available GRID replication schemes, FlexFS attains 15% to 230% higher throughput, both for reading and writing files.

Intrusion prevention systems (IPSs) not only attempt to detect attacks but also block malicious traffic and pro-actively tear down pertinent network connections. To effectively thwart attacks, IPSs have to operate both in real-time and inline fashion. This dual mode renders the design/implementation and more importantly the testing of IPSs a challenge. In this paper, we propose an IPS testing framework termed IPS Evaluator which consists of a trace-driven inline simulator-engine, mechanisms for generating and manipulating test cases, and a comprehensive series of test procedures. The engine features attacker and victim interfaces which bind to the external and internal ports of an IPS-under-testing (IUT). Our engine employs a bi-directional injection policy to ensure that replayed packets are subject to security inspection by the IUT before they are forwarded. Furthermore, the send-and-receive mechanism of our engine allows for the correlation of engine-replayed and IUT-forwarded packets as well as the verification of IUT actions on detected attacks. Using dynamic addressing and routing techniques, our framework rewrites both source and destination addresses for every replayed packet on-the-fly. In this way, replayed packets conform to the specific features of the IUT. We propose algorithms to partition attacker/victim-emanated packets so that they are subjected to security inspections by the IUT and in addition, we offer packet manipulation operations to shape replayed traces. We discuss procedures that help verify the IUT's detection and prevention accuracy, attack coverage and behavior under diverse traffic patterns. Finally, we evaluate the strengths of our framework by mainly examining the open-source IPS Snort-Inline. IPS deficiencies revealed during testing help establish the effectiveness of our approach.

Intrusion detection/prevention systems (IDSs/IPSs) heavily rely on signature databases and pattern matching (PM) techniques to identify network attacks. The engines of such systems often employ traditional PM algorithms to search for telltale patterns in network flows. The observations that real-world network traffic is largely legitimate and that telltales manifested by exploits rarely appear in network streams lead us to the proposal of Fingerprinter. This framework integrates fingerprinting and PM methods to rapidly distinguish well-behaved from malicious traffic. Fingerprinter produces concise digests or fingerprints for attack signatures during its programming phase. In its querying phase, the framework quickly identifies attack-free connections by transforming input traffic into its fingerprint space and matching its digest against those of attack signatures. If the legitimacy of a stream cannot be determined by fingerprints alone, our framework uses the Boyer–Moore algorithm to ascertain whether attack signatures appear in the stream. To reduce false matches, we resort to multiple fingerprinting techniques including Bloom–Filter and Rabin–Fingerprint. Experimentation with a prototype and a variety of traces has helped us establish that Fingerprinter significantly accelerates the attack detection process.

In this paper we discuss a robust aggregation framework that can detect spurious measurements and refrain from incorporating them in the computed aggregate values. Our framework can consider different definitions of an outlier node, based on a specified minimum support. Our experimental evaluation demonstrates the benefits of our approach.

In this paper we present algorithms for building and maintaining efficient collection trees that provide the conduit to disseminate data required for processing monitoring queries in a wireless sensor network. We introduce and formalize the notion of event monitoring queries and demonstrate that they can capture a large class of monitoring applications. We then show techniques which, using a small set of intuitive statistics, can compute collection trees that minimize important resources such as the number of messages exchanged among the nodes or the overall energy consumption. Our experiments demonstrate that our techniques can organize the data collection process while utilizing significantly lower resources than prior approaches.

The problem of flash data dissemination refers to spreading dynamically-created medium-sized data to all members of a large group of users. In this paper, we explore a solution to the problem of flash data dissemination in unstructured P2P networks and propose a gossip-based protocol, termed Catalogue-Gossip. Our protocol alleviates the shortcomings of prior gossip-based dissemination approaches through the introduction of an efficient catalogue exchange scheme that helps reduce unnecessary interactions among nodes in the unstructured network. We provide deterministic guarantees for the termination of the protocol and suggest optimizations concerning the order with which pieces of flash data are assembled at receiving peers. Experimental results show that Catalogue-Gossip is significantly more efficient than existing solutions when it comes to delivery of flash data.

Sessions generated by Instant Messaging and Peer-to-Peer systems (IM/P2Ps) not only consume considerable bandwidth and computing resources but also dramatically change the characteristics of data flows affecting both the operation and performance of networks. Most IM/P2Ps have known security loopholes and vulnerabilities making them an ideal platform for the dissemination of viruses, worms, and other malware. The lack of access control and weak authentication on shared resources further exacerbates the situation. Should IM/P2Ps be deployed in production environments, performance of conventional applications may significantly deteriorate and enterprise data may be contaminated. It is therefore imperative to identify, monitor and finally manage IM/P2P traffic. Unfortunately, this task cannot be easily attained as IM/P2Ps resort to advanced techniques to hide their traces including multiple channels to deliver services, port hopping, message encapsulation and encryption. In this paper, we propose an extensible framework that not only helps to identify and classify IM/P2P-generated sessions in real time but also assists in the manipulation of such traffic. Consisting of four modules namely, session manager, traffic assembler, IM/P2P dissector, and traffic arbitrator, our proposed framework uses multiple techniques to improve its traffic classification accuracy and performance. Through fine-tuned splay and interval trees that help organize IM/P2P sessions and packets in data streams, we accomplish stateful inspection, traffic re-assembly, data stream correlation, and application layer analysis that combined will boost the framework's identification precision. More importantly, we introduce IM/P2Ps "plug-and-play" protocol analyzers that inspect data streams according to their syntax and semantics; these analyzers render our framework easily extensible. Identified IM/P2P sessions can be shaped, blocked, or disconnected, and corresponding traffic can be stored for forensic analysis and threat evaluation. Experiments with our prototype show high IM/P2Ps detection accuracy rates under diverse settings and excellent overall performance in both controlled and real-world environments.

Abstract A Remote Administration Trojan (RAT) allows an attacker to remotely control a computing system and typically consists of a server invisibly running and listening to specificTCP/UDPports on a victim machine as well as a client acting as the interface between the server and the attacker. The accuracy of host and/or network‐based methods often employed to identifyRATshighly depends on the quality of Trojan signatures derived from static patterns appearing inRATprograms and/or their communications. Attackers may also obfuscate such patterns by havingRATsuse dynamic ports, encrypted messages, and even changing Trojan banners. In this paper, we propose a comprehensive framework termedRAT Catcher, which reliably detects and ultimately blocksRATmalicious activities even when Trojans use multiple evasion techniques. Employing network‐based methods and functioning ininlinemode to inspect passing packets in real time, ourRAT Catchercollects and maintains status information for every connection and conducts session correlation to greatly improve detection accuracy. TheRAT Catcherre‐assembles packets in each data stream and dissects the resulting aggregation according to known Trojan communication protocols, further enhancing its traffic classification. By scanning not only protocol headers but also payloads,RAT Catcheris a truly application‐layer inspector that performs a range of corrective actions on identified traffic including alerting, packet dropping, and connection termination. We show the effectiveness and efficiency ofRAT Catcherwith experimentation in both laboratory and real‐world settings. Copyright © 2007 John Wiley & Sons, Ltd.

The emergence of applications producing continuous high-frequency data streams has brought forth a large body of research in the area of distributed stream processing. In presence of high volumes of data, efforts have primarily concentrated on providing approximate aggregate or top-k type results. Scalable solutions for providing answers to window join queries in distributed stream processing systems have received limited attention to date. We provide a solution for the window join in a distributed stream processing system which features reduced inter-node communications achieved through automatic throughput handling based on resource availability. Our approach is based on incrementally updated discrete Fourier transforms (DFTs). Furthermore, we provide formulae for computingDFT compression factors in order to achieve information reduction. We perform WAN-based prototype experiments to ascertain the viability and establish the effectiveness of our method. Our experimental results reveal that our method scales in terms of throughput and error rates, achieving sub-linear message complexity in domains that exhibit a geographic skew in the joining attributes.

By penetrating into a large number of machines and stealthily installing malicious pieces of code, a distributed denial of service (DDoS) attack constructs a hierarchical network and uses it to launch coordinated assaults. DDoS attacks often exhaust the network bandwidth, processing capacity and information resources of victims, thus, leading to unavailability of computing systems services. Various defense mechanisms for the detection, mitigation and/or prevention of DDoS attacks have been suggested including resource redundancy, traceback of attack origins and identification of programs with suspicious behavior. Contemporary DDoS attacks employ sophisticated techniques including formation of hierarchical networks, one-way communication channels, encrypted messages, dynamic ports allocation and source address spoofing to hide the attackers' identities; such techniques make both detection and tracing of DDoS activities a challenge and render traditional DDoS defense mechanisms ineffective. In this paper, we propose the DDoS Container, a comprehensive framework that uses network-based detection methods to overcome the above complex and evasive types of attacks; the framework operates in ‘inline’ mode to inspect and manipulate ongoing traffic in real-time. By keeping track of connections established by both potential DDoS attacks and legitimate applications, the suggested DDoS Container carries out stateful inspection on data streams and correlates events among sessions. The framework performs stream re-assembly and dissects the resulting aggregations against protocols followed by various known DDoS attacks facilitating their identification. The traffic pattern analysis and data correlation of the framework further enhance its detection accuracy on DDoS traffic camouflaged with encryption. Actions available on identified DDoS traffic range from simple alerting to message blocking and proactive session termination. Experimentation with the prototype of our DDoS Container shows its effectiveness in classifying DDoS traffic.

Building footprint simplification is of critical importance to radio propagation predictions in wireless communication systems as the prediction time is closely related to the number of both buildings and vertices involved. Intuitively, if the complexity of footprints (i.e. the number of vertices in the footprints) is reduced, predictions can be generated more quickly. However, such reductions often affect the accuracy of results as the simplification error constrains the efficiency that can be achieved. To achieve a good vertex reduction rate for the footprints involved and at the same time preserve the shapes of footprints in terms of their areas, orientations and centroids, we propose a number of efficient single-pass methods to simplify building footprints. To satisfy constraints on edges, areas and centroids of simplified footprints, multi-pass methods are suggested. Hybrid methods take advantage of complementary properties exhibited by different footprint simplification methods. We assess the baseline effectiveness of our proposed techniques, and carry out an extensive comparative evaluation with real geographic information system data from different municipalities. Through experimentation, we find that hybrid methods deliver the best performance in both vertex reduction rate and simplification error. We examine the effects that these footprint simplification methods have on the ray-tracing based radio propagation prediction systems in terms of processing time and prediction accuracy. Our experiments show that footprint simplification methods indeed reduce prediction time up to three-fold, and maintain prediction accuracy with high confidence as well. We also investigate the relationship between footprint simplification error and the prediction accuracy. We find that the prediction accuracy is sensitive to the distortion (i.e. change of shape) of building footprints. This helps us to better understand the trade-off between precision of the building database and the accuracy of predictions generated by ray-tracing based radio propagation prediction systems.

Conventional two-tier databases have shown performance limitations in the presence of many concurrent clients. We propose logical grouping of clients (or clustering) as the means to improve the performance of collaborative networked databases. In this paper, we discuss a three-tier client-server database architecture (3t-CSD) featuring the above partitioning. The proposed clustering is based on the similarity of clients' access patterns. Each cluster is supervised by a designated manager that coordinates data sharing among its members. A number of clients is optimally partitioned if sites in each individual cluster have the maximum common data access probability possible. We initially show that the optimal client clustering problem is NP-complete and then we develop two approximate solutions based on abstraction and filtering of statistics for client access patterns. Our main goal is to compare the performance of the conventional and three-tier client-server database architecture with respect to the transaction turnaround times and object response times. After developing system prototypes that implement both two-tier and 3t-CSDs, we experimentally show that as long as good client-clustering is possible, the 3t-CSD architecture yields sizable gains over its conventional counterpart. We also compare and evaluate the effectiveness of the two proposed techniques used to create client clusters. Finally, we examine the role of several preprocessing schemes used to reduce the volume of the input data supplied to the clustering techniques.

In this paper we present EasyTransport, a tool that offers effective navigation and/or transportation advice to travelers in wide geographic areas. Unlike most existing navigational and transportation advisory systems that utilize predefined paths connecting transition points and produce answers based on static information, EasyTransport uses no precompiled knowledge to generate the respective paths. The tool's underlying algorithm is based on the breadth-first-search (BFS) algorithm and traces dynamically feasible routes on a terrain. Our rationale is to reduce the number of nodes representing the possible points for a transition and thus the complexity of EasyTransport's operation. Since our algorithm functions with increasingly coarse geographic granularities, it can achieve its successful termination fast. We, furthermore, suggest heuristics that effectively manage the potentially enormous data sets in the geographic areas involved EasyTransport, is a highly interactive system that allows for easy querying and features flexible adaptation and presentation of the generated answers, ensures short response times, and offers useful getting-a round-and-how guidelines.

We propose and experimentally evaluate the use of the client-server database paradigm for real-time processing. To date, the study of transaction processing with time constraints has mostly been restricted to centralized or "single-node" systems. Recently, client-server databases have exploited locality of data accesses in real-world applications to successfully provide reduced transaction response times. Our objective is to investigate the feasibility of real-time processing in a data-shipping client-server database architecture. We compare the efficiency of the proposed architecture with that of a centralized real-time database system. We discuss transaction scheduling issues in the two architectures and propose a new policy for scheduling transactions in the client-server environment. This policy assigns higher priorities to transactions that have a greater potential for successful completion through the use of locally available data. We investigate the effects of client data-access locality and various updating workloads on transaction completion rates. Our experimental results show that real-time client-server databases can provide significant performance gains over their centralized counterparts. These gains become evident when large numbers of clients (more than 40) are attached per server, even in the presence of high data contention.

Upper bounds on the scalability of client-server databases (CSDs) persist due to long delays experienced at the servers' queues. To this end, we have proposed a three-tier architecture that exploits similarities in object access behavior demonstrated by clients. Clients are statically grouped into logical clusters and object requests can be then served in an "internal to cluster" fashion. This is achieved with the introduction of an intermediate directory tier. Good client clustering yields more scalable CSD configurations as it minimizes the number of inter-cluster data accesses. We introduce the problem of client realignment in light of changing client localities and propose an online reclustering framework to address it. Online reclustering facilitates adaptive reconfiguration and redistribution of sites. The core of our proposal is a change detection approach that uses meta-data extracted from observed clients' access patterns. We evaluate the impact of employing a multi-featured change detection scheme in the three-tier CSD architecture and experimentally investigate its performance and trade-offs involved.

We present an approach for indexing animated objects and efficiently answering queries about their position in time and space. In particular, we consider an animated movie as a spatiotemporal evolution. A movie is viewed as an ordered sequence of frames, where each frame is a 2D space occupied by the objects that appear in that frame. The queries of interest are range queries of the form, "find the objects that appear in area S between frames f/sub i/ and f/sub j//sup "/ as well as nearest neighbor queries such as, "find the q nearest objects to a given position A between frames f/sub i/ and f/sub j//sup "/. The straightforward approach to index such objects considers the frame sequence as another dimension and uses a 3D access method (such as an R-Tree or its variants). This, however, assigns long "lifetime" intervals to objects that appear through many consecutive frames. Long intervals are difficult to cluster efficiently in a 3D index. Instead, we propose to reduce the problem to a partial-persistence problem. Namely, we use a 2D access method that is made partially persistent. We show that this approach leads to faster query performance while still using storage proportional to the total number of changes in the frame evolution, What differentiates this problem from traditional temporal indexing approaches is that objects are allowed to move and/or change their extent continuously between frames. We present novel methods to approximate such object evolutions, We formulate an optimization problem for which we provide an optimal solution for the case where objects move linearly. Finally, we present an extensive experimental study of the proposed methods. While we concentrate on animated movies, our approach is general and can be applied to other spatiotemporal applications as well.

In a conventional client-server database system (CS-DBS), a transaction and its requisite data have to be colocated at a single site for the operation to proceed. This has traditionally been achieved by moving either the data or the transaction. Today, the availability of powerful workstations and high-bandwidth networking options has led users to expect real-time guarantees about the completion times of their tasks. So as to offer such guarantees in a CS-DBS, a transaction should be processed by any means that allows it to meet its deadline. In this paper we explore the option of moving both transactions and data to the most promising sites for successful completion. We propose a load-sharing mechanism that oversees the shipment of data and transactions in order to increase the efficiency of a client-server cluster. Additionally, we make use of the concept of grouped locks to schedule the movement of data objects in the cluster in a more efficient manner. An experimental evaluation shows that the use of our load-sharing algorithm provides a considerable improvement in the real-time processing efficiency of a CS-DBS even in the presence of very high volumes of update transactions.

In conventional two-tier client-server databases, clients access and modify shared data resident in a common server. As the number of clients increases, the centralized database server can become a performance bottleneck. In order to overcome this scalability problem, a three-tier client-server configuration has been proposed that features the partitioning of clients into logical clusters. Here, the objective is to maximize the data sharing among the clients in each cluster. We propose a genetic algorithm to create such client clusters and evaluate two different techniques for generating the initial solution populations. We compare the performance of the two-tier and three-tier configurations with respect to the transaction turnaround times and object response times. Our experimental results indicate that the clustered architecture can offer improved performance over its two-tier counterpart.

Shows that there is scope for replication in data-shipping client-server DBMSs, offering opportunities for improved transaction response times. To support this replication, we describe a two-stage protocol for transaction processing (2STP). We extend the conventional client-server data-shipping mechanism by allowing clients to update and query cached objects that have replicas in multiple sites. We use the concept of acceptance criteria to provide a means for the flexible handling of client updates. The effectiveness of the two-stage transaction processing mechanism is supported by means of queuing analysis and detailed simulation experiments comparing 2STP with a global lock-based data-shipping protocol. This improvement in transaction processing efficiency is achieved at the cost of longer downtimes for crash recovery.

Computer systems deployed in contemporary industrial and production environments typically involve a large number of workers who work simultaneously to draft new components and/or trace provided services. Efficient database support for such systems is crucial. The handling of high volume data among various sites of a network based infrastructure poses new challenges as it can be only carried out by aggregates of data servers and powerful workstations/PCs (clients). Operating in such environments, client/server databases (C/S DBSs) (M. Carey et al., 1991) have shown reduced response times for client transactions over their centralized counterparts. Previous work has indicated, however, that when the number of clients attached per server becomes large, C/S DBSs fail to guarantee satisfactory performance rates. This is known as the scalability problem. Client object caching is used as a mechanism to improve system scalability by easing resource contention at the server sites. Design and manufacturing databases display different operational characteristics from their conventional counterparts as they routinely support multiple and mostly independent projects. In such settings, a group of cooperating designers or workers achieve a complex task by closely interacting among themselves and dynamically sharing design data. We exploit the aforementioned feature of design and manufacturing databases, and propose a cluster based caching configuration. The cluster based configuration groups sites according to the similarity of their access patterns. This results in improved client performance rates and offers better scalability.

The Client-Server computing paradigm has significantly influenced the way modern Database Management Systems are designed and built. In such systems, clients maintain data pages in their main-memory caches, originating from the server's database. The Enhanced Client-Server architecture takes advantage of all the available client resources, including their long-term memory. Clients can cache server data into their own disk units if these data are part of their operational spaces. However, when updates occur at the server, a number of clients may need to not only be notified about these changes, but also obtain portions of the updates as well. In this paper, we examine the problem of managing server imposed updates that affect data cached on client disk managers. We propose a number of server update propagation techniques in the context of the Enhanced Client-Server DBMS architecture, and examine the performance of these strategies through detailed simulation experiments. In addition, we study how the various settings of the network affect the performance of these policies.

Increasingly larger data sets are being stored in networked architectures. Many of the available data structures are not easily amenable to parallel realizations. Hashing schemes show promise in that respect for the simple reason that the underlying data structure can be decomposed and spread among the set of cooperating nodes with minimal communication and maintenance requirements. In all cases, storage utilization and load balancing are issues that need to be addressed. One can identify two basic approaches to tackle the problem. One way is to address it as part of the design of the data structure that is used to store and retrieve the data. The other is to maintain the data structure intact but address the problem separately. The method that we present here falls in the latter category and is applicable whenever a hash table is the preferred data structure. Intrinsically attached to the used hash table is a hashing function that allows one to partition a possibly unbounded set of data items into a finite set of groups; the hashing function provides the partitioning by assigning each data item to one of the groups. In general, the hashing function cannot guarantee that the various groups will have the same cardinality on average, for all possible data item distributions. In this paper, we propose a two-stage methodology that uses the knowledge of the hashing function to reorganize the group assignments so that the resulting groups have similar expected cardinalities. The method is generally applicable and independent of the used hashing function. We show the power of the methodology using both synthetic and real-world databases. The derived quasi-uniform storage occupancy and associated load-balancing gains are significant.

Modern high-performance computing systems and databases are implemented under the assumption that a very large proportion of the data used can now be maintained in volatile memory. In this paper, we compare experimentally two recently proposed self-adjusting access structures that can be used to organize data in such settings, namely, the Skip-List (SL) and the Binary B-Tree (BB-Tree). We examine the scalability of these two methods against both mixed and pure-query workloads. Our experiments reveal the behaviour of SLs and BB-Trees under diverse environments and varying data requirements.

Component reuse is widely considered vital for obtaining significant improvement in development productivity. However, as an organization adopts a reuse-oriented development process, the nature of the problems in development is likely to change. In this article, we use a measurement-based approach to better understand and evaluate an evolving reuse process. More specifically, we study the effects of reuse across seven projects in narrow domain from a single development organization. An analysis of the errors that occur in new and reused components across all phases of system development provides insight into the factors influencing the reuse process. We found significant differences between errors associated with new and various types of reused components in terms of the types of errors committed. In addition, we identified differences when errors are introduced and the effect that the errors have on the development process.

Workflow systems are receiving increased attention as they intend to facilitate the operations of enterprises by coordinating and streamlining business activities. The need for automated support and operational models that allow workflow applications to coordinate units of work across multiple servers-according to business defined rules and routes-is becoming critical for the proper management of such activities. In this paper, we describe a Transaction-Oriented Workflow Environment (TOWE) for programming workflow activities. The novelty of our approach resides in the proposed unified abstraction, class libraries, to support workflow activities. The fundamental concept used in the TOWE system is based on the symbiosis of object-oriented programming and interprocess communication concepts. In TOWE, the concurrency abstractions are represented by process objects, active objects acting as processes, which involve asynchronous, location-independent, and application specific process invocations.

Providing a general purpose programming environment that supports the definition of, and exercises control over, the flow of execution of long-running activities is highly beneficial for a variety of client/server distributed data-intensive applications. In this paper, we present a Transaction-Oriented Work-Flow Environment (TOWE) for the programming of long-lived activities through a set of class libraries. The TOWE is based on an amalgamation of object-oriented programming with distributed interprocess communication concepts. The concurrency abstractions provided by TOWE are objects, acting like processes, and involve an asynchronous, location-independent, mode of process invocation coupled with data-driven synchronization of processes.

The merging of distributed computing and object-oriented technology has resulted in novel ways to design and develop modern and aggregate architectures of databases. Distributed object management has emerged as the core technology of this trend, and the CORBA specifications attempt to manage such environments. In this paper, we examine the CORBA architecture, both as a distributed object management framework as well as a service to interoperate persistent objects. We report on using two off-the-shelf DBMSs (ONTOS and UniSQL) as a testbed for a feasibility study.

The size of data shipped over networks of distributed databases has increased substantially with the introduction of multimedia and high performance systems. Therefore, there is a need to understand the behavior and the trade-offs of available data communication abstractions in such settings. In this paper, we consider parameters associated with the abstractions, the impact of their implementation on throughput, and we compare the performance of BSD sockets (TCP, UDP), System V TLI (TCP), and SunOS RPCs (TCP) in the presence of large messages. In such environments, segmentation overhead of UDP messages at the user level outweighs other considerations such as optimal mbuf allocation and full ethernet bandwidth usage. In addition, it is found that the size of buffer areas allocated to TCP sockets gains further impedance when sending large messages. We also find that communication induced paging significantly deteriorates the data transmission throughput and suggest a policy to avoid this problem.

The client-server DBMS model has emerged as the main paradigm in database computing. The enhanced client-server architecture takes advantage of all the available client resources including their disk managers. Clients can cache server data into their own disk units if data are part of their operational space. However, when updates occur at the server, some of the client data managers may need to not only be notified about them but also obtain portions of the updates as well. In this paper, we examine the problem of managing server-imposed updates that affect client cached data. We propose a number of server update propagation techniques in the context of the enhanced client-server DBMS architecture and examine the performance of these strategies through detailed simulation experiments.>

This paper reports on the development of the data binding tool and its use in Ada source code reusability and software system design assessment. The tool was built around the metric of data bindings. Data bindings fall in the category of data visibility metrics and are used to measure inter-component interactions. Software system components are defined in the context of the Ada language using a flexible scheme. They are used, along with cluster analysis, to present structural configurations of a software system. The clustering technique as well as the tool design and its problems are discussed. The analysis of dendrograms (trees of components produced by the tool) reveals several classes of systems dendrograms and provides a simple mechanism for Ada source code reusability. Finally, the implications of different design methodologies used to develop the test software are discussed and explanations for the several types of dendrogram formulations are given.

The introduction of powerful workstations connected through local area networks (LANs) inspired new database management system (DBMS) architectures that offer high performance characteristics. The authors examine three such software architecture configurations: client-server (CS), the RAD-UNIFY type of DBMS (RU), and enhanced client-server (ECS). Their specific functional components and design rationales are discussed. Three simulation models are used to provide a performance comparison under different job workloads. Simulation results show that the RU almost always performs slightly better than the CS, especially under light workloads, and that ECS offers significant performance improvement over both CS and RU. Under reasonable update rates, the ECS over CS (or RU) performance ratio is almost proportional to the number of participating clients (for less than 32 clients). The authors also examine the impact of certain key parameters on the performance of the three architectures and show that ECS is more scalable that the other two.>

Issues pertinent to the concurrent execution of rules in a database management system (DBMS) are studied. Rules are modeled as database transactions. As such, they should follow serializability as their correctness criterion for execution. Rule execution has the additional constraint that the rules, conditions must be true in the database for the actions that execute, and rules must fail when their conditions are not true any longer. Based on this observation, two locking-based protocols are discussed. Information on the possible conflicts between conditions and actions of rules is used to provide greater concurrent access to the relations, based on a new lock paradigm. A simulation testbed was developed in order to study the rule features and database characteristics that play an important role in the performance of concurrent production rule execution.>

Automatic intelligent fire-code checking is examined. A general approach is considered, wherein engineering code requirements are encoded in a knowledge-based expert system which evaluates a design for overall conformance. The system consists of a frame system, a rule system and a set of geometric algorithms. It identifies code violations and generates a report listing them. A number of the supporting algorithms for eliciting knowledge are discussed.>