OpenRaiser/Intern-Atlas huggingface dataset:
Magnetohydrodynamics on Heterogeneous architectures: a performance comparison
Venue: arXiv cs.PF 2010
Year: 2010

We present magneto-hydrodynamic simulation results for heterogeneous systems. Heterogeneous architectures combine high floating point performance many-core units hosted in conventional server nodes. Examples include Graphics Processing Units (GPU's) and Cell. They have potentially large gains in performance, at modest power and monetary cost. We implemented a magneto-hydrodynamic (MHD) simulation code on a variety of heterogeneous and multi-core architectures --- multi-core x86, Cell, Nvidia and ATI GPU --- in different languages, FORTRAN, C, Cell, CUDA and OpenCL. We present initial performance results for these systems. To our knowledge, this is the widest comparison of heterogeneous systems for MHD simulations. We review the different challenges faced in each architecture, and potential bottlenecks. We conclude that substantial gains in performance over traditional systems are possible, and in particular that is possible to extract a greater percentage of peak theoretical performance from some systems when compared to x86 architectures.
New Clustering Algorithm for Vector Quantization using Rotation of Error Vector
Venue: arXiv cs.CV 2010
Year: 2010

The paper presents new clustering algorithm. The proposed algorithm gives less distortion as compared to well known Linde Buzo Gray (LBG) algorithm and Kekre's Proportionate Error (KPE) Algorithm. Constant error is added every time to split the clusters in LBG, resulting in formation of cluster in one direction which is 1350 in 2-dimensional case. Because of this reason clustering is inefficient resulting in high MSE in LBG. To overcome this drawback of LBG proportionate error is added to change the cluster orientation in KPE. Though the cluster orientation in KPE is changed its variation is limited to +/- 450 over 1350. The proposed algorithm takes care of this problem by introducing new orientation every time to split the clusters. The proposed method reduces PSNR by 2db to 5db for codebook size 128 to 1024 with respect to LBG.
An undecidable property of context-free languages
Venue: arXiv cs.FL 2010
Year: 2010

We prove that there exists no algorithm to decide whether the language generated by a context-free grammar is dense with respect to the lexicographic ordering. As a corollary to this result, we show that it is undecidable whether the lexicographic orderings of the languages generated by two context-free grammars have the same order type.
An Analytical Study on Behavior of Clusters Using K Means, EM and K* Means Algorithm
Venue: arXiv cs.LG 2010
Year: 2010

Clustering is an unsupervised learning method that constitutes a cornerstone of an intelligent data analysis process. It is used for the exploration of inter-relationships among a collection of patterns, by organizing them into homogeneous clusters. Clustering has been dynamically applied to a variety of tasks in the field of Information Retrieval (IR). Clustering has become one of the most active area of research and the development. Clustering attempts to discover the set of consequential groups where those within each group are more closely related to one another than the others assigned to different groups. The resultant clusters can provide a structure for organizing large bodies of text for efficient browsing and searching. There exists a wide variety of clustering algorithms that has been intensively studied in the clustering problem. Among the algorithms that remain the most common and effectual, the iterative optimization clustering algorithms have been demonstrated reasonable performance for clustering, e.g. the Expectation Maximization (EM) algorithm and its variants, and the well known k-means algorithm. This paper presents an analysis on how partition method clustering techniques - EM, K -means and K* Means algorithm work on heartspect dataset with below mentioned features - Purity, Entropy, CPU time, Cluster wise analysis, Mean value analysis and inter cluster distance. Thus the paper finally provides the experimental results of datasets for five clusters to strengthen the results that the quality of the behavior in clusters in EM algorithm is far better than k-means algorithm and k*means algorithm.
Node inspection and analysis thereof in the light of area estimation and curve fitting
Venue: arXiv cs.NI 2010
Year: 2010

In this paper, we have given an idea of area specification and its corresponding sensing of nodes in a dynamic network. We have applied the concept of Monte Carlo methods in this respect. We have cited certain statistical as well as artificial intelligence based techniques for realizing the position of a node. We have also applied curve fitting concept for node detection and relative verification.
Joint Design of Congestion Control Routing With Distributed Multi Channel Assignment in Wireless Mesh Networks
Venue: arXiv cs.NI 2010
Year: 2010

In Wireless Mesh Networks (WMN), a channel assignment has to balance the objectives of maintaining connectivity and increasing the aggregate bandwidth. The main aim of the channel assignment algorithm is to assign the channels to the network interfaces, from the given expected load on each virtual link. From the existing work done so far, we can examine that there is no combined solution of multi-channel assignment with routing and congestion control. In this paper, we propose a congestion control routing protocol along with multi-channel assignment. We use a traffic aware metric in this protocol in order to provide quality of service. The proposed protocol can improve the throughput and channel utilization to very high extent because it provides solution for multi-channel assignment and congestion control. The proposed algorithm assigns the channels in a way that, congestion is avoided and co-channel interference levels among links with same channel are reduced. By our simulation results in NS2, we show that the proposed protocol attains high throughput and channel utilization along with reduced latency.
Mobile Broadband Possibilities considering the Arrival of IEEE 802.16m & LTE with an Emphasis on South Asia
Venue: arXiv cs.NI 2010
Year: 2010

This paper intends to look deeper into finding an ideal mobile broadband solution. Special stress has been put in the South Asian region through some comparative analysis. Proving their competency in numerous aspects, WiMAX and LTE already have already made a strong position in telecommunication industry. Both WiMAX and LTE are 4G technologies designed to move data rather than voice having IP networks based on OFDM technology. So, they aren't like typical technological rivals as of GSM and CDMA. But still a gesture of hostility seems to outburst long before the stable commercial launch of LTE. In this paper various aspects of WiMAX and LTE for deployment have been analyzed. Again, we tried to make every possible consideration with respect to south Asia i.e. how mass people of this region may be benefited. As a result, it might be regarded as a good source in case of making major BWA deployment decisions in this region. Besides these, it also opens the path for further research and in depth thinking in this issue.
GIS: Geographic Information System An application for socio-economical data collection for rural area
Venue: arXiv cs.CY 2010
Year: 2010

The country India follows the planning through planning commission. This is on the basis of information collected by traditional, tedious and manual method which is too slow to sustain. Now we are in the age of 21th century. We have seen in last few decades that the progress of information technology with leaps and bounds, which have completely changed the way of life in the developed nations. While internet has changed the established working practice and opened new vistas and provided a platform to connect, this gives the opportunity for collaborative work space that goes beyond the global boundary. We are living in the global economy and India leading towards Liberalize Market Oriented Economy (LMOE). Considering this things, focusing on GIS, we proposed a system for collection of socio economic data and water resource management information of rural area via internet.
Predictive Gain Estimation - A mathematical analysis
Venue: arXiv cs.OH 2010
Year: 2010

In case of realization of successful business, gain analysis is essential. In this paper we have cited some new techniques of gain expectation on the basis of neural property of perceptron. Support rule and Sequence mining based artificial intelligence oriented practices have also been done in this context. In the view of above fuzzy and statistical based gain sensing is also pointed out.
The Socceral Force
Venue: arXiv cs.AI 2010
Year: 2010

We have an audacious dream, we would like to develop a simulation and virtual reality system to support the decision making in European football (soccer). In this review, we summarize the efforts that we have made to fulfil this dream until recently. In addition, an introductory version of FerSML (Footballer and Football Simulation Markup Language) is presented in this paper.
An O(M(n) log n) algorithm for the Jacobi symbol
Venue: arXiv cs.DS 2010
Year: 2010

The best known algorithm to compute the Jacobi symbol of two n-bit integers runs in time O(M(n) log n), using Schönhage's fast continued fraction algorithm combined with an identity due to Gauss. We give a different O(M(n) log n) algorithm based on the binary recursive gcd algorithm of Stehlé and Zimmermann. Our implementation - which to our knowledge is the first to run in time O(M(n) log n) - is faster than GMP's quadratic implementation for inputs larger than about 10000 decimal digits.
Sum Capacity of K User Gaussian Degraded Interference Channels
Venue: arXiv cs.IT 2010
Year: 2010

This paper studies a family of genie-MAC (multiple access channel) outer bounds for K-user Gaussian interference channels. This family is inspired by existing genie-aided bounding mechanisms, but differs from current approaches in its optimization problem formulation and application. The fundamental idea behind these bounds is to create a group of genie receivers that form multiple access channels that can decode a subset of the original interference channel's messages. The MAC sum capacity of each of the genie receivers provides an outer bound on the sum of rates for this subset. The genie-MAC outer bounds are used to derive new sum-capacity results. In particular, this paper derives sum-capacity in closed-form for the class of K-user Gaussian degraded interference channels. The sum-capacity achieving scheme is shown to be a successive interference cancellation scheme. This result generalizes a known result for two-user channels to K-user channels.
Algebraic Proofs over Noncommutative Formulas
Venue: arXiv cs.CC 2010
Year: 2010

We study possible formulations of algebraic propositional proof systems operating with noncommutative formulas. We observe that a simple formulation gives rise to systems at least as strong as Frege---yielding a semantic way to define a Cook-Reckhow (i.e., polynomially verifiable) algebraic analog of Frege proofs, different from that given in [BIKPRS96,GH03]. We then turn to an apparently weaker system, namely, polynomial calculus (PC) where polynomials are written as ordered formulas (PC over ordered formulas, for short): an ordered polynomial is a noncommutative polynomial in which the order of products in every monomial respects a fixed linear order on variables; an algebraic formula is ordered if the polynomial computed by each of its subformulas is ordered. We show that PC over ordered formulas is strictly stronger than resolution, polynomial calculus and polynomial calculus with resolution (PCR) and admits polynomial-size refutations for the pigeonhole principle and the Tseitin's formulas. We conclude by proposing an approach for establishing lower bounds on PC over ordered formulas proofs, and related systems, based on properties of lower bounds on noncommutative formulas. The motivation behind this work is developing techniques incorporating rank arguments (similar to those used in algebraic circuit complexity) for establishing lower bounds on propositional proofs.
GénéSyst : Génération d'un système de transitions étiquetées à partir d'une spécification B événementiel
Venue: arXiv cs.SE 2010
Year: 2010

The most expensive source of errors and the more difficult to detect in a formal development is the error during specification. Hence, the first step in a formal development usually consists in exhibiting the set of all behaviors of the specification, for instance with an automaton. Starting from this observation, many researches are about the generation of a B machine from a behavioral specification, such as UML. However, no backward verification are done. This is why, we propose the GeneSyst tool, which aims at generating an automaton describing at least all behaviors of the specification. The refinement step is considered and appears as sub-automatons in the produced SLTS.
One Tree Suffices: A Simultaneous O(1)-Approximation for Single-Sink Buy-at-Bulk
Venue: arXiv cs.DS 2010
Year: 2010

We study the single-sink buy-at-bulk problem with an unknown cost function. We wish to route flow from a set of demand nodes to a root node, where the cost of routing x total flow along an edge is proportional to f(x) for some concave, non-decreasing function f satisfying f(0)=0. We present a simple, fast, combinatorial algorithm that takes a set of demands and constructs a single tree T such that for all f the cost f(T) is a 47.45-approximation of the optimal cost for that f. This is within a factor of 2.33 of the best approximation ratio currently achievable when the tree can be optimized for a specific function. Trees achieving simultaneous O(1)-approximations for all concave functions were previously not known to exist regardless of computation time.
The Binary-Symmetric Parallel-Relay Network
Venue: arXiv cs.IT 2010
Year: 2010

We present capacity results of the binary-symmetric parallel-relay network, where there is one source, one destination, and K relays in parallel. We show that forwarding relays, where the relays merely transmit their received signals, achieve the capacity in two ways: with coded transmission at the source and a finite number of relays, or uncoded transmission at the source and a sufficiently large number of relays. On the other hand, decoding relays, where the relays decode the source message, re-encode, and forward it to the destination, achieve the capacity when the number of relays is small.
Towards Shift Tolerant Visual Secret Sharing Schemes
Venue: arXiv cs.CR 2010
Year: 2010

In (k, n) visual secret sharing (VSS) scheme, secret image can be visually reconstructed when k or more participants printing theirs shares on transparencies and stack them together. No secret is revealed with fewer than k shares. The alignment of the transparencies is important to the visual quality of the reconstructed secret image. In VSS scheme, each pixel of the original secret image is expanded to m sub-pixels in a share image. If a share image is printed on paper with the same size as the original secret image, the alignment or the registration of the sub-pixels, which is only m times smaller than that in the original secret, could be troublesome. Liu et al. [4] has noticed this alignment problem and observed that some information of the secret image may still be revealed even when the shares are not precisely registered in the horizontal direction. Yang et al. [9] introduced a general approach to construct a misalignment tolerant (k, n)-VSS scheme using big and small blocks for the situation where the original secret image has a certain degree of redundancy in shape accuracy. In this paper, we propose a (2, n)-VSS scheme that allows a relative shift between the shares in the horizontal direction and vertical direction. When the shares are perfectly aligned, the contrast of the reconstructed image is equal to that of traditional VSS shceme. When there is a shift, average contrast in the reconstructed image is higher than that of the traditional VSS scheme, and the scheme can still work in the cases where very little shape redundancy presents in the image. The trade-off is that our method involves a larger pixel expansion. The basic building block of our scheme is duplication and concatenation of certain rows or columns of the basic matrices. This seemingly simple but very powerful construction principle can be easily used to create more general (k, n)-VSS schemes.
GIST: A Solver for Probabilistic Games
Venue: arXiv cs.LO 2010
Year: 2010

Gist is a tool that (a) solves the qualitative analysis problem of turn-based probabilistic games with ω-regular objectives; and (b) synthesizes reasonable environment assumptions for synthesis of unrealizable specifications. Our tool provides the first and efficient implementations of several reduction-based techniques to solve turn-based probabilistic games, and uses the analysis of turn-based probabilistic games for synthesizing environment assumptions for unrealizable specifications.
On the Continuous CNN Problem
Venue: arXiv cs.DS 2010
Year: 2010

In the (discrete) CNN problem, online requests appear as points in $\mathbb{R}^2$. Each request must be served before the next one is revealed. We have a server that can serve a request simply by aligning either its $x$ or $y$ coordinate with the request. The goal of the online algorithm is to minimize the total $L_1$ distance traveled by the server to serve all the requests. The best known competitive ratio for the discrete version is 879 (due to Sitters and Stougie). We study the continuous version, in which, the request can move continuously in $\mathbb{R}^2$ and the server must continuously serve the request. A simple adversarial argument shows that the lower bound on the competitive ratio of any online algorithm for the continuous CNN problem is 3. Our main contribution is an online algorithm with competitive ratio $3+2 \sqrt{3} \approx 6.464$. Our analysis is tight. The continuous version generalizes the discrete orthogonal CNN problem, in which every request must be $x$ or $y$ aligned with the previous request. Therefore, Our result improves upon the previous best competitive ratio of 9 (due to Iwama and Yonezawa).
Bounds on Thresholds Related to Maximum Satisfiability of Regular Random Formulas
Venue: arXiv cs.IT 2010
Year: 2010

We consider the regular balanced model of formula generation in conjunctive normal form (CNF) introduced by Boufkhad, Dubois, Interian, and Selman. We say that a formula is $p$-satisfying if there is a truth assignment satisfying $1-2^{-k}+p 2^{-k}$ fraction of clauses. Using the first moment method we determine upper bound on the threshold clause density such that there are no $p$-satisfying assignments with high probability above this upper bound. There are two aspects in deriving the lower bound using the second moment method. The first aspect is, given any $p \in (0,1)$ and $k$, evaluate the lower bound on the threshold. This evaluation is numerical in nature. The second aspect is to derive the lower bound as a function of $p$ for large enough $k$. We address the first aspect and evaluate the lower bound on the $p$-satisfying threshold using the second moment method. We observe that as $k$ increases the lower bound seems to converge to the asymptotically derived lower bound for uniform model of formula generation by Achlioptas, Naor, and Peres.
Competitive Equilibria in Matching Markets with Budgets
Venue: arXiv cs.GT 2010
Year: 2010

We study competitive equilibria in the classic Shapley-Shubik assignment model with indivisible goods and unit-demand buyers, with budget constraints: buyers can specify a maximum price they are willing to pay for each item, beyond which they cannot afford the item. This single discontinuity introduced by the budget constraint fundamentally changes the properties of equilibria: in the assignment model without budget constraints, a competitive equilibrium always exists, and corresponds exactly to a stable matching. With budgets, a competitive equilibrium need not always exist. In addition, there are now two distinct notions of stability, depending on whether both or only one of the buyer and seller can strictly benefit in a blocking pair, that no longer coincide due to the budget-induced discontinuity. We define weak and strong stability for the assignment model with transferable utilities, and show that competitive equilibria correspond exactly to strongly stable matchings. We consider the algorithmic question of efficiently computing competitive equilibria in an extension of the assignment model with budgets, where each buyer specifies his preferences over items using utility functions $u_{ij}$, where $u_{ij}(p_j)$ is the utility of buyer $i$ for item $j$ when its price is $p_j$. Our main result is a strongly polynomial time algorithm that decides whether or not a competitive equilibrium exists and if yes, computes a minimum one, for a general class of utility functions $u_{ij}$. This class of utility functions includes the standard quasi-linear utility model with a budget constraint, and in addition, allows modeling marketplaces where, for example, buyers only have a preference ranking amongst items subject to a maximum payment limit for each item, or where buyers want to optimize return on investment (ROI) instead of a quasi-linear utility and only know items' relative values.
Is This a Good Title?
Venue: arXiv cs.IR 2010
Year: 2010

Missing web pages, URIs that return the 404 "Page Not Found" error or the HTTP response code 200 but dereference unexpected content, are ubiquitous in today's browsing experience. We use Internet search engines to relocate such missing pages and provide means that help automate the rediscovery process. We propose querying web pages' titles against search engines. We investigate the retrieval performance of titles and compare them to lexical signatures which are derived from the pages' content. Since titles naturally represent the content of a document they intuitively change over time. We measure the edit distance between current titles and titles of copies of the same pages obtained from the Internet Archive and display their evolution. We further investigate the correlation between title changes and content modifications of a web page over time. Lastly we provide a predictive model for the quality of any given web page title in terms of its discovery performance. Our results show that titles return more than 60% URIs top ranked and further relevant content returned in the top 10 results. We show that titles decay slowly but are far more stable than the pages' content. We further distill stop titles than can help identify insufficiently performing search engine queries.
Behavioural Correlation for Detecting P2P Bots
Venue: arXiv cs.AI 2010
Year: 2010

In the past few years, IRC bots, malicious programs which are remotely controlled by the attacker through IRC servers, have become a major threat to the Internet and users. These bots can be used in different malicious ways such as issuing distributed denial of services attacks to shutdown other networks and services, keystrokes logging, spamming, traffic sniffing cause serious disruption on networks and users. New bots use peer to peer (P2P) protocols start to appear as the upcoming threat to Internet security due to the fact that P2P bots do not have a centralized point to shutdown or traceback, thus making the detection of P2P bots is a real challenge. In response to these threats, we present an algorithm to detect an individual P2P bot running on a system by correlating its activities. Our evaluation shows that correlating different activities generated by P2P bots within a specified time period can detect these kind of bots.