Mining patterns from graph traversals

In data models that have graph representations, users navigate following the links of the graph structure. Conducting data mining on collected information about user accesses in such models, involves the determination of frequently occurring access sequences. In this paper, the problem of finding traversal patterns from such collections is examined. The determination of patterns is based on the graph structure of the model. For this purpose, three algorithms, one which is level-wise with respect to the lengths of the patterns and two which are not are presented. Additionally, we consider the fact that accesses within patterns may be interleaved with random accesses due to navigational purposes. The definition of the pattern type generalizes existing ones in order to take into account this fact. The performance of all algorithms and their sensitivity to several parameters is examined experimentally.     

Mining association rules in very large clustered domains

Emerging applications introduce the requirement for novel association-rule mining algorithms that will be scalable not only with respect to the number of records (number of rows) but also with respect to the domain's size (number of columns). In this paper, we focus on the cases where the items of a large domain correlate with each other in a way that small worlds are formed, that is, the domain is clustered into groups with a large number of intra-group and a small number of inter-group correlations. This property appears in several real-world cases, e.g., in bioinformatics, e-commerce applications, and bibliographic analysis, and can help to significantly prune the search space so as to perform efficient association-rule mining. We develop an algorithm that partitions the domain of items according to their correlations and we describe a mining algorithm that carefully combines partitions to improve the efficiency. Our experiments show the superiority of the proposed method against existing algorithms, and that it overcomes the problems (e.g., increase in CPU cost and possible I/O thrashing) caused by existing algorithms due to the combination of a large domain and a large number of records.     

Efficient generation of secure elliptic curves

In many cryptographic applications it is necessary to generate elliptic curves (ECs) whose order possesses certain properties. The method that is usually employed for the generation of such ECs is the so-called Complex Multiplication method. This method requires the use of the roots of certain class field polynomials defined on a specific parameter called the discriminant. The most commonly used polynomials are the Hilbert and Weber ones. The former can be used to generate directly the EC, but they are characterized by high computational demands. The latter have usually much lower computational requirements, but they do not directly construct the desired EC. This can be achieved if transformations of their roots to the roots of the corresponding (generated by the same discriminant) Hilbert polynomials are provided. In this paper we present a variant of the Complex Multiplication method that generates ECs of cryptographically strong order. Our variant is based on the computation of Weber polynomials. We present in a simple and unifying manner a complete set of transformations of the roots of a Weber polynomial to the roots of its corresponding Hilbert polynomial for all values of the discriminant. In addition, we prove a theoretical estimate of the precision required for the computation of Weber polynomials for all values of the discriminant. We present an extensive experimental assessment of the computational efficiency of the Hilbert and Weber polynomials along with their precision requirements for various discriminant values and we compare them with the theoretical estimates. We further investigate the time efficiency of the new Complex Multiplication variant under different implementations of a crucial step of the variant. Our results can serve as useful guidelines to potential implementers of EC cryptosystems involving generation of ECs of a desirable order on resource limited hardware devices or in systems operating under strict timing response constraints. This work was partially supported by the IST Programme of EC under contract no. IST-2001-33116 (FLAGS), and by the Action IRAKLITOS (Fellowships for Research in the University of Patras) with matching funds from ESF (European Social Fund) and the Greek Ministry of Education.     

Optimal resource allocation for Medium Grain Scalable video transmission over MIMO channels

In this paper we investigate an optimal solution for adaptive H.264/SVC video transmission over Multiple-Input Multiple-Output (MIMO) channels.We first write the end-to-end distortion of the H.264/SVC video transmission over a diagonal MIMO channel. The total distortion is expressed following three physical layer parameters: power allocation, modulation spectral efficiency and Error Code Correction (ECC) code rate. Minimizing the total distortion is considered as an optimization problem containing both discrete and continuous variables.We use the Lagrangian method associated with Karush–Kuhn and Tucker conditions to find out the optimal continuous physical layer parameters. Concerting the discrete modulation spectral efficiency and ECC code rate, we exploit information of the MIMO system to remove all suboptimal configurations. Therefore, the optimal power allocation is computed only for a reduced number of discrete configurations.The performance of the proposed solution is evaluated over both statistical and realistic MIMO channels. Results show that the proposed solution performs an optimal resource allocation to achieve the best QoS regardless the channel conditions.     

A Si 1.8 GHz RLC filter with tunable center frequency and qualityfactor

A second-order active bandpass filter using integrated inductors was implemented in Si bipolar technology. The filter uses special techniques to make the quality factor and the center frequency tunable. For a nominal center frequency of 1.8 GHz and a quality factor of 35, the filter has 1 dB compression dynamic range of 40 dB, and draws 8.7 mA from a 2.8 V supply     

A 1-V 5-GHz CMOS Multiple Magnetic Feedback Receiver Front-End

In this paper, a receiver front-end module operating at 5 GHz and suitable for low-voltage operation is presented. The design consists of a single amplifying transistor low-noise amplifier topology that utilizes multiple magnetic feedback in order to simultaneously achieve high gain and high reverse isolation. In addition, a mixer topology for optimum performance regarding gain, noise, and linearity under low-voltage operation is presented. The design has been fabricated in IBM's 0.13-mum CMOS technology, and the measured performance indicates a receiver conversion gain of 22.3 dB, a noise figure of 2.64 dB, and a third-order input intercept point of .     

Supporting the data cube lifecycle: the power of ROLAP

The lifecycle of a data cube involves efficient construction and storage, fast query answering, and incremental updating. Existing ROLAP methods that implement data cubes are weak with respect to one or more of the above, focusing mainly on construction and storage. In this paper, we present a comprehensive ROLAP solution that addresses efficiently all functionality in the lifecycle of a cube and can be implemented easily over existing relational servers. It is a family of algorithms centered around a purely ROLAP construction method that provides fast computation of a fully materialized cube in compressed form, is incrementally updateable, and exhibits quick query response times that can be improved by low-cost indexing and caching. This is demonstrated through comprehensive experiments on both synthetic and real-world datasets, whose results have shown great promise for the performance and scalability potential of the proposed techniques, with respect to both the size and dimensionality of the fact table. The project is co-financed within Op. Education by the ESF (European Social Fund) and National Resources.     

Revisiting the cube lifecycle in the presence of hierarchies

On-line analytical processing (OLAP) typically involves complex aggregate queries over large datasets. The data cube has been proposed as a structure that materializes the results of such queries in order to accelerate OLAP. A significant fraction of the related work has been on Relational-OLAP (ROLAP) techniques, which are based on relational technology. Existing ROLAP cubing solutions mainly focus on “flat” datasets, which do not include hierarchies in their dimensions. Nevertheless, as shown in this paper, the nature of hierarchies introduces several complications into the entire lifecycle of a data cube including the operations of construction, storage, indexing, query processing, and incremental maintenance. This fact renders existing techniques essentially inapplicable in a significant number of real-world applications and mandates revisiting the entire cube lifecycle under the new perspective. In order to overcome this problem, the CURE algorithm has been recently proposed as an efficient mechanism to construct complete cubes over large datasets with arbitrary hierarchies and store them in a highly compressed format, compatible with the relational model. In this paper, we study the remaining phases in the cube lifecycle and introduce query-processing and incremental-maintenance algorithms for CURE cubes. These are significantly different from earlier approaches, which have been proposed for flat cubes constructed by other techniques and are inadequate for CURE due to its high compression rate and the presence of hierarchies. Our methods address issues such as cube indexing, query optimization, and lazy update policies. Especially regarding updates, such lazy approaches are applied for the first time on cubes. We demonstrate the effectiveness of CURE in all phases of the cube lifecycle through experiments on both real-world and synthetic datasets. Among the experimental results, we distinguish those that have made CURE the first ROLAP technique to complete the construction and usage of the cube of the highest-density dataset in the APB-1 benchmark (12 GB). CURE was in fact quite efficient on this, showing great promise with respect to the potential of the technique overall.     

Algorithms and applications for answering ranked queries using ranked views

Ranked queries return the top objects of a database according to a preference function. We present and evaluate (experimentally and theoretically) a core algorithm that answers ranked queries in an efficient pipelined manner using materialized ranked views. We use and extend the core algorithm in the described PREFER and MERGE systems. PREFER precomputes a set of materialized views that provide guaranteed query performance. We present an algorithm that selects a near optimal set of views under space constraints. We also describe multiple optimizations and implementation aspects of the downloadable version of PREFER. Then we discuss MERGE, which operates at a metabroker and answers ranked queries by retrieving a minimal number of objects from sources that offer ranked queries. A speculative version of the pipelining algorithm is described.Received: 10 June 2002, Accepted: 11 June 2002, Published online: 30 September 2003Edited by: A. MendelzonWork supported by NSF Grant No. 9734548.     

Efficient range query processing in metric spaces over highly distributed data

Similarity search in P2P systems has attracted a lot of attention recently and several important applications, like distributed image search, can profit from the proposed distributed algorithms. In this paper, we address the challenging problem of efficient processing of range queries in metric spaces, where data is horizontally distributed across a super-peer network. Our approach relies on SIMPEER (Doulkeridis et al. in Proceedings of VLDB, pp. 986–997, 2007), a framework that dynamically clusters peer data, in order to build distributed routing information at super-peer level. SIMPEER allows the evaluation of exact range and nearest neighbor queries in a distributed manner that reduces communication cost, network latency, bandwidth consumption and computational overhead at each individual peer. In this paper, we extend SIMPEER by focusing on efficient range query processing and providing recall-based guarantees for the quality of the result retrieved so far. This is especially useful for range queries that lead to result sets of high cardinality and incur high processing costs, while the complete result set becomes overwhelming for the user. Our framework employs statistics for estimating an upper limit of the number of possible results for a range query and each super-peer may decide not to propagate further the query and reduce the scope of the search. We provide an experimental evaluation of our framework and show that our approach performs efficiently, even in the case of high degree of distribution.