OpenRaiser/Intern-Atlas huggingface dataset:
Benchmarks, Performance Evaluation and Contests for 3D Shape Retrieval
Venue: arXiv cs.CV 2011
Year: 2011

Benchmarking of 3D Shape retrieval allows developers and researchers to compare the strengths of different algorithms on a standard dataset. Here we describe the procedures involved in developing a benchmark and issues involved. We then discuss some of the current 3D shape retrieval benchmarks efforts of our group and others. We also review the different performance evaluation measures that are developed and used by researchers in the community. After that we give an overview of the 3D shape retrieval contest (SHREC) tracks run under the EuroGraphics Workshop on 3D Object Retrieval and give details of tracks that we organized for SHREC 2010. Finally we demonstrate some of the results based on the different SHREC contest tracks and the NIST shape benchmark.
Tecnologia Móvel: Uma Tendência, Uma Realidade
Venue: arXiv cs.CY 2011
Year: 2011

Currently, mobility presents itself as a major innovation in historic technological revolution. From the first decade of this century, nothing compares to what happened in the field of Information Technology (IT), which is adding to market a range of news relating to infrastructure such as mobile computing hardware, software, computer networks, etc.. From a handheld as a wireless device, iPad, Smartphone, you can connect to the digital world, people, customers, business partners, etc.. Given the infinite range of information, services and resources available in the electronic world, it is considered that few are those, markets and people who want to be left behind. The interest in this channel of communication becomes not only a new strategy of marketing and communications. Mobile devices are becoming more sophisticated and allows access to the web. Thinking in this context is that manufacturers of electronic components face each other in a war over the disputed technology to a competitive environment that is open to those who put on the market the product more attractive, interactive and versatile.
A Multiple-Choice Test Recognition System based on the Gamera Framework
Venue: arXiv cs.CV 2011
Year: 2011

This article describes JECT-OMR, a system that analyzes digital images representing scans of multiple-choice tests compiled by students. The system performs a structural analysis of the document in order to get the chosen answer for each question, and it also contains a bar-code decoder, used for the identification of additional information encoded in the document. JECT-OMR was implemented using the Python programming language, and leverages the power of the Gamera framework in order to accomplish its task. The system exhibits an accuracy of over 99% in the recognition of marked and non-marked squares representing answers, thus making it suitable for real world applications
Non-Malleable Codes from the Wire-Tap Channel
Venue: arXiv cs.CR 2011
Year: 2011

Recently, Dziembowski et al. introduced the notion of non-malleable codes (NMC), inspired from the notion of non-malleability in cryptography and the work of Gennaro et al. in 2004 on tamper proof security. Informally, when using NMC, if an attacker modifies a codeword, decoding this modified codeword will return either the original message or a completely unrelated value. The definition of NMC is related to a family of modifications authorized to the attacker. In their paper, Dziembowski et al. propose a construction valid for the family of all bit-wise independent functions. In this article, we study the link between the second version of the Wire-Tap (WT) Channel, introduced by Ozarow and Wyner in 1984, and NMC. Using coset-coding, we describe a new construction for NMC w.r.t. a subset of the family of bit-wise independent functions. Our scheme is easier to build and more efficient than the one proposed by Dziembowski et al.
Compressed k2-Triples for Full-In-Memory RDF Engines
Venue: arXiv cs.IR 2011
Year: 2011

Current "data deluge" has flooded the Web of Data with very large RDF datasets. They are hosted and queried through SPARQL endpoints which act as nodes of a semantic net built on the principles of the Linked Data project. Although this is a realistic philosophy for global data publishing, its query performance is diminished when the RDF engines (behind the endpoints) manage these huge datasets. Their indexes cannot be fully loaded in main memory, hence these systems need to perform slow disk accesses to solve SPARQL queries. This paper addresses this problem by a compact indexed RDF structure (called k2-triples) applying compact k2-tree structures to the well-known vertical-partitioning technique. It obtains an ultra-compressed representation of large RDF graphs and allows SPARQL queries to be full-in-memory performed without decompression. We show that k2-triples clearly outperforms state-of-the-art compressibility and traditional vertical-partitioning query resolution, remaining very competitive with multi-index solutions.
A New Achievable DoF Region for the 3-user MxN Symmetric Interference Channel
Venue: arXiv cs.IT 2011
Year: 2011

In this paper, the 3-user multiple-input multiple-output Gaussian interference channel with M antennas at each transmitter and N antennas at each receiver is considered. It is assumed that the channel coefficients are constant and known to all transmitters and receivers. A novel scheme is presented that spans a new achievable degrees of freedom region. For some values of M and N, the proposed scheme achieve higher number of DoF than are currently achievable, while for other values it meets the best known upperbound. Simulation results are presented showing the superior performance of the proposed schemes to earlier approaches.
Privacy-Preserving Group Data Access via Stateless Oblivious RAM Simulation
Venue: arXiv cs.CR 2011
Year: 2011

We study the problem of providing privacy-preserving access to an outsourced honest-but-curious data repository for a group of trusted users. We show that such privacy-preserving data access is possible using a combination of probabilistic encryption, which directly hides data values, and stateless oblivious RAM simulation, which hides the pattern of data accesses. We give simulations that have only an $O(\log n)$ amortized time overhead for simulating a RAM algorithm, $\cal A$, that has a memory of size $n$, using a scheme that is data-oblivious with very high probability assuming the simulation has access to a private workspace of size $O(n^ν)$, for any given fixed constant $ν>0$. This simulation makes use of pseudorandom hash functions and is based on a novel hierarchy of cuckoo hash tables that all share a common stash. We also provide results from an experimental simulation of this scheme, showing its practicality. In addition, in a result that may be of some theoretical interest, we also show that one can eliminate the dependence on pseudorandom hash functions in our simulation while having the overhead rise to be $O(\log^2 n)$.
Personalized Social Recommendations - Accurate or Private?
Venue: arXiv cs.DB 2011
Year: 2011

With the recent surge of social networks like Facebook, new forms of recommendations have become possible - personalized recommendations of ads, content, and even new friend and product connections based on one's social interactions. Since recommendations may use sensitive social information, it is speculated that these recommendations are associated with privacy risks. The main contribution of this work is in formalizing these expected trade-offs between the accuracy and privacy of personalized social recommendations. In this paper, we study whether "social recommendations", or recommendations that are solely based on a user's social network, can be made without disclosing sensitive links in the social graph. More precisely, we quantify the loss in utility when existing recommendation algorithms are modified to satisfy a strong notion of privacy, called differential privacy. We prove lower bounds on the minimum loss in utility for any recommendation algorithm that is differentially private. We adapt two privacy preserving algorithms from the differential privacy literature to the problem of social recommendations, and analyze their performance in comparison to the lower bounds, both analytically and experimentally. We show that good private social recommendations are feasible only for a small subset of the users in the social network or for a lenient setting of privacy parameters.
Physical-Layer Network Coding: Tutorial, Survey, and Beyond
Venue: arXiv cs.NI 2011
Year: 2011

The concept of physical-layer network coding (PNC) was proposed in 2006 for application in wireless networks. Since then it has developed into a subfield of network coding with wide followings. The basic idea of PNC is to exploit the network coding operation that occurs naturally when electromagnetic (EM) waves are superimposed on one another. This simple idea turns out to have profound and fundamental ramifications. Subsequent works by various researchers have led to many new results in the domains of 1) wireless communication; 2) wireless information theory; and 3) wireless networking. The purpose of this paper is fourfold. First, we give a brief tutorial on the basic concept of PNC. Second, we survey and discuss recent key results in the three aforementioned areas. Third, we examine a critical issue in PNC: synchronization. It has been a common belief that PNC requires tight synchronization. Our recent results suggest, however, that PNC may actually benefit from asynchrony. Fourth, we propose that PNC is not just for wireless networks; it can also be useful in optical networks. We provide an example showing that the throughput of a passive optical network (PON) could potentially be raised by 100% with PNC.
Correction of Noisy Sentences using a Monolingual Corpus
Venue: arXiv cs.DL 2011
Year: 2011

Correction of Noisy Natural Language Text is an important and well studied problem in Natural Language Processing. It has a number of applications in domains like Statistical Machine Translation, Second Language Learning and Natural Language Generation. In this work, we consider some statistical techniques for Text Correction. We define the classes of errors commonly found in text and describe algorithms to correct them. The data has been taken from a poorly trained Machine Translation system. The algorithms use only a language model in the target language in order to correct the sentences. We use phrase based correction methods in both the algorithms. The phrases are replaced and combined to give us the final corrected sentence. We also present the methods to model different kinds of errors, in addition to results of the working of the algorithms on the test set. We show that one of the approaches fail to achieve the desired goal, whereas the other succeeds well. In the end, we analyze the possible reasons for such a trend in performance.
Integrating Testing and Interactive Theorem Proving
Venue: arXiv cs.SE 2011
Year: 2011

Using an interactive theorem prover to reason about programs involves a sequence of interactions where the user challenges the theorem prover with conjectures. Invariably, many of the conjectures posed are in fact false, and users often spend considerable effort examining the theorem prover's output before realizing this. We present a synergistic integration of testing with theorem proving, implemented in the ACL2 Sedan (ACL2s), for automatically generating concrete counterexamples. Our method uses the full power of the theorem prover and associated libraries to simplify conjectures; this simplification can transform conjectures for which finding counterexamples is hard into conjectures where finding counterexamples is trivial. In fact, our approach even leads to better theorem proving, e.g. if testing shows that a generalization step leads to a false conjecture, we force the theorem prover to backtrack, allowing it to pursue more fruitful options that may yield a proof. The focus of the paper is on the engineering of a synergistic integration of testing with interactive theorem proving; this includes extending ACL2 with new functionality that we expect to be of general interest. We also discuss our experience in using ACL2s to teach freshman students how to reason about their programs.
A Modeling Approach based on UML/MARTE for GPU Architecture
Venue: arXiv cs.DC 2011
Year: 2011

Nowadays, the High Performance Computing is part of the context of embedded systems. Graphics Processing Units (GPUs) are more and more used in acceleration of the most part of algorithms and applications. Over the past years, not many efforts have been done to describe abstractions of applications in relation to their target architectures. Thus, when developers need to associate applications and GPUs, for example, they find difficulty and prefer using API for these architectures. This paper presents a metamodel extension for MARTE profile and a model for GPU architectures. The main goal is to specify the task and data allocation in the memory hierarchy of these architectures. The results show that this approach will help to generate code for GPUs based on model transformations using Model Driven Engineering (MDE).
Standardization of information systems development processes and banking industry adaptations
Venue: arXiv cs.SE 2011
Year: 2011

This paper examines the current system development processes of three major Turkish banks in terms of compliance to internationally accepted system development and software engineering standards to determine the common process problems of banks. After an in-depth investigation into system development and software engineering standards, related process-based standards were selected. Questions were then prepared covering the whole system development process by applying the classical Waterfall life cycle model. Each question is made up of guidance and suggestions from the international system development standards. To collect data, people from the information technology departments of three major banks in Turkey were interviewed. Results have been aggregated by examining the current process status of the three banks together. Problematic issues were identified using the international system development standards.
On the Cohomology of 3D Digital Images
Venue: arXiv cs.CV 2011
Year: 2011

We propose a method for computing the cohomology ring of three--dimensional (3D) digital binary-valued pictures. We obtain the cohomology ring of a 3D digital binary--valued picture $I$, via a simplicial complex K(I)topologically representing (up to isomorphisms of pictures) the picture I. The usefulness of a simplicial description of the "digital" cohomology ring of 3D digital binary-valued pictures is tested by means of a small program visualizing the different steps of the method. Some examples concerning topological thinning, the visualization of representative (co)cycles of (co)homology generators and the computation of the cup product on the cohomology of simple pictures are showed.
Synthesis of Parallel Binary Machines
Venue: arXiv cs.CR 2011
Year: 2011

Binary machines are a generalization of Feedback Shift Registers (FSRs) in which both, feedback and feedforward, connections are allowed and no chain connection between the register stages is required. In this paper, we present an algorithm for synthesis of binary machines with the minimum number of stages for a given degree of parallelization. Our experimental results show that for sequences with high linear complexity such as complementary, Legendre, or truly random, parallel binary machines are an order of magnitude smaller than parallel FSRs generating the same sequence. The presented approach can potentially be of advantage for any application which requires sequences with high spectrum efficiency or high security, such as data transmission, wireless communications, and cryptography.
On the Limits of Sequential Testing in High Dimensions
Venue: arXiv cs.IT 2011
Year: 2011

This paper presents results pertaining to sequential methods for support recovery of sparse signals in noise. Specifically, we show that any sequential measurement procedure fails provided the average number of measurements per dimension grows slower then log s / D(f0||f1) where s is the level of sparsity, and D(f0||f1) the Kullback-Leibler divergence between the underlying distributions. For comparison, we show any non-sequential procedure fails provided the number of measurements grows at a rate less than log n / D(f1||f0), where n is the total dimension of the problem. Lastly, we show that a simple procedure termed sequential thresholding guarantees exact support recovery provided the average number of measurements per dimension grows faster than (log s + log log n) / D(f0||f1), a mere additive factor more than the lower bound.
Mapping excellence in the geography of science: An approach based on Scopus data
Venue: arXiv cs.DL 2011
Year: 2011

As research becomes an ever more globalized activity, there is growing interest in national and international comparisons of standards and quality in different countries and regions. A sign for this trend is the increasing interest in rankings of universities according to their research performance, both inside but also outside the scientific environment. New methods presented in this paper, enable us to map centers of excellence around the world using programs that are freely available. Based on Scopus data, field-specific excellence can be identified and agglomerated in regions and cities where recently highly-cited papers were published. Differences in performance rates can be visualized on the map using colors and sizes of the marks.
Fault-tolerant Algorithms for Tick-Generation in Asynchronous Logic: Robust Pulse Generation
Venue: arXiv cs.DC 2011
Year: 2011

Today's hardware technology presents a new challenge in designing robust systems. Deep submicron VLSI technology introduced transient and permanent faults that were never considered in low-level system designs in the past. Still, robustness of that part of the system is crucial and needs to be guaranteed for any successful product. Distributed systems, on the other hand, have been dealing with similar issues for decades. However, neither the basic abstractions nor the complexity of contemporary fault-tolerant distributed algorithms match the peculiarities of hardware implementations. This paper is intended to be part of an attempt striving to overcome this gap between theory and practice for the clock synchronization problem. Solving this task sufficiently well will allow to build a very robust high-precision clocking system for hardware designs like systems-on-chips in critical applications. As our first building block, we describe and prove correct a novel Byzantine fault-tolerant self-stabilizing pulse synchronization protocol, which can be implemented using standard asynchronous digital logic. Despite the strict limitations introduced by hardware designs, it offers optimal resilience and smaller complexity than all existing protocols.
Search for Hidden Knowledge in Collective Intelligence dealing Indeterminacy Ontology of Folksonomy with Linguistic Pragmatics and Quantum Logic
Venue: arXiv cs.IR 2011
Year: 2011

Information retrieval is not only the most frequent application executed on the Web but it is also the base of different types of applications. Considering collective intelligence of groups of individuals as a framework for evaluating and incorporating new experiences and information we often cannot retrieve such knowledge being tacit. Tacit knowledge underlies many competitive capabilities and it is hard to articulate on discrete ontology structure. It is unstructured or unorganized, and therefore remains hidden. Developing generic solutions that can find the hidden knowledge is extremely complex. Moreover this will be a great challenge for the developers of semantic technologies. This work aims to explore ways to make explicit and available the tacit knowledge hidden in the collective intelligence of a collaborative environment within organizations. The environment was defined by folksonomies supported by a faceted semantic search. Vector space model which incorporates an analogy with the mathematical apparatus of quantum theory is adopted for the representation and manipulation of the meaning of folksonomy. Vector space retrieval has been proven efficiency when there isn't a data behavioural because it bears ranking algorithms involving a small number of types of elements and few operations. A solution to find what the user has in mind when posing a query could be based on "joint meaning" understood as a joint construal of the creator of the contents and the reader of the contents. The joint meaning was proposed to deal with vagueness on ontology of folksonomy indeterminacy, incompleteness and inconsistencies on collective intelligence. A proof-of concept prototype was built for collaborative environment as evolution of the actual social networks (like Facebook, LinkedIn,..) using the information visualization on a RIA application with Semantic Web techniques and technologies.
A faster exact multiprocessor schedulability test for sporadic tasks
Venue: arXiv cs.OS 2011
Year: 2011

Baker and Cirinei introduced an exact but naive algorithm, based on solving a state reachability problem in a finite automaton, to check whether sets of sporadic hard real-time tasks are schedulable on identical multiprocessor platforms. However, the algorithm suffered from poor performance due to the exponential size of the automaton relative to the size of the task set. In this paper, we successfully apply techniques developed by the formal verification community, specifically antichain algorithms, by defining and proving the correctness of a simulation relation on Baker and Cirinei's automaton. We show our improved algorithm yields dramatically improved performance for the schedulability test and opens for many further improvements.
Reserved or On-Demand Instances? A Revenue Maximization Model for Cloud Providers
Venue: arXiv cs.DC 2011
Year: 2011

We examine the problem of managing a server farm in a way that attempts to maximize the net revenue earned by a cloud provider by renting servers to customers according to a typical Platform-as-a-Service model. The Cloud provider offers its resources to two classes of customers: `premium' and `basic'. Premium customers pay upfront fees to reserve servers for a specified period of time (e.g. a year). Premium customers can submit jobs for their reserved servers at any time and pay a fee for the server-hours they use. The provider is liable to pay a penalty every time a `premium' job can not be executed due to lack of resources. On the other hand, `basic' customers are served on a best-effort basis, and pay a server-hour fee that may be higher than the one paid by premium customers. The provider incurs energy costs when running servers. Hence, it has an incentive to turn off idle servers. The question of how to choose the number of servers to allocate to each pool (basic and premium) is answered by analyzing a suitable queuing model and maximizing a revenue function. Experimental results show that the proposed scheme adapts to different traffic conditions, penalty levels, energy costs and usage fees.