OpenRaiser/Intern-Atlas huggingface dataset:
Preprocessing: A Prerequisite for Discovering Patterns in Web Usage Mining Process
Venue: arXiv cs.DB 2011
Year: 2011

Web log data is usually diverse and voluminous. This data must be assembled into a consistent, integrated and comprehensive view, in order to be used for pattern discovery. Without properly cleaning, transforming and structuring the data prior to the analysis, one cannot expect to find meaningful patterns. As in most data mining applications, data preprocessing involves removing and filtering redundant and irrelevant data, removing noise, transforming and resolving any inconsistencies. In this paper, a complete preprocessing methodology having merging, data cleaning, user/session identification and data formatting and summarization activities to improve the quality of data by reducing the quantity of data has been proposed. To validate the efficiency of the proposed preprocessing methodology, several experiments are conducted and the results show that the proposed methodology reduces the size of Web access log files down to 73-82% of the initial size and offers richer logs that are structured for further stages of Web Usage Mining (WUM). So preprocessing of raw data in this WUM process is the central theme of this paper.
Parallel and Distributed Simulation: Five W's (and One H)
Venue: arXiv cs.DC 2011
Year: 2011

A well known golden rule of journalism (and many other fields too) is that if you want to know the full story about something you have to answer all the five W's (Who, What, When, Where, Why) and the H (How). This extended abstract is about what is missing in parallel and distributed simulation and how this affects its popularity.
MCA Based Performance Evaluation of Project Selection
Venue: arXiv cs.SE 2011
Year: 2011

Multi-criteria decision support systems are used in various fields of human activities. In every alternative multi-criteria decision making problem can be represented by a set of properties or constraints. The properties can be qualitative & quantitative. For measurement of these properties, there are different unit, as well as there are different optimization techniques. Depending upon the desired goal, the normalization aims for obtaining reference scales of values of these properties. This paper deals with a new additive ratio assessment method. In order to make the appropriate decision and to make a proper comparison among the available alternatives Analytic Hierarchy Process (AHP) and ARAS have been used. The uses of AHP is for analysis the structure of the project selection problem and to assign the weights of the properties and the ARAS method is used to obtain the final ranking and select the best one among the projects. To illustrate the above mention methods survey data on the expansion of optical fibre for a telecommunication sector is used. The decision maker can also used different weight combination in the decision making process according to the demand of the system.
On Gröbner Basis Detection for Zero-dimensional Ideals
Venue: arXiv cs.CC 2011
Year: 2011

The Gröbner basis detection (GBD) is defined as follows: Given a set of polynomials, decide whether there exists -and if "yes" find- a term order such that the set of polynomials is a Gröbner basis. This problem was shown to be NP-hard by Sturmfels and Wiegelmann. We show that GBD when studied in the context of zero dimensional ideals is also NP-hard. An algorithm to solve GBD for zero dimensional ideals is also proposed which runs in polynomial time if the number of indeterminates is a constant.
A Sensing Error Aware MAC Protocol for Cognitive Radio Networks
Venue: arXiv cs.IT 2011
Year: 2011

Cognitive radios (CR) are intelligent radio devices that can sense the radio environment and adapt to changes in the radio environment. Spectrum sensing and spectrum access are the two key CR functions. In this paper, we present a spectrum sensing error aware MAC protocol for a CR network collocated with multiple primary networks. We explicitly consider both types of sensing errors in the CR MAC design, since such errors are inevitable for practical spectrum sensors and more important, such errors could have significant impact on the performance of the CR MAC protocol. Two spectrum sensing polices are presented, with which secondary users collaboratively sense the licensed channels. The sensing policies are then incorporated into p-Persistent CSMA to coordinate opportunistic spectrum access for CR network users. We present an analysis of the interference and throughput performance of the proposed CR MAC, and find the analysis highly accurate in our simulation studies. The proposed sensing error aware CR MAC protocol outperforms two existing approaches with considerable margins in our simulations, which justify the importance of considering spectrum sensing errors in CR MAC design.
Downlink Power Allocation for Stored Variable-Bit-Rate Videos
Venue: arXiv cs.IT 2011
Year: 2011

In this paper, we study the problem of power allocation for streaming multiple variable-bit-rate (VBR) videos in the downlink of a cellular network. We consider a deterministic model for VBR video traffic and finite playout buffer at the mobile users. The objective is to derive the optimal downlink power allocation for the VBR video sessions, such that the video data can be delivered in a timely fashion without causing playout buffer overflow and underflow. The formulated problem is a nonlinear nonconvex optimization problem. We analyze the convexity conditions for the formulated problem and propose a two-step greedy approach to solve the problem. We also develop a distributed algorithm based on the dual decomposition technique. The performance of the proposed algorithms are validated with simulations using VBR video traces under realistic scenarios.
A simpler and more efficient algorithm for the next-to-shortest path problem
Venue: arXiv cs.DS 2011
Year: 2011

Given an undirected graph $G=(V,E)$ with positive edge lengths and two vertices $s$ and $t$, the next-to-shortest path problem is to find an $st$-path which length is minimum amongst all $st$-paths strictly longer than the shortest path length. In this paper we show that the problem can be solved in linear time if the distances from $s$ and $t$ to all other vertices are given. Particularly our new algorithm runs in $O(|V|\log |V|+|E|)$ time for general graphs, which improves the previous result of $O(|V|^2)$ time for sparse graphs, and takes only linear time for unweighted graphs, planar graphs, and graphs with positive integer edge lengths.
Streaming Multimedia Information Using the Features of the DVB-S Card
Venue: arXiv cs.MM 2011
Year: 2011

This paper presents a study of audio-video streaming using the additional possibilities of a DVB-S card. The board used for experiments (Technisat SkyStar 2) is one of the most frequently used cards for this purpose. Using the main blocks of the board's software support it is possible the implement a really useful and full functional system for audio-video streaming. The streaming is possible to be implemented either for decoded MPEG stream or for transport stream. In this last case it is possible to view not only a program, but any program from the same multiplex. This allows us to implement
Maximum Gain Round Trips with Cost Constraints
Venue: arXiv cs.SI 2011
Year: 2011

Searching for optimal ways in a network is an important task in multiple application areas such as social networks, co-citation graphs or road networks. In the majority of applications, each edge in a network is associated with a certain cost and an optimal way minimizes the cost while fulfilling a certain property, e.g connecting a start and a destination node. In this paper, we want to extend pure cost networks to so-called cost-gain networks. In this type of network, each edge is additionally associated with a certain gain. Thus, a way having a certain cost additionally provides a certain gain. In the following, we will discuss the problem of finding ways providing maximal gain while costing less than a certain budget. An application for this type of problem is the round trip problem of a traveler: Given a certain amount of time, which is the best round trip traversing the most scenic landscape or visiting the most important sights? In the following, we distinguish two cases of the problem. The first does not control any redundant edges and the second allows a more sophisticated handling of edges occurring more than once. To answer the maximum round trip queries on a given graph data set, we propose unidirectional and bidirectional search algorithms. Both types of algorithms are tested for the use case named above on real world spatial networks.
Rapid Feature Learning with Stacked Linear Denoisers
Venue: arXiv cs.LG 2011
Year: 2011

We investigate unsupervised pre-training of deep architectures as feature generators for "shallow" classifiers. Stacked Denoising Autoencoders (SdA), when used as feature pre-processing tools for SVM classification, can lead to significant improvements in accuracy - however, at the price of a substantial increase in computational cost. In this paper we create a simple algorithm which mimics the layer by layer training of SdAs. However, in contrast to SdAs, our algorithm requires no training through gradient descent as the parameters can be computed in closed-form. It can be implemented in less than 20 lines of MATLABTMand reduces the computation time from several hours to mere seconds. We show that our feature transformation reliably improves the results of SVM classification significantly on all our data sets - often outperforming SdAs and even deep neural networks in three out of four deep learning benchmarks.
Public Key Protocol Based on Amalgamated Free Product
Venue: arXiv cs.CR 2011
Year: 2011

In the spirit of Diffie Hellman the concept of a protocol algebra is introduced using certain amalgamated free product of Braid group B and Thompson group T together with a nilpotent subgroup H of index 2.
Sampling-based Algorithms for Optimal Motion Planning
Venue: arXiv cs.RO 2011
Year: 2011

During the last decade, sampling-based path planning algorithms, such as Probabilistic RoadMaps (PRM) and Rapidly-exploring Random Trees (RRT), have been shown to work well in practice and possess theoretical guarantees such as probabilistic completeness. However, little effort has been devoted to the formal analysis of the quality of the solution returned by such algorithms, e.g., as a function of the number of samples. The purpose of this paper is to fill this gap, by rigorously analyzing the asymptotic behavior of the cost of the solution returned by stochastic sampling-based algorithms as the number of samples increases. A number of negative results are provided, characterizing existing algorithms, e.g., showing that, under mild technical conditions, the cost of the solution returned by broadly used sampling-based algorithms converges almost surely to a non-optimal value. The main contribution of the paper is the introduction of new algorithms, namely, PRM* and RRT*, which are provably asymptotically optimal, i.e., such that the cost of the returned solution converges almost surely to the optimum. Moreover, it is shown that the computational complexity of the new algorithms is within a constant factor of that of their probabilistically complete (but not asymptotically optimal) counterparts. The analysis in this paper hinges on novel connections between stochastic sampling-based path planning algorithms and the theory of random geometric graphs.
Software Architecture for Fiji National University Campus Information Systems
Venue: arXiv cs.SE 2011
Year: 2011

Software Architecture defines the overview of the system which consists of various components and their relationships among the software. Architectural design is very important in the development of large scale software solution and plays a very active role in achieving business goals, quality and reusable solution. It is often difficult to choose the best software architecture for your system from the several candidate types available. In this paper we look at the several architectural types and compare them based on the key requirements of our system, and select the most appropriate architecture for the implementation of campus information systems at Fiji National University. Finally we provide details of proposed architecture and outline future plans for implementation of our system.
A Comparison of Trojan Virus Behavior in Linux and Windows Operating Systems
Venue: arXiv cs.CR 2011
Year: 2011

Trojan virus attacks pose one of the most serious threats to computer security. A Trojan horse is typically separated into two parts - a server and a client. It is the client that is cleverly disguised as significant software and positioned in peer-to-peer file sharing networks, or unauthorized download websites. The most common means of infection is through email attachments. The developer of the virus usually uses various spamming techniques in order to distribute the virus to unsuspecting users. Malware developers use chat software as another method to spread their Trojan horse viruses such as Yahoo Messenger and Skype. The objective of this paper is to explore the network packet information and detect the behavior of Trojan attacks to monitoring operating systems such as Windows and Linux. This is accomplished by detecting and analyzing the Trojan infected packet from a network segment -which passes through email attachment- before attacking a host computer. The results that have been obtained to detect information and to store infected packets through monitoring when using the web browser also compare the behaviors of Linux and Windows using the payload size after implementing the Wireshark sniffer packet results. Conclusions of the figures analysis from the packet captured data to analyze the control bit, and check the behavior of the control bits, and the usability of the operating systems Linux and Windows.
Optimal Computation of Symmetric Boolean Functions in Collocated Networks
Venue: arXiv cs.IT 2011
Year: 2011

We consider collocated wireless sensor networks, where each node has a Boolean measurement and the goal is to compute a given Boolean function of these measurements. We first consider the worst case setting and study optimal block computation strategies for computing symmetric Boolean functions. We study three classes of functions: threshold functions, delta functions and interval functions. We provide exactly optimal strategies for the first two classes, and a scaling law order-optimal strategy with optimal preconstant for interval functions. We also extend the results to the case of integer measurements and certain integer-valued functions. We use lower bounds from communication complexity theory, and provide an achievable scheme using information theoretic tools. Next, we consider the case where nodes measurements are random and drawn from independent Bernoulli distributions. We address the problem of optimal function computation so as to minimize the expected total number of bits that are transmitted. In the case of computing a single instance of a Boolean threshold function, we show the surprising result that the optimal order of transmissions depends in an extremely simple way on the values of previously transmitted bits, and the ordering of the marginal probabilities of the Boolean variables. The approach presented can be generalized to the case where each node has a block of measurements, though the resulting problem is somewhat harder, and we conjecture the optimal strategy. We further show how to generalize to a pulse model of communication. One can also consider the related problem of approximate computation given a fixed number of bits. In this case, the optimal strategy is significantly different, and lacks an elegant characterization. However, for the special case of the parity function, we show that the greedy strategy is optimal.
Machine-Part cell formation through visual decipherable clustering of Self Organizing Map
Venue: arXiv cs.AI 2011
Year: 2011

Machine-part cell formation is used in cellular manufacturing in order to process a large variety, quality, lower work in process levels, reducing manufacturing lead-time and customer response time while retaining flexibility for new products. This paper presents a new and novel approach for obtaining machine cells and part families. In the cellular manufacturing the fundamental problem is the formation of part families and machine cells. The present paper deals with the Self Organising Map (SOM) method an unsupervised learning algorithm in Artificial Intelligence, and has been used as a visually decipherable clustering tool of machine-part cell formation. The objective of the paper is to cluster the binary machine-part matrix through visually decipherable cluster of SOM color-coding and labelling via the SOM map nodes in such a way that the part families are processed in that machine cells. The Umatrix, component plane, principal component projection, scatter plot and histogram of SOM have been reported in the present work for the successful visualization of the machine-part cell formation. Computational result with the proposed algorithm on a set of group technology problems available in the literature is also presented. The proposed SOM approach produced solutions with a grouping efficacy that is at least as good as any results earlier reported in the literature and improved the grouping efficacy for 70% of the problems and found immensely useful to both industry practitioners and researchers.
Modeling queuing dynamics of TCP: a simple model and its empirical validation
Venue: arXiv cs.NI 2011
Year: 2011

Understanding queuing dynamics of TCP is important for correct router buffer sizing as well as for optimizing the performance of the TCP protocol itself. However, modeling of buffer content dynamics under TCP has received relatively little attention given its importance. Commonly used queuing models are based on overly simplistic assumptions about the packet arrival process. As a consequence, there are no quantitatively accurate closed loop TCP models capable of predicting performance even for a single link shared by multiple flows. Our present paper aims to close this gap by proposing a simple TCP queuing model, which is based on experimental observations and validated by extensive packet level simulations.
Topological Considerations for Tuning and Fingering Stringed Instruments
Venue: arXiv cs.SD 2011
Year: 2011

We present a formal language for assigning pitches to strings for fingered multi-string instruments, particularly the six-string guitar. Given the instrument's tuning (the strings' open pitches) and the compass of the fingers of the hand stopping the strings, the formalism yields a framework for simultaneously optimizing three things: the mapping of pitches to strings, the choice of instrument tuning, and the key of the composition. Final optimization relies on heuristics idiomatic to the tuning, the particular musical style, and the performer's proficiency.
Embeddings of Linear Arrays, Rings and 2-D Meshes on Extended Lucas Cube Networks
Venue: arXiv cs.NI 2011
Year: 2011

A Fibonacci string is a length n binary string containing no two consecutive 1s. Fibonacci cubes (FC), Extended Fibonacci cubes (ELC) and Lucas cubes (LC) are subgraphs of hypercube defined in terms of Fibonacci strings. All these cubes were introduced in the last ten years as models for interconnection networks and shown that their network topology posseses many interesting properties that are important in parallel processor network design and parallel applications. In this paper, we propose a new family of Fibonacci-like cube, namely Extended Lucas Cube (ELC). We address the following network simulation problem : Given a linear array, a ring or a two-dimensional mesh; how can its nodes be assigned to ELC nodes so as to keep their adjacent nodes near each other in ELC ?. We first show a simple fact that there is a Hamiltonian path and cycle in any ELC. We prove that any linear array and ring network can be embedded into its corresponding optimum ELC (the smallest ELC with at least the number of nodes in the ring) with dilation 1, which is optimum for most cases. Then, we describe dilation 1 embeddings of a class of meshes into their corresponding optimum ELC.
Solving Rubik's Cube Using SAT Solvers
Venue: arXiv cs.AI 2011
Year: 2011

Rubik's Cube is an easily-understood puzzle, which is originally called the "magic cube". It is a well-known planning problem, which has been studied for a long time. Yet many simple properties remain unknown. This paper studies whether modern SAT solvers are applicable to this puzzle. To our best knowledge, we are the first to translate Rubik's Cube to a SAT problem. To reduce the number of variables and clauses needed for the encoding, we replace a naive approach of 6 Boolean variables to represent each color on each facelet with a new approach of 3 or 2 Boolean variables. In order to be able to solve quickly Rubik's Cube, we replace the direct encoding of 18 turns with the layer encoding of 18-subtype turns based on 6-type turns. To speed up the solving further, we encode some properties of two-phase algorithm as an additional constraint, and restrict some move sequences by adding some constraint clauses. Using only efficient encoding cannot solve this puzzle. For this reason, we improve the existing SAT solvers, and develop a new SAT solver based on PrecoSAT, though it is suited only for Rubik's Cube. The new SAT solver replaces the lookahead solving strategy with an ALO (\emph{at-least-one}) solving strategy, and decomposes the original problem into sub-problems. Each sub-problem is solved by PrecoSAT. The empirical results demonstrate both our SAT translation and new solving technique are efficient. Without the efficient SAT encoding and the new solving technique, Rubik's Cube will not be able to be solved still by any SAT solver. Using the improved SAT solver, we can find always a solution of length 20 in a reasonable time. Although our solver is slower than Kociemba's algorithm using lookup tables, but does not require a huge lookup table.
Efficient Soft-Input Soft-Output Tree Detection Via an Improved Path Metric
Venue: arXiv cs.IT 2011
Year: 2011

Tree detection techniques are often used to reduce the complexity of a posteriori probability (APP) detection in high dimensional multi-antenna wireless communication systems. In this paper, we introduce an efficient soft-input soft-output tree detection algorithm that employs a new type of look-ahead path metric in the computation of its branch pruning (or sorting). While conventional path metrics depend only on symbols on a visited path, the new path metric accounts for unvisited parts of the tree in advance through an unconstrained linear estimator and adds a bias term that reflects the contribution of as-yet undecided symbols. By applying the linear estimate-based look-ahead path metric to an M-algorithm that selects the best M paths for each level of the tree we develop a new soft-input soft-output tree detector, called an improved soft-input soft-output M-algorithm (ISS-MA). Based on an analysis of the probability of correct path loss, we show that the improved path metric offers substantial performance gain over the conventional path metric. We also demonstrate through simulations that the ISS-MA provides a better performance-complexity trade-off than existing soft-input soft-output detection algorithms.
Code Reverse Engineering problem for Identification Codes
Venue: arXiv cs.CR 2011
Year: 2011

At ITW'10, Bringer et al. suggest to strengthen their previous identification protocol by extending the Code Reverse Engineering (CRE) problem to identification codes. We first extend security results by Tillich et al. on this very problem. We then prove the security of this protocol using information theoretical arguments.