OpenRaiser/Intern-Atlas huggingface dataset:
Evaluation of Huffman and Arithmetic Algorithms for Multimedia Compression Standards
Venue: arXiv cs.IT 2011
Year: 2011

Compression is a technique to reduce the quantity of data without excessively reducing the quality of the multimedia data. The transition and storing of compressed multimedia data is much faster and more efficient than original uncompressed multimedia data. There are various techniques and standards for multimedia data compression, especially for image compression such as the JPEG and JPEG2000 standards. These standards consist of different functions such as color space conversion and entropy coding. Arithmetic and Huffman coding are normally used in the entropy coding phase. In this paper we try to answer the following question. Which entropy coding, arithmetic or Huffman, is more suitable compared to other from the compression ratio, performance, and implementation points of view? We have implemented and tested Huffman and arithmetic algorithms. Our implemented results show that compression ratio of arithmetic coding is better than Huffman coding, while the performance of the Huffman coding is higher than Arithmetic coding. In addition, implementation of Huffman coding is much easier than the Arithmetic coding.
Orthogonal Query Expansion
Venue: arXiv cs.IR 2011
Year: 2011

Over the last fifteen years, web searching has seen tremendous improvements. Starting from a nearly random collection of matching pages in 1995, today, search engines tend to satisfy the user's informational need on well-formulated queries. One of the main remaining challenges is to satisfy the users' needs when they provide a poorly formulated query. When the pages matching the user's original keywords are judged to be unsatisfactory, query expansion techniques are used to alter the result set. These techniques find keywords that are similar to the keywords given by the user, which are then appended to the original query leading to a perturbation of the result set. However, when the original query is sufficiently ill-posed, the user's informational need is best met using entirely different keywords, and a small perturbation of the original result set is bound to fail. We propose a novel approach that is not based on the keywords of the original query. We intentionally seek out orthogonal queries, which are related queries that have low similarity to the user's query. The result sets of orthogonal queries intersect with the result set of the original query on a small number of pages. An orthogonal query can access the user's informational need while consisting of entirely different terms than the original query. We illustrate the effectiveness of our approach by proposing a query expansion method derived from these observations that improves upon results obtained using the Yahoo BOSS infrastructure.
A tight bound on the length of odd cycles in the incompatibility graph of a non-C1P matrix
Venue: arXiv cs.DS 2011
Year: 2011

A binary matrix has the consecutive ones property (C1P) if it is possible to order the columns so that all 1s are consecutive in every row. In [McConnell, SODA 2004 768-777] the notion of incompatibility graph of a binary matrix was introduced and it was shown that odd cycles of this graph provide a certificate that a matrix does not have the consecutive ones property. A bound of (k+2) was claimed for the smallest odd cycle of a non-C1P matrix with k columns. In this note we show that this result can be obtained simply and directly via Tucker patterns, and that the correct bound is (k+2) when k is even, but (k+3) when k is odd.
Phase Retrieval via Matrix Completion
Venue: arXiv cs.IT 2011
Year: 2011

This paper develops a novel framework for phase retrieval, a problem which arises in X-ray crystallography, diffraction imaging, astronomical imaging and many other applications. Our approach combines multiple structured illuminations together with ideas from convex programming to recover the phase from intensity measurements, typically from the modulus of the diffracted wave. We demonstrate empirically that any complex-valued object can be recovered from the knowledge of the magnitude of just a few diffracted patterns by solving a simple convex optimization problem inspired by the recent literature on matrix completion. More importantly, we also demonstrate that our noise-aware algorithms are stable in the sense that the reconstruction degrades gracefully as the signal-to-noise ratio decreases. Finally, we introduce some theory showing that one can design very simple structured illumination patterns such that three diffracted figures uniquely determine the phase of the object we wish to recover.
Stealthy Traffic Analysis of Low-Latency Anonymous Communication Using Throughput Fingerprinting
Venue: arXiv cs.CR 2011
Year: 2011

Anonymity systems such as Tor aim to enable users to communicate in a manner that is untraceable by adversaries that control a small number of machines. To provide efficient service to users, these anonymity systems make full use of forwarding capacity when sending traffic between intermediate relays. In this paper, we show that doing this leaks information about the set of Tor relays in a circuit (path). We present attacks that, with high confidence and based solely on throughput information, can (a) reduce the attacker's uncertainty about the bottleneck relay of any Tor circuit whose throughput can be observed, (b) exactly identify the guard relay(s) of a Tor user when circuit throughput can be observed over multiple connections, and (c) identify whether two concurrent TCP connections belong to the same Tor user, breaking unlinkability. Our attacks are stealthy, and cannot be readily detected by a user or by Tor relays. We validate our attacks using experiments over the live Tor network. We find that the attacker can substantially reduce the entropy of a bottleneck relay distribution of a Tor circuit whose throughput can be observed-the entropy gets reduced by a factor of 2 in the median case. Such information leaks from a single Tor circuit can be combined over multiple connections to exactly identify a user's guard relay(s). Finally, we are also able to link two connections from the same initiator with a crossover error rate of less than 1.5% in under 5 minutes. Our attacks are also more accurate and require fewer resources than previous attacks on Tor.
Transmission of Successful Route Error Message(RERR) in Routing Aware Multiple Description Video Coding over Mobile Ad-Hoc Network
Venue: arXiv cs.MM 2011
Year: 2011

Video transmission over mobile ad-hoc networks is becoming important as these networks become more widely used in the wireless networks. We propose a routing-aware multiple description video coding approach to support video transmission over mobile ad-hoc networks with single and multiple path transport. We build a model to estimate the packet loss probability of each packet transmitted over the network based on the standard ad-hoc routing messages and network parameters without losing the RERR message. We then calculate the frame loss probability in order to eliminate error without any loss of data.
Intelligent Bees for QoS Routing in Networks-on-Chip
Venue: arXiv cs.AR 2011
Year: 2011

Networks-on-Chip (NoCs) for future many-core processor platforms integrate more and more heterogeneous components of different types and many real-time and latency-sensitive applications can run on a single chip concurrently. The reconfigurable FPGA and reconfigurable NoCs have emerged for the purpose of reusability. Those types' traffics within NoCs exhibit diverse, burst, and unpredictable communication patterns. QoS guaranteed mechanisms are necessary to provide guaranteed throughput (GT) or guaranteed bandwidth (GB) performance for NoCs. In this paper, we propose a QoS routing algorithm inspired by bees' foraging behaviors to provide guaranteed bandwidth performance. Virtual circuits and Spatial Division Multiplexing are employed to maintain available paths for different type's traffics.
Drawing Sound Conclusions from Unsound Premises
Venue: arXiv cs.LO 2011
Year: 2011

Given sets $Φ_1=\{ϕ_{11},...,ϕ_{1u(1)}\}, ...,Φ_{z}=\{ϕ_{z1},...,ϕ_{zu(z)}\}$ of boolean formulas, a formula $ω$ follows from the conjunction $\bigwedgeΦ_i= \bigwedge ϕ_{ij}$ iff $\neg ω\wedge \bigwedge_{i=1}^z Φ_i$ is unsatisfiable. Now assume that, given integers $0\leq e_i < u(i)$, we must check if $\neg ω\wedge \bigwedge_{i=1}^z Φ'_i$ remains unsatisfiable, where $Φ'_i\subseteq Φ_i$ is obtained by deleting $\,\,e_{i}$ arbitrarily chosen formulas of $Φ_i$, for each $i=1,...,z.$ Intuitively, does $ω$ {\it stably} follow, after removing $e_i$ random formulas from each $Φ_i$? We construct a quadratic reduction of this problem to the consequence problem in infinite-valued \luk\ logic Ł$_\infty$. In this way we obtain a self-contained proof that the Ł$_\infty$-consequence problem is coNP-complete.
Ranking of Wikipedia articles in search engines revisited: Fair ranking for reasonable quality?
Venue: arXiv cs.IR 2011
Year: 2011

This paper aims to review the fiercely discussed question of whether the ranking of Wikipedia articles in search engines is justified by the quality of the articles. After an overview of current research on information quality in Wikipedia, a summary of the extended discussion on the quality of encyclopedic entries in general is given. On this basis, a heuristic method for evaluating Wikipedia entries is developed and applied to Wikipedia articles that scored highly in a search engine retrieval effectiveness test and compared with the relevance judgment of jurors. In all search engines tested, Wikipedia results are unanimously judged better by the jurors than other results on the corresponding results position. Relevance judgments often roughly correspond with the results from the heuristic evaluation. Cases in which high relevance judgments are not in accordance with the comparatively low score from the heuristic evaluation are interpreted as an indicator of a high degree of trust in Wikipedia. One of the systemic shortcomings of Wikipedia lies in its necessarily incoherent user model. A further tuning of the suggested criteria catalogue, for instance the different weighing of the supplied criteria, could serve as a starting point for a user model differentiated evaluation of Wikipedia articles. Approved methods of quality evaluation of reference works are applied to Wikipedia articles and integrated with the question of search engine evaluation.
Review on Feature Selection Techniques and the Impact of SVM for Cancer Classification using Gene Expression Profile
Venue: arXiv cs.CE 2011
Year: 2011

The DNA microarray technology has modernized the approach of biology research in such a way that scientists can now measure the expression levels of thousands of genes simultaneously in a single experiment. Gene expression profiles, which represent the state of a cell at a molecular level, have great potential as a medical diagnosis tool. But compared to the number of genes involved, available training data sets generally have a fairly small sample size for classification. These training data limitations constitute a challenge to certain classification methodologies. Feature selection techniques can be used to extract the marker genes which influence the classification accuracy effectively by eliminating the un wanted noisy and redundant genes This paper presents a review of feature selection techniques that have been employed in micro array data based cancer classification and also the predominant role of SVM for cancer classification.
An Automatic Clustering Technique for Optimal Clusters
Venue: arXiv cs.CV 2011
Year: 2011

This paper proposes a simple, automatic and efficient clustering algorithm, namely, Automatic Merging for Optimal Clusters (AMOC) which aims to generate nearly optimal clusters for the given datasets automatically. The AMOC is an extension to standard k-means with a two phase iterative procedure combining certain validation techniques in order to find optimal clusters with automation of merging of clusters. Experiments on both synthetic and real data have proved that the proposed algorithm finds nearly optimal clustering structures in terms of number of clusters, compactness and separation.
An Extension of Semantic Proximity for Fuzzy Multivalued Dependencies in Fuzzy Relational Database
Venue: arXiv cs.DB 2011
Year: 2011

Following the development of fuzzy logic theory by Lotfi Zadeh, its applications were investigated by researchers in different fields. Presenting and working with uncertain data is a complex problem. To solve for such a complex problem, the structure of relationships and operators dependent on such relationships must be repaired. The fuzzy database has integrity limitations including data dependencies. In this paper, first fuzzy multivalued dependency based semantic proximity and its problems are studied. To solve these problems, the semantic proximity's formula is modified, and fuzzy multivalued dependency based on the concept of extension of semantic proximity with αdegree is defined in fuzzy relational database which includes Crisp, NULL and fuzzy values, and also inference rules for this dependency are defined, and their completeness is proved. Finally, we will show that fuzzy functional dependency based on this concept is a special case of fuzzy multivalued dependency in fuzzy relational database.
Synthesis of Distributed Control and Communication Schemes from Global LTL Specifications
Venue: arXiv cs.RO 2011
Year: 2011

We introduce a technique for synthesis of control and communication strategies for a team of agents from a global task specification given as a Linear Temporal Logic (LTL) formula over a set of properties that can be satisfied by the agents. We consider a purely discrete scenario, in which the dynamics of each agent is modeled as a finite transition system. The proposed computational framework consists of two main steps. First, we extend results from concurrency theory to check whether the specification is distributable among the agents. Second, we generate individual control and communication strategies by using ideas from LTL model checking. We apply the method to automatically deploy a team of miniature cars in our Robotic Urban-Like Environment.
Trace Norm Regularized Tensor Classification and Its Online Learning Approaches
Venue: arXiv cs.NA 2011
Year: 2011

In this paper we propose an algorithm to classify tensor data. Our methodology is built on recent studies about matrix classification with the trace norm constrained weight matrix and the tensor trace norm. Similar to matrix classification, the tensor classification is formulated as a convex optimization problem which can be solved by using the off-the-shelf accelerated proximal gradient (APG) method. However, there are no analytic solutions as the matrix case for the updating of the weight tensors via the proximal gradient. To tackle this problem, the Douglas-Rachford splitting technique and the alternating direction method of multipliers (ADM) used in tensor completion are adapted to update the weight tensors. Further more, due to the demand of real applications, we also propose its online learning approaches. Experiments demonstrate the efficiency of the methods.
Pattern Matching under Polynomial Transformation
Venue: arXiv cs.DS 2011
Year: 2011

We consider a class of pattern matching problems where a normalising transformation is applied at every alignment. Normalised pattern matching plays a key role in fields as diverse as image processing and musical information processing where application specific transformations are often applied to the input. By considering the class of polynomial transformations of the input, we provide fast algorithms and the first lower bounds for both new and old problems. Given a pattern of length m and a longer text of length n where both are assumed to contain integer values only, we first show O(n log m) time algorithms for pattern matching under linear transformations even when wildcard symbols can occur in the input. We then show how to extend the technique to polynomial transformations of arbitrary degree. Next we consider the problem of finding the minimum Hamming distance under polynomial transformation. We show that, for any epsilon>0, there cannot exist an O(n m^(1-epsilon)) time algorithm for additive and linear transformations conditional on the hardness of the classic 3SUM problem. Finally, we consider a version of the Hamming distance problem under additive transformations with a bound k on the maximum distance that need be reported. We give a deterministic O(nk log k) time solution which we then improve by careful use of randomisation to O(n sqrt(k log k) log n) time for sufficiently small k. Our randomised solution outputs the correct answer at every position with high probability.
A New Method for Lower Bounds on the Running Time of Evolutionary Algorithms
Venue: arXiv cs.NE 2011
Year: 2011

We present a new method for proving lower bounds on the expected running time of evolutionary algorithms. It is based on fitness-level partitions and an additional condition on transition probabilities between fitness levels. The method is versatile, intuitive, elegant, and very powerful. It yields exact or near-exact lower bounds for LO, OneMax, long k-paths, and all functions with a unique optimum. Most lower bounds are very general: they hold for all evolutionary algorithms that only use bit-flip mutation as variation operator---i.e. for all selection operators and population models. The lower bounds are stated with their dependence on the mutation rate. These results have very strong implications. They allow to determine the optimal mutation-based algorithm for LO and OneMax, i.e., which algorithm minimizes the expected number of fitness evaluations. This includes the choice of the optimal mutation rate.
Abstract Diagnosis for Timed Concurrent Constraint programs
Venue: arXiv cs.PL 2011
Year: 2011

The Timed Concurrent Constraint Language (tccp in short) is a concurrent logic language based on the simple but powerful concurrent constraint paradigm of Saraswat. In this paradigm, the notion of store-as-value is replaced by the notion of store-as-constraint, which introduces some differences w.r.t. other approaches to concurrency. In this paper, we provide a general framework for the debugging of tccp programs. To this end, we first present a new compact, bottom-up semantics for the language that is well suited for debugging and verification purposes in the context of reactive systems. We also provide an abstract semantics that allows us to effectively implement debugging algorithms based on abstract interpretation. Given a tccp program and a behavior specification, our debugging approach automatically detects whether the program satisfies the specification. This differs from other semiautomatic approaches to debugging and avoids the need to provide symptoms in advance. We show the efficacy of our approach by introducing two illustrative examples. We choose a specific abstract domain and show how we can detect that a program is erroneous.
Solving Limited Memory Influence Diagrams
Venue: arXiv cs.AI 2011
Year: 2011

We present a new algorithm for exactly solving decision making problems represented as influence diagrams. We do not require the usual assumptions of no forgetting and regularity; this allows us to solve problems with simultaneous decisions and limited information. The algorithm is empirically shown to outperform a state-of-the-art algorithm on randomly generated problems of up to 150 variables and $10^{64}$ solutions. We show that the problem is NP-hard even if the underlying graph structure of the problem has small treewidth and the variables take on a bounded number of states, but that a fully polynomial time approximation scheme exists for these cases. Moreover, we show that the bound on the number of states is a necessary condition for any efficient approximation scheme.
Conjure Revisited: Towards Automated Constraint Modelling
Venue: arXiv cs.AI 2011
Year: 2011

Automating the constraint modelling process is one of the key challenges facing the constraints field, and one of the principal obstacles preventing widespread adoption of constraint solving. This paper focuses on the refinement-based approach to automated modelling, where a user specifies a problem in an abstract constraint specification language and it is then automatically refined into a constraint model. In particular, we revisit the Conjure system that first appeared in prototype form in 2005 and present a new implementation with a much greater coverage of the specification language Essence.
Progressive versus Random Projections for Compressive Capture of Images, Lightfields and Higher Dimensional Visual Signals
Venue: arXiv cs.CV 2011
Year: 2011

Computational photography involves sophisticated capture methods. A new trend is to capture projection of higher dimensional visual signals such as videos, multi-spectral data and lightfields on lower dimensional sensors. Carefully designed capture methods exploit the sparsity of the underlying signal in a transformed domain to reduce the number of measurements and use an appropriate reconstruction method. Traditional progressive methods may capture successively more detail using a sequence of simple projection basis, such as DCT or wavelets and employ straightforward backprojection for reconstruction. Randomized projection methods do not use any specific sequence and use L0 minimization for reconstruction. In this paper, we analyze the statistical properties of natural images, videos, multi-spectral data and light-fields and compare the effectiveness of progressive and random projections. We define effectiveness by plotting reconstruction SNR against compression factor. The key idea is a procedure to measure best-case effectiveness that is fast, independent of specific hardware and independent of the reconstruction procedure. We believe this is the first empirical study to compare different lossy capture strategies without the complication of hardware or reconstruction ambiguity. The scope is limited to linear non-adaptive sensing. The results show that random projections produce significant advantages over other projections only for higher dimensional signals, and suggest more research to nascent adaptive and non-linear projection methods.
Modular Abstractions of Reactive Nodes using Disjunctive Invariants
Venue: arXiv cs.PL 2011
Year: 2011

We wish to abstract nodes in a reactive programming language, such as Lustre, into nodes with a simpler control structure, with a bound on the number of control states. In order to do so, we compute disjunctive invariants in predicate abstraction, with a bounded number of disjuncts, then we abstract the node, each disjunct representing an abstract state. The computation of the disjunctive invariant is performed by a form of quantifier elimination expressed using SMT-solving. The same method can also be used to obtain disjunctive loop invariants.
Efficient Personalized Web Mining: Utilizing The Most Utilized Data
Venue: arXiv cs.IR 2011
Year: 2011

Looking into the growth of information in the web it is a very tedious process of getting the exact information the user is looking for. Many search engines generate user profile related data listing. This paper involves one such process where the rating is given to the link that the user is clicking on. Rather than avoiding the uninterested links both interested links and the uninterested links are listed. But sorted according to the weightings given to each link by the number of visit made by the particular user and the amount of time spent on the particular link.