OpenRaiser/Intern-Atlas huggingface dataset:
Compressed Matrix Multiplication
Venue: arXiv cs.DS 2011
Year: 2011

Motivated by the problems of computing sample covariance matrices, and of transforming a collection of vectors to a basis where they are sparse, we present a simple algorithm that computes an approximation of the product of two n-by-n real matrices A and B. Let ||AB||_F denote the Frobenius norm of AB, and b be a parameter determining the time/accuracy trade-off. Given 2-wise independent hash functions $_1,h_2: [n] -> [b], and s_1,s_2: [n] -> {-1,+1} the algorithm works by first "compressing" the matrix product into the polynomial p(x) = sum_{k=1}^n (sum_{i=1}^n A_{ik} s_1(i) x^{h_1(i)}) (sum_{j=1}^n B_{kj} s_2(j) x^{h_2(j)}) Using FFT for polynomial multiplication, we can compute c_0,...,c_{b-1} such that sum_i c_i x^i = (p(x) mod x^b) + (p(x) div x^b) in time Õ(n^2+ n b). An unbiased estimator of (AB)_{ij} with variance at most ||AB||_F^2 / b can then be computed as: C_{ij} = s_1(i) s_2(j) c_{(h_1(i)+h_2(j)) mod b. Our approach also leads to an algorithm for computing AB exactly, whp., in time Õ(N + nb) in the case where A and B have at most N nonzero entries, and AB has at most b nonzero entries. Also, we use error-correcting codes in a novel way to recover significant entries of AB in near-linear time.
Variability of location management costs with different mobilities and timer periods to update locations
Venue: arXiv cs.SI 2011
Year: 2011

In this article, we examine the Location Management costs in mobile communication networks utilizing the timer-based method. From the study of the probabilities that a mobile terminal changes a number of Location Areas between two calls, we identify a threshold value of 0.7 for the Call-to-Mobility Ratio (CMR) below which the application of the timer-based method is most appropriate. We characterize the valley appearing in the evolution of the costs with the timeout period, showing that the time interval required to reach 90% of the stabilized costs grows with the mobility index, the paging cost per Location Area and the movement dimension, in opposition to the behavior presented by the time interval that achieves the minimum of the costs. The results obtained for CMRs below the suggested 0.7 threshold show that the valley appearing in the costs tends to disappear for CMRs within [0.001, 0.7] in onedimensional movements and within [0.2, 0.7] in two-dimensional ones, and when the normalized paging cost per Location Area is below 0.3.
Non-cooperative Game For Capacity Offload
Venue: arXiv cs.NI 2011
Year: 2011

With the blasting increase of wireless data traffic, incumbent wireless service providers (WSPs) face critical challenges in provisioning spectrum resource. Given the permission of unlicensed access to TV white spaces, WSPs can alleviate their burden by exploiting the concept of "capacity offload" to transfer part of their traffic load to unlicensed spectrum. For such use cases, a central problem is for WSPs to coexist with others, since all of them may access the unlicensed spectrum without coordination thus interfering each other. Game theory provides tools for predicting the behavior of WSPs, and we formulate the coexistence problem under the framework of non-cooperative games as a capacity offload game (COG). We show that a COG always possesses at least one pure-strategy Nash equilibrium (NE), and does not have any mixed-strategy NE. The analysis provides a full characterization of the structure of the NEs in two-player COGs. When the game is played repeatedly and each WSP individually updates its strategy based on its best-response function, the resulting process forms a best-response dynamic. We establish that, for two-player COGs, alternating-move best-response dynamics always converge to an NE, while simultaneous-move best-response dynamics does not always converge to an NE when multiple NEs exist. When there are more than two players in a COG, if the network configuration satisfies certain conditions so that the resulting best-response dynamics become linear, both simultaneous-move and alternating-move best-response dynamics are guaranteed to converge to the unique NE.
Applying Algebraic Specifications on Digital Right Management Systems
Venue: arXiv cs.LO 2011
Year: 2011

Digital Right Management (DRM) Systems have been created to meet the need for digital content protection and distribution. In this paper we present some of the directions of our ongoing research to apply algebraic specification techniques on mobile DRM systems.
A New Algorithmic Scheme for Computing Characteristic Sets
Venue: arXiv cs.SC 2011
Year: 2011

Ritt-Wu's algorithm of characteristic sets is the most representative for triangularizing sets of multivariate polynomials. Pseudo-division is the main operation used in this algorithm. In this paper we present a new algorithmic scheme for computing generalized characteristic sets by introducing other admissible reductions than pseudo-division. A concrete subalgorithm is designed to triangularize polynomial sets using selected admissible reductions and several effective elimination strategies and to replace the algorithm of basic sets (used in Ritt-Wu's algorithm). The proposed algorithm has been implemented and experimental results show that it performs better than Ritt-Wu's algorithm in terms of computing time and simplicity of output for a number of non-trivial test examples.
Imitation of Life: Advanced system for native Artificial Evolution
Venue: arXiv cs.NE 2011
Year: 2011

A model for artificial evolution in native x86 Windows systems has been developed at the end of 2010. In this text, further improvements and additional analogies to natural microbiologic processes are presented. Several experiments indicate the capability of the system - and raise the question of possible countermeasures.
A joint time-invariant filtering approach to the linear Gaussian relay problem
Venue: arXiv cs.IT 2011
Year: 2011

In this paper, the linear Gaussian relay problem is considered. Under the linear time-invariant (LTI) model the problem is formulated in the frequency domain based on the Toeplitz distribution theorem. Under the further assumption of realizable input spectra, the LTI Gaussian relay problem is converted to a joint design problem of source and relay filters under two power constraints, one at the source and the other at the relay, and a practical solution to this problem is proposed based on the projected subgradient method. Numerical results show that the proposed method yields a noticeable gain over the instantaneous amplify-and-forward (AF) scheme in inter-symbol interference (ISI) channels. Also, the optimality of the AF scheme within the class of one-tap relay filters is established in flat-fading channels.
HybridNN: Supporting Network Location Service on Generalized Delay Metrics
Venue: arXiv cs.DC 2011
Year: 2011

Distributed Nearest Neighbor Search (DNNS) locates service nodes that have shortest interactive delay towards requesting hosts. DNNS provides an important service for large-scale latency sensitive networked applications, such as VoIP, online network games, or interactive network services on the cloud. Existing work assumes the delay to be symmetric, which does not generalize to applications that are sensitive to one-way delays, such as the multimedia video delivery from the servers to the hosts. We propose a relaxed inframetric model for the network delay space that does not assume the triangle inequality and delay symmetry to hold. We prove that the DNNS requests can be completed efficiently if the delay space exhibits modest inframetric dimensions, which we can observe empirically. Finally, we propose a DNNS method named HybridNN (\textit{Hybrid} \textit{N}earest \textit{N}eighbor search) based on the inframetric model for fast and accurate DNNS. For DNNS requests, HybridNN chooses closest neighbors accurately via the inframetric modelling, and scalably by combining delay predictions with direct probes to a pruned set of neighbors. Simulation results show that HybridNN locates nearly optimally the nearest neighbor. Experiments on PlanetLab show that HybridNN can provide accurate nearest neighbors that are close to optimal with modest query overhead and maintenance traffic.
A Knowledge Mining Model for Ranking Institutions using Rough Computing with Ordering Rules and Formal Concept analysis
Venue: arXiv cs.AI 2011
Year: 2011

Emergences of computers and information technological revolution made tremendous changes in the real world and provides a different dimension for the intelligent data analysis. Well formed fact, the information at right time and at right place deploy a better knowledge.However, the challenge arises when larger volume of inconsistent data is given for decision making and knowledge extraction. To handle such imprecise data certain mathematical tools of greater importance has developed by researches in recent past namely fuzzy set, intuitionistic fuzzy set, rough Set, formal concept analysis and ordering rules. It is also observed that many information system contains numerical attribute values and therefore they are almost similar instead of exact similar. To handle such type of information system, in this paper we use two processes such as pre process and post process. In pre process we use rough set on intuitionistic fuzzy approximation space with ordering rules for finding the knowledge whereas in post process we use formal concept analysis to explore better knowledge and vital factors affecting decisions.
Uncertain Nearest Neighbor Classification
Venue: arXiv cs.LG 2011
Year: 2011

This work deals with the problem of classifying uncertain data. With this aim the Uncertain Nearest Neighbor (UNN) rule is here introduced, which represents the generalization of the deterministic nearest neighbor rule to the case in which uncertain objects are available. The UNN rule relies on the concept of nearest neighbor class, rather than on that of nearest neighbor object. The nearest neighbor class of a test object is the class that maximizes the probability of providing its nearest neighbor. It is provided evidence that the former concept is much more powerful than the latter one in the presence of uncertainty, in that it correctly models the right semantics of the nearest neighbor decision rule when applied to the uncertain scenario. An effective and efficient algorithm to perform uncertain nearest neighbor classification of a generic (un)certain test object is designed, based on properties that greatly reduce the temporal cost associated with nearest neighbor class probability computation. Experimental results are presented, showing that the UNN rule is effective and efficient in classifying uncertain data.
Context Protecting Privacy Preservation in Ubiquitous Computing
Venue: arXiv cs.CR 2011
Year: 2011

In ubiquitous computing domain context awareness is an important issue. So, in ubiquitous computing, mere protection of message confidentiality is not sufficient for most of the applications where context-awareness can lead to near deterministic ideas. An adversary might deduce sensitive information by observing the contextual data, which when correlated with prior information about the people and the physical locations that are being monitored by a set of sensors can reveal most of the sensitive information. So, it is obvious that for security and privacy preservation in ubiquitous computing context protection is of equal importance. In this paper, we propose a scheme which provides two layer privacy protection of user's or application's context data. Our proposed context protecting privacy preservation scheme focuses on protecting spatial and temporal contextual information. We consider the communication part of ubiquitous computing consists of tiny sensor nodes forming Wireless Sensor Networks (WSNs). Through simulation we show the efficacy of our scheme. We also demonstrate the capability of our scheme to overcome the constraints of WSNs.
Governing Information Security in Conjunction with COBIT and ISO 27001
Venue: arXiv cs.CR 2011
Year: 2011

In this paper, after giving a brief definition of Information Security Management Systems (ISMS), ISO 27001, IT governance and COBIT, pros and cons of implementing only COBIT, implementing only IS0 27001 and implementing both COBIT and ISO 27001 together when governing information security in enterprises will be issued.
Partner selection in indoor-to-outdoor cooperative networks: an experimental study
Venue: arXiv cs.NI 2011
Year: 2011

In this paper, we develop a partner selection protocol for enhancing the network lifetime in cooperative wireless networks. The case-study is the cooperative relayed transmission from fixed indoor nodes to a common outdoor access point. A stochastic bivariate model for the spatial distribution of the fading parameters that govern the link performance, namely the Rician K-factor and the path-loss, is proposed and validated by means of real channel measurements. The partner selection protocol is based on the real-time estimation of a function of these fading parameters, i.e., the coding gain. To reduce the complexity of the link quality assessment, a Bayesian approach is proposed that uses the site-specific bivariate model as a-priori information for the coding gain estimation. This link quality estimator allows network lifetime gains almost as if all K-factor values were known. Furthermore, it suits IEEE 802.15.4 compliant networks as it efficiently exploits the information acquired from the receiver signal strength indicator. Extensive numerical results highlight the trade-off between complexity, robustness to model mismatches and network lifetime performance. We show for instance that infrequent updates of the site-specific model through K-factor estimation over a subset of links are sufficient to at least double the network lifetime with respect to existing algorithms based on path loss information only.
Product Lines for Service Oriented Applications - PL for SOA
Venue: arXiv cs.SE 2011
Year: 2011

PL for SOA proposes, formally, a software engineering methodology, development techniques and support tools for the provision of service product lines. We propose rigorous modeling techniques for the specification and verification of formal notations and languages for service computing with inclinations of variability. Through these cutting-edge technologies, increased levels of flexibility and adaptivity can be achieved. This will involve developing semantics of variability over behavioural models of services. Such tools will assist organizations to plan, optimize and control the quality of software service provision, both at design and at run time by making it possible to develop flexible and cost-effective software systems that support high levels of reuse. We tackle this challenge from two levels. We use feature modeling from product line engineering and, from a services point of view, the orchestration language Orc. We introduce the Smart Grid as the service product line to apply the techniques to.
Width-parameterized SAT: Time-Space Tradeoffs
Venue: arXiv cs.CC 2011
Year: 2011

Width parameterizations of SAT, such as tree-width and path-width, enable the study of computationally more tractable and practical SAT instances. We give two simple algorithms. One that runs simultaneously in time-space $(O^*(2^{2tw(ϕ)}), O^*(2^{tw(ϕ)}))$ and another that runs in time-space $(O^*(3^{tw(ϕ)\log{|ϕ|}}),|ϕ|^{O(1)})$, where $tw(ϕ)$ is the tree-width of a formula $ϕ$ with $|ϕ|$ many clauses and variables. This partially answers the question of Alekhnovitch and Razborov, who also gave algorithms exponential both in time and space, and asked whether the space can be made smaller. We conjecture that every algorithm for this problem that runs in time $2^{tw(ϕ)\mathbf{o(\log{|ϕ|})}}$ necessarily blows up the space to exponential in $tw(ϕ)$. We introduce a novel way to combine the two simple algorithms that allows us to trade \emph{constant} factors in the exponents between running time and space. Our technique gives rise to a family of algorithms controlled by two parameters. By fixing one parameter we obtain an algorithm that runs in time-space $(O^*(3^{1.441(1-ε)tw(ϕ)\log{|ϕ|}}), O^*(2^{2εtw(ϕ)}))$, for every $0<ε<1$. We systematically study the limitations of this technique, and show that these algorithmic results are the best achievable using this technique. We also study further the computational complexity of width parameterizations of SAT. We prove non-sparsification lower bounds for formulas of path-width $ω(\log|ϕ|)$, and a separation between the complexity of path-width and tree-width parametrized SAT modulo plausible complexity assumptions.
A New System Architecture for Pervasive Computing
Venue: arXiv cs.OH 2011
Year: 2011

We present new system architecture, a distributed framework designed to support pervasive computing applications. We propose a new architecture consisting of a search engine and peripheral clients that addresses issues in scalability, data sharing, data transformation and inherent platform heterogeneity. Key features of our application are a type-aware data transport that is capable of extract data, and present data through handheld devices (PDA (personal digital assistant), mobiles, etc). Pervasive computing uses web technology, portable devices, wireless communications and nomadic or ubiquitous computing systems. The web and the simple standard HTTP protocol that it is based on, facilitate this kind of ubiquitous access. This can be implemented on a variety of devices - PDAs, laptops, information appliances such as digital cameras and printers. Mobile users get transparent access to resources outside their current environment. We discuss our system's architecture and its implementation. Through experimental study, we show reasonable performance and adaptation for our system's implementation for the mobile devices.
Sequential Auctions and Externalities
Venue: arXiv cs.GT 2011
Year: 2011

In many settings agents participate in multiple different auctions that are not necessarily implemented simultaneously. Future opportunities affect strategic considerations of the players in each auction, introducing externalities. Motivated by this consideration, we study a setting of a market of buyers and sellers, where each seller holds one item, bidders have combinatorial valuations and sellers hold item auctions sequentially. Our results are qualitatively different from those of simultaneous auctions, proving that simultaneity is a crucial aspect of previous work. We prove that if sellers hold sequential first price auctions then for unit-demand bidders (matching market) every subgame perfect equilibrium achieves at least half of the optimal social welfare, while for submodular bidders or when second price auctions are used, the social welfare can be arbitrarily worse than the optimal. We also show that a first price sequential auction for buying or selling a base of a matroid is always efficient, and implements the VCG outcome. An important tool in our analysis is studying first and second price auctions with externalities (bidders have valuations for each possible winner outcome), which can be of independent interest. We show that a Pure Nash Equilibrium always exists in a first price auction with externalities.
Data Accuracy Model for Distributed Clustering Algorithm based on Spatial Data Correlation in Wireless Sensor Networks
Venue: arXiv cs.NI 2011
Year: 2011

Objective: The main objective of this paper is to construct a distributed clustering algorithm based upon spatial data correlation among sensor nodes and perform data accuracy for each distributed cluster at their respective cluster head node. Design Procedure/Approach: We investigate that due to deployment of high density of sensor nodes in the sensor field, spatial data are highly correlated among sensor nodes in spatial domain. Based on high data correlation among sensor nodes, we propose a non -overlapping irregular distributed clustering algorithm with different sizes to collect most accurate or precise data at the cluster head node for each respective distributed cluster. To collect the most accurate data at the cluster head node for each distributed cluster in sensor field, we propose a Data accuracy model and compare the results with Information accuracy model. Finding: Simulation results shows that our propose Data accuracy model collects more accurate data and gives better performance than Information accuracy model at the cluster head node for each respective distributed cluster in our propose distributed clustering algorithm.Morover there exist a optimal cluster of sensor nodes which is adequate to perform approximately the same data accuracy achieve by a cluster. Practical Implementation: Measuring humidity and moisture content in an agricultural field, measuring temperature in physical environment. Inventive /Novel Idea: A distributed clustering algorithm is proposed based on spatial data correlation among sensor nodes with Data accuracy model.
Conscious Machines and Consciousness Oriented Programming
Venue: arXiv cs.AI 2011
Year: 2011

In this paper, we investigate the following question: how could you write such computer programs that can work like conscious beings? The motivation behind this question is that we want to create such applications that can see the future. The aim of this paper is to provide an overall conceptual framework for this new approach to machine consciousness. So we introduce a new programming paradigm called Consciousness Oriented Programming (COP).
Edge Transitive Ramanujan Graphs and Highly Symmetric LDPC Good Codes
Venue: arXiv cs.IT 2011
Year: 2011

We present a symmetric LDPC code with constant rate and constant distance (i.e. good LDPC code) that its constraint space is generated by the orbit of one constant weight constraint under a group action. Our construction provides the first symmetric LDPC good codes. This solves the main open problem raised by Kaufman and Wigderson in [4].
A First Approach on Modelling Staff Proactiveness in Retail Simulation Models
Venue: arXiv cs.AI 2011
Year: 2011

There has been a noticeable shift in the relative composition of the industry in the developed countries in recent years; manufacturing is decreasing while the service sector is becoming more important. However, currently most simulation models for investigating service systems are still built in the same way as manufacturing simulation models, using a process-oriented world view, i.e. they model the flow of passive entities through a system. These kinds of models allow studying aspects of operational management but are not well suited for studying the dynamics that appear in service systems due to human behaviour. For these kinds of studies we require tools that allow modelling the system and entities using an object-oriented world view, where intelligent objects serve as abstract "actors" that are goal directed and can behave proactively. In our work we combine process-oriented discrete event simulation modelling and object-oriented agent based simulation modelling to investigate the impact of people management practices on retail productivity. In this paper, we reveal in a series of experiments what impact considering proactivity can have on the output accuracy of simulation models of human centric systems. The model and data we use for this investigation are based on a case study in a UK department store. We show that considering proactivity positively influences the validity of these kinds of models and therefore allows analysts to make better recommendations regarding strategies to apply people management practises.