OpenRaiser/Intern-Atlas huggingface dataset:
A Framework for Interactive Work Design based on Digital Work Analysis and Simulation
Venue: arXiv cs.RO 2010
Year: 2010

Due to the flexibility and adaptability of human, manual handling work is still very important in industry, especially for assembly and maintenance work. Well-designed work operation can improve work efficiency and quality; enhance safety, and lower cost. Most traditional methods for work system analysis need physical mock-up and are time consuming. Digital mockup (DMU) and digital human modeling (DHM) techniques have been developed to assist ergonomic design and evaluation for a specific worker population (e.g. 95 percentile); however, the operation adaptability and adjustability for a specific individual are not considered enough. In this study, a new framework based on motion tracking technique and digital human simulation technique is proposed for motion-time analysis of manual operations. A motion tracking system is used to track a worker's operation while he/she is conducting a manual handling work. The motion data is transferred to a simulation computer for real time digital human simulation. The data is also used for motion type recognition and analysis either online or offline for objective work efficiency evaluation and subjective work task evaluation. Methods for automatic motion recognition and analysis are presented. Constraints and limitations of the proposed method are discussed.
Linear Detrending Subsequence Matching in Time-Series Databases
Venue: arXiv cs.DB 2010
Year: 2010

Each time-series has its own linear trend, the directionality of a timeseries, and removing the linear trend is crucial to get the more intuitive matching results. Supporting the linear detrending in subsequence matching is a challenging problem due to a huge number of possible subsequences. In this paper we define this problem the linear detrending subsequence matching and propose its efficient index-based solution. To this end, we first present a notion of LD-windows (LD means linear detrending), which is obtained as follows: we eliminate the linear trend from a subsequence rather than each window itself and obtain LD-windows by dividing the subsequence into windows. Using the LD-windows we then present a lower bounding theorem for the index-based matching solution and formally prove its correctness. Based on the lower bounding theorem, we next propose the index building and subsequence matching algorithms for linear detrending subsequence matching.We finally show the superiority of our index-based solution through extensive experiments.
A Survey Paper on Recommender Systems
Venue: arXiv cs.IR 2010
Year: 2010

Recommender systems apply data mining techniques and prediction algorithms to predict users' interest on information, products and services among the tremendous amount of available items. The vast growth of information on the Internet as well as number of visitors to websites add some key challenges to recommender systems. These are: producing accurate recommendation, handling many recommendations efficiently and coping with the vast growth of number of participants in the system. Therefore, new recommender system technologies are needed that can quickly produce high quality recommendations even for huge data sets. To address these issues we have explored several collaborative filtering techniques such as the item based approach, which identify relationship between items and indirectly compute recommendations for users based on these relationships. The user based approach was also studied, it identifies relationships between users of similar tastes and computes recommendations based on these relationships. In this paper, we introduce the topic of recommender system. It provides ways to evaluate efficiency, scalability and accuracy of recommender system. The paper also analyzes different algorithms of user based and item based techniques for recommendation generation. Moreover, a simple experiment was conducted using a data mining application -Weka- to apply data mining algorithms to recommender system. We conclude by proposing our approach that might enhance the quality of recommender systems.
The F5 Algorithm in Buchberger's Style
Venue: arXiv cs.SC 2010
Year: 2010

The famous F5 algorithm for computing \gr basis was presented by Faugère in 2002. The original version of F5 is given in programming codes, so it is a bit difficult to understand. In this paper, the F5 algorithm is simplified as F5B in a Buchberger's style such that it is easy to understand and implement. In order to describe F5B, we introduce F5-reduction, which keeps the signature of labeled polynomials unchanged after reduction. The equivalence between F5 and F5B is also shown. At last, some versions of the F5 algorithm are illustrated.
Optimal Trade-Off for Succinct String Indexes
Venue: arXiv cs.DS 2010
Year: 2010

Let s be a string whose symbols are solely available through access(i), a read-only operation that probes s and returns the symbol at position i in s. Many compressed data structures for strings, trees, and graphs, require two kinds of queries on s: select(c, j), returning the position in s containing the jth occurrence of c, and rank(c, p), counting how many occurrences of c are found in the first p positions of s. We give matching upper and lower bounds for this problem, improving the lower bounds given by Golynski [Theor. Comput. Sci. 387 (2007)] [PhD thesis] and the upper bounds of Barbay et al. [SODA 2007]. We also present new results in another model, improving on Barbay et al. [SODA 2007] and matching a lower bound of Golynski [SODA 2009]. The main contribution of this paper is to introduce a general technique for proving lower bounds on succinct data structures, that is based on the access patterns of the supported operations, abstracting from the particular operations at hand. For this, it may find application to other interesting problems on succinct data structures.
Resource Allocation using Virtual Clusters
Venue: arXiv cs.DC 2010
Year: 2010

In this report we demonstrate the potential utility of resource allocation management systems that use virtual machine technology for sharing parallel computing resources among competing jobs. We formalize the resource allocation problem with a number of underlying assumptions, determine its complexity, propose several heuristic algorithms to find near-optimal solutions, and evaluate these algorithms in simulation. We find that among our algorithms one is very efficient and also leads to the best resource allocations. We then describe how our approach can be made more general by removing several of the underlying assumptions.
Cresterea securitatii sistemelor informatice si de comunicatii prin criptografia cuantica
Venue: arXiv cs.CR 2010
Year: 2010

Catch 22 of cryptography - "Before two parties can communicate in secret, they must first communicate in secret". The weakness of classical cryptographic communication systems is that secret communication can only take place after a key is communicated in secret over a totally secure communication channel. Here comes quantum key distribution which takes advantage of certain phenomena that occur at the subatomic level, so that any attempt by an enemy to obtain the bits in a key not only fails, but gets detected as well.
A Game Theoretical Approach to Modeling Information Dissemination in Social Networks
Venue: arXiv cs.GT 2010
Year: 2010

One major function of social networks (e.g., massive online social networks) is the dissemination of information such as scientific knowledge, news, and rumors. Information can be propagated by the users of the network via natural connections in written, oral or electronic form. The information passing from a sender to a receiver intrinsically involves both of them considering their self-perceived knowledge, reputation, and popularity, which further determine their decisions of whether or not to forward the information and whether or not to provide feedback. To understand such human aspects of the information dissemination, we propose a game theoretical model of the information forwarding and feedback mechanisms in a social network that take into account the personalities of the sender and the receiver (including their perceived knowledgeability, reputation, and desire for popularity) and the global characteristics of the network.
Mirage: Mitigating Illicit Inventorying in a RFID Enabled Retail Environment
Venue: arXiv cs.CR 2010
Year: 2010

Given its low dollar and maintenance cost, RFID is poised to become the enabling technology for inventory control and supply chain management. However, as an outcome of its low cost, RFID based inventory control is susceptible to pernicious security and privacy threats. A deleterious attack on such a system is corporate espionage, where attackers through illicit inventorying infer sales and restocking trends for products. In this paper, we first present plausible aftermaths of corporate espionage using real data from online sources. Second, to mitigate corporate espionage in a retail store environment, we present a simple lowcost system called Mirage. Mirage uses additional programmable low cost passive RFID tags called honeytokens to inject noise in retail store inven-torying. Using a simple history based algorithm that controls activation and de-activation of honeytokens, Mirage randomizes sales and restocking trends. We evaluate Mirage in a real warehouse environment using a commercial off-the-shelf Motorola MC9090 handheld RFID reader and over 450 Gen2 low cost RFID tags. We show that Mirage successfully flattens and randomizes sales and restocking trends while adding minimal cost to inventory control.
Rewriting Preserving Recognizability of Finite Tree Languages
Venue: arXiv cs.LO 2010
Year: 2010

We show that left-linear generalized semi-monadic TRSs effectively preserving recognizability of finite tree languages (are EPRF-TRSs). We show that reachability, joinability, and local confluence are decidable for EPRF-TRSs.
Observation-Driven Configuration of Complex Software Systems
Venue: arXiv cs.SE 2010
Year: 2010

The ever-increasing complexity of software systems makes them hard to comprehend, predict and tune due to emergent properties and non-deterministic behaviour. Complexity arises from the size of software systems and the wide variety of possible operating environments: the increasing choice of platforms and communication policies leads to ever more complex performance characteristics. In addition, software systems exhibit different behaviour under different workloads. Many software systems are designed to be configurable so that policies can be chosen to meet the needs of various stakeholders. For complex software systems it can be difficult to accurately predict the effects of a change and to know which configuration is most appropriate. This thesis demonstrates that it is useful to run automated experiments that measure a selection of system configurations. Experiments can find configurations that meet the stakeholders' needs, find interesting behavioural characteristics, and help produce predictive models of the system's behaviour. The design and use of ACT (Automated Configuration Tool) for running such experiments is described, in combination a number of search strategies for deciding on the configurations to measure. Design Of Experiments (DOE) is discussed, with emphasis on Taguchi Methods. These statistical methods have been used extensively in manufacturing, but have not previously been used for configuring software systems. The novel contribution here is an industrial case study, applying the combination of ACT and Taguchi Methods to DC-Directory, a product from Data Connection Ltd (DCL). The case study investigated the applicability of Taguchi Methods for configuring complex software systems. Taguchi Methods were found to be useful for modelling and configuring DC- Directory, making them a valuable addition to the techniques available to system administrators and developers.
Computational complexity of reconstruction and isomorphism testing for designs and line graphs
Venue: arXiv cs.CC 2010
Year: 2010

Graphs with high symmetry or regularity are the main source for experimentally hard instances of the notoriously difficult graph isomorphism problem. In this paper, we study the computational complexity of isomorphism testing for line graphs of $t$-$(v,k,λ)$ designs. For this class of highly regular graphs, we obtain a worst-case running time of $O(v^{\log v + O(1)})$ for bounded parameters $t,k,λ$. In a first step, our approach makes use of the Babai--Luks algorithm to compute canonical forms of $t$-designs. In a second step, we show that $t$-designs can be reconstructed from their line graphs in polynomial-time. The first is algebraic in nature, the second purely combinatorial. For both, profound structural knowledge in design theory is required. Our results extend earlier complexity results about isomorphism testing of graphs generated from Steiner triple systems and block designs.
A novel approach for handwritten Devnagari character recognition
Venue: arXiv cs.CV 2010
Year: 2010

In this paper a method for recognition of handwritten devanagari characters is described. Here, feature vector is constituted by accumulated directional gradient changes in different segments, number of intersections points for the character, type of spine present and type of shirorekha present in the character. One Multi-layer Perceptron with conjugate-gradient training is used to classify these feature vectors. This method is applied to a database with 1000 sample characters and the recognition rate obtained is 88.12%
Secure Transmission with Artificial Noise over Fading Channels: Achievable Rate and Optimal Power Allocation
Venue: arXiv cs.IT 2010
Year: 2010

We consider the problem of secure communication with multi-antenna transmission in fading channels. The transmitter simultaneously transmits an information bearing signal to the intended receiver and artificial noise to the eavesdroppers. We obtain an analytical closed-form expression of an achievable secrecy rate, and use it as the objective function to optimize the transmit power allocation between the information signal and the artificial noise. Our analytical and numerical results show that equal power allocation is a simple yet near optimal strategy for the case of non-colluding eavesdroppers. When the number of colluding eavesdroppers increases, more power should be used to generate the artificial noise. We also provide an upper bound on the signal-to-noise ratio (SNR) above which the achievable secrecy rate is positive and show that the bound is tight at low SNR. Furthermore, we consider the impact of imperfect channel state information (CSI) at both the transmitter and the receiver and find that it is wise to create more artificial noise to confuse the eavesdroppers than to increase the signal strength for the intended receiver if the CSI is not accurately obtained.
Randomized Rounding for Routing and Covering Problems: Experiments and Improvements
Venue: arXiv cs.DS 2010
Year: 2010

Following previous theoretical work by Srinivasan (FOCS 2001) and the first author (STACS 2006) and a first experimental evaluation on random instances (ALENEX 2009), we investigate how the recently developed different approaches to generate randomized roundings satisfying disjoint cardinality constraints behave when used in two classical algorithmic problems, namely low-congestion routing in networks and max-coverage problems in hypergraphs. We generally find that all randomized rounding algorithms work well, much better than what is guaranteed by existing theoretical work. The derandomized versions produce again significantly better rounding errors, with running times still negligible compared to the one for solving the corresponding LP. It thus seems worth preferring them over the randomized variants. The data created in these experiments lets us propose and investigate the following new ideas. For the low-congestion routing problems, we suggest to solve a second LP, which yields the same congestion, but aims at producing a solution that is easier to round. Experiments show that this reduces the rounding errors considerably, both in combination with randomized and derandomized rounding. For the max-coverage instances, we generally observe that the greedy heuristics also performs very good. We develop a strengthened method of derandomized rounding, and a simple greedy/rounding hybrid approach using greedy and LP-based rounding elements, and observe that both these improvements yield again better solutions than both earlier approaches on their own. For unit disk max-domination, we also develop a PTAS. Contrary to all other algorithms investigated, it performs not much better in experiments than in theory; thus, unless extremely good solutions are to be obtained with huge computational resources, greedy, LP-based rounding or hybrid approaches are preferable.
Quasi-Cyclic Asymptotically Regular LDPC Codes
Venue: arXiv cs.IT 2010
Year: 2010

Families of "asymptotically regular" LDPC block code ensembles can be formed by terminating (J,K)-regular protograph-based LDPC convolutional codes. By varying the termination length, we obtain a large selection of LDPC block code ensembles with varying code rates, minimum distance that grows linearly with block length, and capacity approaching iterative decoding thresholds, despite the fact that the terminated ensembles are almost regular. In this paper, we investigate the properties of the quasi-cyclic (QC) members of such an ensemble. We show that an upper bound on the minimum Hamming distance of members of the QC sub-ensemble can be improved by careful choice of the component protographs used in the code construction. Further, we show that the upper bound on the minimum distance can be improved by using arrays of circulants in a graph cover of the protograph.
Perturbed Hankel Determinants: Applications to the Information Theory of MIMO Wireless Communications
Venue: arXiv cs.IT 2010
Year: 2010

In this paper we compute two important information-theoretic quantities which arise in the application of multiple-input multiple-output (MIMO) antenna wireless communication systems: the distribution of the mutual information of multi-antenna Gaussian channels, and the Gallager random coding upper bound on the error probability achievable by finite-length channel codes. It turns out that the mathematical problem underpinning both quantities is the computation of certain Hankel determinants generated by deformed versions of classical weight functions. For single-user MIMO systems, it is a deformed Laguerre weight, whereas for multi-user MIMO systems it is a deformed Jacobi weight. We apply two different methods to characterize each of these Hankel determinants. First, we employ the ladder operators of the corresponding monic orthogonal polynomials to give an exact characterization of the Hankel determinants in terms of Painlevé differential equations. This turns out to be a Painlevé V for the single-user MIMO scenario and a Painlevé VI for the multi user scenario. We then employ Coulomb fluid methods to derive new closed-form approximations for the Hankel determinants which, although formally valid for large matrix dimensions, are shown to give accurate results for both the MIMO mutual information distribution and the error exponent even when the matrix dimensions are small. Focusing on the single-user mutual information distribution, we then employ both the exact Painlevé representation and the Coulomb fluid approximation to yield deeper insights into the scaling behavior in terms of the number of antennas and signal-to-noise ratio. Among other things, these results allow us to study the asymptotic Gaussianity of the distribution as the number of antennas increase, and to explicitly compute the correction terms to the mean, variance, and higher order cumulants.
Quotient Based Multiresolution Image Fusion of Thermal and Visual Images Using Daubechies Wavelet Transform for Human Face Recognition
Venue: arXiv cs.CV 2010
Year: 2010

This paper investigates the multiresolution level-1 and level-2 Quotient based Fusion of thermal and visual images. In the proposed system, the method-1 namely "Decompose then Quotient Fuse Level-1" and the method-2 namely "Decompose-Reconstruct then Quotient Fuse Level-2" both work on wavelet transformations of the visual and thermal face images. The wavelet transform is well-suited to manage different image resolution and allows the image decomposition in different kinds of coefficients, while preserving the image information without any loss. This approach is based on a definition of an illumination invariant signature image which enables an analytic generation of the image space with varying illumination. The quotient fused images are passed through Principal Component Analysis (PCA) for dimension reduction and then those images are classified using a multi-layer perceptron (MLP). The performances of both the methods have been evaluated using OTCBVS and IRIS databases. All the different classes have been tested separately, among them the maximum recognition result is 100%.
Classification of Log-Polar-Visual Eigenfaces using Multilayer Perceptron
Venue: arXiv cs.CV 2010
Year: 2010

In this paper we present a simple novel approach to tackle the challenges of scaling and rotation of face images in face recognition. The proposed approach registers the training and testing visual face images by log-polar transformation, which is capable to handle complicacies introduced by scaling and rotation. Log-polar images are projected into eigenspace and finally classified using an improved multi-layer perceptron. In the experiments we have used ORL face database and Object Tracking and Classification Beyond Visible Spectrum (OTCBVS) database for visual face images. Experimental results show that the proposed approach significantly improves the recognition performances from visual to log-polar-visual face images. In case of ORL face database, recognition rate for visual face images is 89.5% and that is increased to 97.5% for log-polar-visual face images whereas for OTCBVS face database recognition rate for visual images is 87.84% and 96.36% for log-polar-visual face images.
Local search for stable marriage problems with ties and incomplete lists
Venue: arXiv cs.AI 2010
Year: 2010

The stable marriage problem has a wide variety of practical applications, ranging from matching resident doctors to hospitals, to matching students to schools, or more generally to any two-sided market. We consider a useful variation of the stable marriage problem, where the men and women express their preferences using a preference list with ties over a subset of the members of the other sex. Matchings are permitted only with people who appear in these preference lists. In this setting, we study the problem of finding a stable matching that marries as many people as possible. Stability is an envy-free notion: no man and woman who are not married to each other would both prefer each other to their partners or to being single. This problem is NP-hard. We tackle this problem using local search, exploiting properties of the problem to reduce the size of the neighborhood and to make local moves efficiently. Experimental results show that this approach is able to solve large problems, quickly returning stable matchings of large and often optimal size.