OpenRaiser/Intern-Atlas huggingface dataset:
A Variation of the Box-Counting Algorithm Applied to Colour Images
Venue: arXiv cs.CV 2011
Year: 2011

The box counting method for fractal dimension estimation had not been applied to large or colour images thus far due to the processing time required. In this letter we present a fast, easy to implement and very easily expandable to any number of dimensions variation, the box merging method. It is applied here in RGB images which are considered as sets in 5-D space.
A CONVERT compiler of REC for PDP-8
Venue: arXiv cs.PL 2011
Year: 2011

REC (REGULAR EXPRESSION COMPILER) is a programming language of simple structure developed originally for the PDP-8 computer of the Digital Equipment, Corporation, but readily adaptable to any other general purpose computer. It has been used extensively in teaching Algebra and Numerical Analysis in the Escuela Superior de Física y Matemáticas of the Instituto Politécnico Nacional. Moreover, the fact that the same control language, REC, is equally applicable and equally efficient over the whole range of computer facilities available to the students gives a very welcome coherence to the entire teaching program, including the course of Mathematical Logic which is devoted to the theoretical aspects of such matters. REC; derives its appeal from the fact that computers can be regarded reasonably well as Turing Machines. The REC notation is simply a manner of writing regular expression, somewhat more amenable to programming the Turing Machine which they control. If one does not wish to think so strictly in terms of Turing Machines, REC expressions still provide a means of defining the flow of control in a program which is quite convenient for many applications.
Aspects of Entertainment Distribution in an Intelligent Home Environment
Venue: arXiv cs.NI 2011
Year: 2011

The paper presents an implementation and tests of a simple home entertainment distribution architecture (server + multiple clients) implemented using two conventional cabling architectures: CATV coaxial cable and conventional Ethernet. This architecture is created taking into account the "Home gateway" concept present in most attempts to solve the problem of the "Intelligent home". A short presentation of the experimental is given with an investigation of the main performances obtained using this architecture. The experiments revealed that this simple solution makes possible to have entertainment and data services with performances close to traditional data services in a cost-effective architecture
A Fuzzy View on k-Means Based Signal Quantization with Application in Iris Segmentation
Venue: arXiv cs.CV 2011
Year: 2011

This paper shows that the k-means quantization of a signal can be interpreted both as a crisp indicator function and as a fuzzy membership assignment describing fuzzy clusters and fuzzy boundaries. Combined crisp and fuzzy indicator functions are defined here as natural generalizations of the ordinary crisp and fuzzy indicator functions, respectively. An application to iris segmentation is presented together with a demo program.
Proposed Quality Evaluation Framework to Incorporate Quality Aspects in Web Warehouse Creation
Venue: arXiv cs.IR 2011
Year: 2011

Web Warehouse is a read only repository maintained on the web to effectively handle the relevant data. Web warehouse is a system comprised of various subsystems and process. It supports the organizations in decision making. Quality of data store in web warehouse can affect the quality of decision made. For a valuable decision making it is required to consider the quality aspects in designing and modelling of a web warehouse. Thus data quality is one of the most important issues of the web warehousing system. Quality must be incorporated at different stages of the web warehousing system development. It is necessary to enhance existing data warehousing system to increase the data quality. It results in the storage of high quality data in the repository and efficient decision making. In this paper a Quality Evaluation Framework is proposed keeping in view the quality dimensions associated with different phases of a web warehouse. Further more, the proposed framework is validated empirically with the help of quantitative analysis.
Modelling Distributed Shape Priors by Gibbs Random Fields of Second Order
Venue: arXiv cs.CV 2011
Year: 2011

We analyse the potential of Gibbs Random Fields for shape prior modelling. We show that the expressive power of second order GRFs is already sufficient to express simple shapes and spatial relations between them simultaneously. This allows to model and recognise complex shapes as spatial compositions of simpler parts.
Computing q-gram Frequencies on Collage Systems
Venue: arXiv cs.DS 2011
Year: 2011

Collage systems are a general framework for representing outputs of various text compression algorithms. We consider the all $q$-gram frequency problem on compressed string represented as a collage system, and present an $O((q+h\log n)n)$-time $O(qn)$-space algorithm for calculating the frequencies for all $q$-grams that occur in the string. Here, $n$ and $h$ are respectively the size and height of the collage system.
Non-equilibrium Information Envelopes and the Capacity-Delay-Error-Tradeoff of Source Coding
Venue: arXiv cs.PF 2011
Year: 2011

This paper develops an envelope-based approach to establish a link between information and queueing theory. Unlike classical, equilibrium information theory, information envelopes focus on the dynamics of sources and coders, using functions of time that bound the number of bits generated. In the limit the information envelopes converge to the average behavior and recover the entropy of a source, respectively, the average codeword length of a coder. In contrast, on short time scales and for sources with memory it is shown that large deviations from known equilibrium results occur with non-negligible probability. These can cause significant network delays. Compared to well-known traffic models from queueing theory, information envelopes consider the functioning of information sources and coders, avoiding a priori assumptions, such as exponential traffic, or empirical, trace-based traffic models. Using results from the stochastic network calculus, the envelopes yield a characterization of the operating points of source coders by the triplet of capacity, delay, and error. In the limit, assuming an optimal coder the required capacity approaches the entropy with arbitrarily small probability of error if infinitely large delays are permitted. We derive a corresponding characterization of channels and prove that the model has the desirable property of additivity, that allows analyzing coders and channels separately.
Experimenting with Transitive Verbs in a DisCoCat
Venue: arXiv cs.CL 2011
Year: 2011

Formal and distributional semantic models offer complementary benefits in modeling meaning. The categorical compositional distributional (DisCoCat) model of meaning of Coecke et al. (arXiv:1003.4394v1 [cs.CL]) combines aspected of both to provide a general framework in which meanings of words, obtained distributionally, are composed using methods from the logical setting to form sentence meaning. Concrete consequences of this general abstract setting and applications to empirical data are under active study (Grefenstette et al., arxiv:1101.0309; Grefenstette and Sadrzadeh, arXiv:1106.4058v1 [cs.CL]). . In this paper, we extend this study by examining transitive verbs, represented as matrices in a DisCoCat. We discuss three ways of constructing such matrices, and evaluate each method in a disambiguation task developed by Grefenstette and Sadrzadeh (arXiv:1106.4058v1 [cs.CL]).
Cooperative oligopoly games: a probabilistic approach
Venue: arXiv cs.GT 2011
Year: 2011

We analyze the core of a cooperative Cournot game. We assume that when contemplating a deviation, the members of a coalition assign positive probability over all possible coalition structures that the non-members can form. We show that when the number of firms in the market is sufficiently large then the core of the underlying cooperative game is non-empty. Moreover, we show that the core of our game is a subset of the γ- core.
An Agent-based Strategy for Deploying Analysis Models into Specification and Design for Distributed APS Systems
Venue: arXiv cs.MA 2011
Year: 2011

Despite the extensive use of the agent technology in the Supply Chain Management field, its integration with Advanced Planning and Scheduling (APS) tools still represents a promising field with several open research questions. Specifically, the literature falls short in providing an integrated framework to analyze, specify, design and implement simulation experiments covering the whole simulation cycle. Thus, this paper proposes an agent-based strategy to convert the 'analysis' models into 'specification' and 'design' models combining two existing methodologies proposed in the literature. The first one is a recent and unique approach dedicated to the 'analysis' of agent-based APS systems. The second one is a well-established methodological framework to 'specify' and 'design' agent-based supply chain systems. The proposed conversion strategy is original and is the first one allowing simulation analysts to integrate the whole simulation development process in the domain of distributed APS.
E-DTN : A Multi-Interface Energy DTN Gateway
Venue: arXiv cs.NI 2011
Year: 2011

To overcome the problem of unavailability of grid power in rural India, we explore the possibility of powering WSN gateways using a bicycle dynamo. The "Data mule" bicycle generates its own power to ensure a self sustainable data transfer for information dissemination to small and marginal farmers. Our multi-interface WSN gateway is equipped with Bluetooth, Wi-Fi and GPRS technologies. To achieve our goal, we exploit the DTN stack in the energy sense and introduce necessary modifications to its configuration.
SD-AODV: A Protocol for Secure and Dynamic Data Dissemination in Mobile Ad Hoc Network
Venue: arXiv cs.NI 2011
Year: 2011

Security remains as a major concern in the mobile ad hoc networks. This paper presents a new protocol SD-AODV, which is an extension of the exiting protocol AODV. The proposed protocol is made secure and dynamic against three main types of routing attacks- wormhole attack, byzantine attack and blackhole attack. SD-AODV protocol was evaluated through simulation experiments done on Glomosim and performance of the network was measured in terms of packet delivery fraction, average end-to-end delay, global throughput and route errors of a mobile ad hoc network where a defined percentage of nodes behave maliciously. Experimentally it was found that the performance of the network did not degrade in the presence of the above said attacks indicating that the proposed protocol was secure against these attacks.
Randomisation and Derandomisation in Descriptive Complexity Theory
Venue: arXiv cs.LO 2011
Year: 2011

We study probabilistic complexity classes and questions of derandomisation from a logical point of view. For each logic L we introduce a new logic BPL, bounded error probabilistic L, which is defined from L in a similar way as the complexity class BPP, bounded error probabilistic polynomial time, is defined from PTIME. Our main focus lies on questions of derandomisation, and we prove that there is a query which is definable in BPFO, the probabilistic version of first-order logic, but not in Cinf, finite variable infinitary logic with counting. This implies that many of the standard logics of finite model theory, like transitive closure logic and fixed-point logic, both with and without counting, cannot be derandomised. Similarly, we present a query on ordered structures which is definable in BPFO but not in monadic second-order logic, and a query on additive structures which is definable in BPFO but not in FO. The latter of these queries shows that certain uniform variants of AC0 (bounded-depth polynomial sized circuits) cannot be derandomised. These results are in contrast to the general belief that most standard complexity classes can be derandomised. Finally, we note that BPIFP+C, the probabilistic version of fixed-point logic with counting, captures the complexity class BPP, even on unordered structures.
What can we learn from slow self-avoiding adaptive walks by an infinite radius search algorithm?
Venue: arXiv cs.NE 2011
Year: 2011

Slow self-avoiding adaptive walks by an infinite radius search algorithm (Limax) are analyzed as themselves, and as the network they form. The study is conducted on several NK problems and two HIFF problems. We find that examination of such "slacker" walks and networks can indicate relative search difficulty within a family of problems, help identify potential local optima, and detect presence of structure in fitness landscapes. Hierarchical walks are used to differentiate rugged landscapes which are hierarchical (e.g. HIFF) from those which are anarchic (e.g. NK). The notion of node viscidity as a measure of local optimum potential is introduced and found quite successful although more work needs to be done to improve its accuracy on problems with larger K.
What Trends in Chinese Social Media
Venue: arXiv cs.CY 2011
Year: 2011

There has been a tremendous rise in the growth of online social networks all over the world in recent times. While some networks like Twitter and Facebook have been well documented, the popular Chinese microblogging social network Sina Weibo has not been studied. In this work, we examine the key topics that trend on Sina Weibo and contrast them with our observations on Twitter. We find that there is a vast difference in the content shared in China, when compared to a global social network such as Twitter. In China, the trends are created almost entirely due to retweets of media content such as jokes, images and videos, whereas on Twitter, the trends tend to have more to do with current global events and news stories.
K-sort: A new sorting algorithm that beats Heap sort for n <= 70 lakhs!
Venue: arXiv cs.DS 2011
Year: 2011

Sundararajan and Chakraborty (2007) introduced a new version of Quick sort removing the interchanges. Khreisat (2007) found this algorithm to be competing well with some other versions of Quick sort. However, it uses an auxiliary array thereby increasing the space complexity. Here, we provide a second version of our new sort where we have removed the auxiliary array. This second improved version of the algorithm, which we call K-sort, is found to sort elements faster than Heap sort for an appreciably large array size (n <= 70,00,000) for uniform U[0, 1] inputs.
A Review on Elliptic Curve Cryptography for Embedded Systems
Venue: arXiv cs.CR 2011
Year: 2011

Importance of Elliptic Curves in Cryptography was independently proposed by Neal Koblitz and Victor Miller in 1985.Since then, Elliptic curve cryptography or ECC has evolved as a vast field for public key cryptography (PKC) systems. In PKC system, we use separate keys to encode and decode the data. Since one of the keys is distributed publicly in PKC systems, the strength of security depends on large key size. The mathematical problems of prime factorization and discrete logarithm are previously used in PKC systems. ECC has proved to provide same level of security with relatively small key sizes. The research in the field of ECC is mostly focused on its implementation on application specific systems. Such systems have restricted resources like storage, processing speed and domain specific CPU architecture.
The countable versus uncountable branching recurrences in computability logic
Venue: arXiv cs.LO 2011
Year: 2011

This paper introduces a new simplified version of the countable branching recurrence of Computability Logic, proves its equivalence to the old one, and shows that the basic logic induced by it is a proper superset of the basic logic induced by the uncountable branching recurrence. A further result of this paper is showing that the countable branching recurrence is strictly weaker than the uncountable branching recurrence in the sense that the latter logically implies the former but not vice versa.
Iterative Constructions and Private Data Release
Venue: arXiv cs.DS 2011
Year: 2011

In this paper we study the problem of approximately releasing the cut function of a graph while preserving differential privacy, and give new algorithms (and new analyses of existing algorithms) in both the interactive and non-interactive settings. Our algorithms in the interactive setting are achieved by revisiting the problem of releasing differentially private, approximate answers to a large number of queries on a database. We show that several algorithms for this problem fall into the same basic framework, and are based on the existence of objects which we call iterative database construction algorithms. We give a new generic framework in which new (efficient) IDC algorithms give rise to new (efficient) interactive private query release mechanisms. Our modular analysis simplifies and tightens the analysis of previous algorithms, leading to improved bounds. We then give a new IDC algorithm (and therefore a new private, interactive query release mechanism) based on the Frieze/Kannan low-rank matrix decomposition. This new release mechanism gives an improvement on prior work in a range of parameters where the size of the database is comparable to the size of the data universe (such as releasing all cut queries on dense graphs). We also give a non-interactive algorithm for efficiently releasing private synthetic data for graph cuts with error O(|V|^{1.5}). Our algorithm is based on randomized response and a non-private implementation of the SDP-based, constant-factor approximation algorithm for cut-norm due to Alon and Naor. Finally, we give a reduction based on the IDC framework showing that an efficient, private algorithm for computing sufficiently accurate rank-1 matrix approximations would lead to an improved efficient algorithm for releasing private synthetic data for graph cuts. We leave finding such an algorithm as our main open problem.
Computational Hardness of Enumerating Satisfying Spin-Assignments in Triangulations
Venue: arXiv cs.CC 2011
Year: 2011

Satisfying spin-assignments in triangulations of a surface are states of minimum energy of the antiferromagnetic Ising model on triangulations which correspond (via geometric duality) to perfect matchings in cubic bridgeless graphs. In this work we show that it is NP-complete to decide whether or not a surface triangulation admits a satisfying spin-assignment, and that it is #P-complete to determine the number of such assignments. Both results are derived via an elaborate (and atypical) reduction that maps a Boolean formula in 3-conjunctive normal form into a triangulation of an orientable closed surface.
A Glance into the Future of Human Computer Interaction
Venue: arXiv cs.HC 2011
Year: 2011

Computers have a direct impact on our lives nowadays. Human's interaction with the computer has modified with the passage of time as improvement in technology occurred the better the human computer interaction became. Today we are facilitated by the operating system that has reduced all the complexity of hardware and we undergo our computation in a very convenient way irrespective of the process occurring at the hardware level. Though the human computer interaction has improved but it's not done yet. If we come to the future the computer's role in our lives would be a lot more rather our life would be of the artificial intelligence. In our future the biggest resource would be component of time and wasting time for a key board entry or a mouse input would be unbearable so the need would be of the computer interaction environment that along with the complexity reduction also minimizes the time wastage in the human computer interaction. Accordingly in our future the computation would also be increased it would not be a simple operating system limited to a computer it would be computers managing our entire life activities hence fall out of domain of present computers electronic based architecture .In this research paper we propose a model that shall be meeting the future human computer interaction needs possessing linguistic human computer interference environment based on surface technology, automation and photonic computing, which would be reliable, efficient and quicker satisfying all the future artificial intelligence pre requisites.
How Hidden Can Be Even More Hidden?
Venue: arXiv cs.CR 2011
Year: 2011

The paper presents Deep Hiding Techniques (DHTs) that define general techniques that can be applied to every network steganography method to improve its undetectability and make steganogram extraction harder to perform. We define five groups of techniques that can make steganogram less susceptible to detection and extraction. For each of the presented group, examples of the usage are provided based on existing network steganography methods. To authors' best knowledge presented approach is the first attempt in the state of the art to systematically describe general solutions that can make steganographic communication more hidden and steganogram extraction harder to perform.
Performance and Convergence of Multi-user Online Learning
Venue: arXiv cs.MA 2011
Year: 2011

We study the problem of allocating multiple users to a set of wireless channels in a decentralized manner when the channel quali- ties are time-varying and unknown to the users, and accessing the same channel by multiple users leads to reduced quality due to interference. In such a setting the users not only need to learn the inherent channel quality and at the same time the best allocations of users to channels so as to maximize the social welfare. Assuming that the users adopt a certain online learning algorithm, we investigate under what conditions the socially optimal allocation is achievable. In particular we examine the effect of different levels of knowledge the users may have and the amount of communications and cooperation. The general conclusion is that when the cooperation of users decreases and the uncertainty about channel payoffs increases it becomes harder to achieve the socially opti- mal allocation.
Local Optima Networks of NK Landscapes with Neutrality
Venue: arXiv cs.AI 2011
Year: 2011

In previous work we have introduced a network-based model that abstracts many details of the underlying landscape and compresses the landscape information into a weighted, oriented graph which we call the local optima network. The vertices of this graph are the local optima of the given fitness landscape, while the arcs are transition probabilities between local optima basins. Here we extend this formalism to neutral fitness landscapes, which are common in difficult combinatorial search spaces. By using two known neutral variants of the NK family (i.e. NKp and NKq) in which the amount of neutrality can be tuned by a parameter, we show that our new definitions of the optima networks and the associated basins are consistent with the previous definitions for the non-neutral case. Moreover, our empirical study and statistical analysis show that the features of neutral landscapes interpolate smoothly between landscapes with maximum neutrality and non-neutral ones. We found some unknown structural differences between the two studied families of neutral landscapes. But overall, the network features studied confirmed that neutrality, in landscapes with percolating neutral networks, may enhance heuristic search. Our current methodology requires the exhaustive enumeration of the underlying search space. Therefore, sampling techniques should be developed before this analysis can have practical implications. We argue, however, that the proposed model offers a new perspective into the problem difficulty of combinatorial optimization problems and may inspire the design of more effective search heuristics.