OpenRaiser/Intern-Atlas huggingface dataset:
On MMSE estimation from quantized observations in the nonasymptotic regime
Venue: arXiv cs.IT 2015
Year: 2015

This paper studies MMSE estimation on the basis of quantized noisy observations. It presents nonasymptotic bounds on MMSE regret due to quantization for two settings: (1) estimation of a scalar random variable given a quantized vector of $n$ conditionally independent observations, and (2) estimation of a $p$-dimensional random vector given a quantized vector of $n$ observations (not necessarily independent) when the full MMSE estimator has a subgaussian concentration property.
Edge Detection Based on Global and Local Parameters of the Image
Venue: arXiv cs.CV 2015
Year: 2015

This paper presents an edge detection method based on global and local parameters of the image, which produces satisfactory results on the edge detection of complex images and has a simple structure for execution. The local and global parameters of the image are arithmetic means and standard deviations, the former acquired from a three sized window representing five pixels, the latter acquired from the entire row or column. We obtain the differences of grayscale intensities between two adjacent pixels and the sum of the modulus of these differences from the horizontal and vertical scans of the image. Using these obtained values, we calculate the local and global parameters. After the gathering of the local and global parameters, we compare each sum of the modulus of differences with its own local and global parameter. In the case of the comparison is true, the consecutive pixel to the modulus sum of differences index is marked as an edge. We present the results of the tests with grayscale images using different parameters and discuss the advantages and disadvantages of each parameter value and algorithm structure chosen on the edge processing. There is a comparison of results between this papers detector and Canny, where we evaluate the quality of the presented detector.
Quasiperiodicity and non-computability in tilings
Venue: arXiv cs.DM 2015
Year: 2015

We study tilings of the plane that combine strong properties of different nature: combinatorial and algorithmic. We prove existence of a tile set that accepts only quasiperiodic and non-recursive tilings. Our construction is based on the fixed point construction; we improve this general technique and make it enforce the property of local regularity of tilings needed for quasiperiodicity. We prove also a stronger result: any effectively closed set can be recursively transformed into a tile set so that the Turing degrees of the resulted tilings consists exactly of the upper cone based on the Turing degrees of the later.
From End-User's Requirements to Web Services Retrieval: A Semantic and Intention-Driven Approach
Venue: arXiv cs.SE 2015
Year: 2015

In this paper, we present SATIS, a framework to derive Web Service specifications from end-user's requirements in order to opera-tionalise business processes in the context of a specific application domain. The aim of SATIS is to provide to neuroscientists, which are not familiar with computer science, a complete solution to easily find a set of Web Services to implement an image processing pipeline. More precisely, our framework offers the capability to capture high-level end-user's requirements in an iterative and incremental way and to turn them into queries to retrieve Web Services description. The whole framework relies on reusable and combinable elements which can be shared out by a community of users sharing some interest or problems for a given topic. In our approach, we adopt Web semantic languages and models as a unified framework to deal with end-user's requirements and Web Service descriptions in order to take advantage of their reasoning and traceability capabilities.
Collectively Embedding Multi-Relational Data for Predicting User Preferences
Venue: arXiv cs.LG 2015
Year: 2015

Matrix factorization has found incredible success and widespread application as a collaborative filtering based approach to recommendations. Unfortunately, incorporating additional sources of evidence, especially ones that are incomplete and noisy, is quite difficult to achieve in such models, however, is often crucial for obtaining further gains in accuracy. For example, additional information about businesses from reviews, categories, and attributes should be leveraged for predicting user preferences, even though this information is often inaccurate and partially-observed. Instead of creating customized methods that are specific to each type of evidences, in this paper we present a generic approach to factorization of relational data that collectively models all the relations in the database. By learning a set of embeddings that are shared across all the relations, the model is able to incorporate observed information from all the relations, while also predicting all the relations of interest. Our evaluation on multiple Amazon and Yelp datasets demonstrates effective utilization of additional information for held-out preference prediction, but further, we present accurate models even for the cold-starting businesses and products for which we do not observe any ratings or reviews. We also illustrate the capability of the model in imputing missing information and jointly visualizing words, categories, and attribute factors.
Interactive Communication with Unknown Noise Rate
Venue: arXiv cs.DS 2015
Year: 2015

Alice and Bob want to run a protocol over a noisy channel, where a certain number of bits are flipped adversarially. Several results take a protocol requiring $L$ bits of noise-free communication and make it robust over such a channel. In a recent breakthrough result, Haeupler described an algorithm that sends a number of bits that is conjectured to be near optimal in such a model. However, his algorithm critically requires $a \ priori$ knowledge of the number of bits that will be flipped by the adversary. We describe an algorithm requiring no such knowledge. If an adversary flips $T$ bits, our algorithm sends $L + O\left(\sqrt{L(T+1)\log L} + T\right)$ bits in expectation and succeeds with high probability in $L$. It does so without any $a \ priori$ knowledge of $T$. Assuming a conjectured lower bound by Haeupler, our result is optimal up to logarithmic factors. Our algorithm critically relies on the assumption of a private channel. We show that privacy is necessary when the amount of noise is unknown.
Use of Ensembles of Fourier Spectra in Capturing Recurrent Concepts in Data Streams
Venue: arXiv cs.AI 2015
Year: 2015

In this research, we apply ensembles of Fourier encoded spectra to capture and mine recurring concepts in a data stream environment. Previous research showed that compact versions of Decision Trees can be obtained by applying the Discrete Fourier Transform to accurately capture recurrent concepts in a data stream. However, in highly volatile environments where new concepts emerge often, the approach of encoding each concept in a separate spectrum is no longer viable due to memory overload and thus in this research we present an ensemble approach that addresses this problem. Our empirical results on real world data and synthetic data exhibiting varying degrees of recurrence reveal that the ensemble approach outperforms the single spectrum approach in terms of classification accuracy, memory and execution time.
Logical Conditional Preference Theories
Venue: arXiv cs.AI 2015
Year: 2015

CP-nets represent the dominant existing framework for expressing qualitative conditional preferences between alternatives, and are used in a variety of areas including constraint solving. Over the last fifteen years, a significant literature has developed exploring semantics, algorithms, implementation and use of CP-nets. This paper introduces a comprehensive new framework for conditional preferences: logical conditional preference theories (LCP theories). To express preferences, the user specifies arbitrary (constraint) Datalog programs over a binary ordering relation on outcomes. We show how LCP theories unify and generalize existing conditional preference proposals, and leverage the rich semantic, algorithmic and implementation frameworks of Datalog.
3-D Velocity Regulation for Nonholonomic Source Seeking Without Position Measurement
Venue: arXiv cs.RO 2015
Year: 2015

We consider a three-dimensional problem of steering a nonholonomic vehicle to seek an unknown source of a spatially distributed signal field without any position measurement. In the literature, there exists an extremum seeking-based strategy under a constant forward velocity and tunable pitch and yaw velocities. Obviously, the vehicle with a constant forward velocity may exhibit certain overshoots in the seeking process and can not slow down even it approaches the source. To resolve this undesired behavior, this paper proposes a regulation strategy for the forward velocity along with the pitch and yaw velocities. Under such a strategy, the vehicle slows down near the source and stays within a small area as if it comes to a full stop, and controllers for angular velocities become succinct. We prove the local exponential convergence via the averaging technique. Finally, the theoretical results are illustrated with simulations.
Searching for a Compressed Polyline with a Minimum Number of Vertices
Venue: arXiv cs.CG 2015
Year: 2015

There are many practical applications that require simplification of polylines. Some of the goals are to reduce the amount of information necessary to store, improve processing time, or simplify editing. The simplification is usually done by removing some of the vertices, making the resultant polyline go through a subset of the source polyline vertices. However, such approaches do not necessarily produce a new polyline with the minimum number of vertices. The approximate solution to find a polyline, within a specified tolerance, with the minimum number of vertices is described in this paper.
Adaptive Locally Affine-Invariant Shape Matching
Venue: arXiv cs.CV 2015
Year: 2015

Matching deformable objects using their shapes is an important problem in computer vision since shape is perhaps the most distinguishable characteristic of an object. The problem is difficult due to many factors such as intra-class variations, local deformations, articulations, viewpoint changes and missed and extraneous contour portions due to errors in shape extraction. While small local deformations has been handled in the literature by allowing some leeway in the matching of individual contour points via methods such as Chamfer distance and Hausdorff distance, handling more severe deformations and articulations has been done by applying local geometric corrections such as similarity or affine. However, determining which portions of the shape should be used for the geometric corrections is very hard, although some methods have been tried. In this paper, we address this problem by an efficient search for the group of contour segments to be clustered together for a geometric correction using Dynamic Programming by essentially searching for the segmentations of two shapes that lead to the best matching between them. At the same time, we allow portions of the contours to remain unmatched to handle missing and extraneous contour portions. Experiments indicate that our method outperforms other algorithms, especially when the shapes to be matched are more complex.
ROBUS: Fair Cache Allocation for Multi-tenant Data-parallel Workloads
Venue: arXiv cs.DC 2015
Year: 2015

Systems for processing big data---e.g., Hadoop, Spark, and massively parallel databases---need to run workloads on behalf of multiple tenants simultaneously. The abundant disk-based storage in these systems is usually complemented by a smaller, but much faster, {\em cache}. Cache is a precious resource: Tenants who get to use cache can see two orders of magnitude performance improvement. Cache is also a limited and hence shared resource: Unlike a resource like a CPU core which can be used by only one tenant at a time, a cached data item can be accessed by multiple tenants at the same time. Cache, therefore, has to be shared by a multi-tenancy-aware policy across tenants, each having a unique set of priorities and workload characteristics. In this paper, we develop cache allocation strategies that speed up the overall workload while being {\em fair} to each tenant. We build a novel fairness model targeted at the shared resource setting that incorporates not only the more standard concepts of Pareto-efficiency and sharing incentive, but also define envy freeness via the notion of {\em core} from cooperative game theory. Our cache management platform, ROBUS, uses randomization over small time batches, and we develop a proportionally fair allocation mechanism that satisfies the core property in expectation. We show that this algorithm and related fair algorithms can be approximated to arbitrary precision in polynomial time. We evaluate these algorithms on a ROBUS prototype implemented on Spark with RDD store used as cache. Our evaluation on a synthetically generated industry-standard workload shows that our algorithms provide a speedup close to performance optimal algorithms while guaranteeing fairness across tenants.
Collaborative Real Time Coding or How to Avoid the Dreaded Merge
Venue: arXiv cs.SE 2015
Year: 2015

Software engineers who collaborate to develop software in teams often have to manually merge changes they made to a module (e.g. a class), because the change conflicts with one that has just been made by another engineer to the same or another module (e.g. a supplier class). This is due to the fact that engineers edit code separately, and loosely coordinate their work via a source control or a software configuration management system (SCM). This work proposes to eliminate almost all the need to manually merge a recent change, by proposing a Collaborative Real Time Coding approach. In this approach, valid changes to the code are seen by others in real time, but intermediate changes (that cause the code not to compile) result in blocking other engineers from making changes related to the entity (e.g. method) being modified, while allowing them to work on most of the system. The subject of collaborative real time editing systems has been studied for the past 20 years. Research in this field has mostly concentrated on collaborative textual and graphical editing. In this work we address the challenges involved in designing a collaborative real time coding system, as well as present the major differences when compared to collaborative editing of plain text. We then present a prototype plug in for the Eclipse Integrated Development Environment (IDE) that allows for a collaborative coding to take place.
Implementing a Case Management Modeling and Notation (CMMN) System using a Content Management Interoperability Services (CMIS) compliant repository
Venue: arXiv cs.SE 2015
Year: 2015

This paper describes how a Case Management Modeling and Notation (CMMN) implementation can use Content Management Interoperability Services (CMIS) to implement the CMMN information model. The interaction between CMMN and CMIS is described in detail, and two implementation alternatives are presented. An integration alternative where any external CMIS repository is used. This alternative is useful to process technology vendors looking to integrate with CMIS compliant repositories. An embedded alternative where a CMIS repository is embedded within the CMMN engine. This alternative is useful to content management vendors implementing CMMN. In both alternatives a CMIS folder is used as the case file containing the case instance data. The CMIS repository can also be used to store the CMMN models to take advantage of CMIS versioning and meta-data. Extensive Java pseudocode is provided as an example of how a CMMN implementation can use a CMIS repository to implement the CMMN information model. No extensions to CMIS are needed, and only minor extensions to CMMN are proposed.
A Formal Approach to Network/Distributed Systems Complex Testing
Venue: arXiv cs.DC 2015
Year: 2015

Deployment of network/distributed systems sets high requirements for procedures, tools and approaches for the complex testing of these systems. This work provides a survey of testing activities with regard to these systems based on standards and actual practices for both software-based and distribution (network) aspects. On the basis of this survey, we determine formal testing procedures/processes which cover these aspects, but which are not contrary to both aspects. The next step, based on the analysis of the implementation phase of System Development Life Cycle, determines a formal model for these processes
A bi-convex optimization problem to compute Nash equilibrium in n-player games and an algorithm
Venue: arXiv cs.GT 2015
Year: 2015

In this paper we present optimization problems with biconvex objective function and linear constraints such that the set of global minima of the optimization problems is the same as the set of Nash equilibria of a n-player general-sum normal form game. We further show that the objective function is an invex function and consider a projected gradient descent algorithm. We prove that the projected gradient descent scheme converges to a partial optimum of the objective function. We also present simulation results on certain test cases showing convergence to a Nash equilibrium strategy.
Monitoring Extreme-scale Lustre Toolkit
Venue: arXiv cs.DC 2015
Year: 2015

We discuss the design and ongoing development of the Monitoring Extreme-scale Lustre Toolkit (MELT), a unified Lustre performance monitoring and analysis infrastructure that provides continuous, low-overhead summary information on the health and performance of Lustre, as well as on-demand, in- depth problem diagnosis and root-cause analysis. The MELT infrastructure leverages a distributed overlay network to enable monitoring of center-wide Lustre filesystems where clients are located across many network domains. We preview interactive command-line utilities that help administrators and users to observe Lustre performance at various levels of resolution, from individual servers or clients to whole filesystems, including job-level reporting. Finally, we discuss our future plans for automating the root-cause analysis of common Lustre performance problems.
Index Coding and Network Coding via Rank Minimization
Venue: arXiv cs.IT 2015
Year: 2015

Index codes reduce the number of bits broadcast by a wireless transmitter to a number of receivers with different demands and with side information. It is known that the problem of finding optimal linear index codes is NP-hard. We investigate the performance of different heuristics based on rank minimization and matrix completion methods, such as alternating projections and alternating minimization, for constructing linear index codes over the reals. As a summary of our results, the alternating projections method gives the best results in terms of minimizing the number of broadcast bits and convergence rate and leads to up to 13% savings in average communication cost compared to graph coloring algorithms studied in the literature. Moreover, we describe how the proposed methods can be used to construct linear network codes for non-multicast networks. Our computer code is available online.
Fast Dictionary Matching for Content-based Image Retrieval
Venue: arXiv cs.CV 2015
Year: 2015

This paper describes a method for searching for common sets of descriptors between collections of images. The presented method operates on local interest keypoints, which are generated using the SURF algorithm. The use of a dictionary of descriptors allowed achieving good performance of the content-based image retrieval. The method can be used to initially determine a set of similar pairs of keypoints between images. For this purpose, we use a certain level of tolerance between values of descriptors, as values of feature descriptors are almost never equal but similar between different images. After that, the method compares the structure of rotation and location of interest points in one image with the point structure in other images. Thus, we were able to find similar areas in images and determine the level of similarity between them, even when images contain different scenes.
Multi-layer Architecture For Storing Visual Data Based on WCF and Microsoft SQL Server Database
Venue: arXiv cs.DB 2015
Year: 2015

In this paper we present a novel architecture for storing visual data. Effective storing, browsing and searching collections of images is one of the most important challenges of computer science. The design of architecture for storing such data requires a set of tools and frameworks such as SQL database management systems and service-oriented frameworks. The proposed solution is based on a multi-layer architecture, which allows to replace any component without recompilation of other components. The approach contains five components, i.e. Model, Base Engine, Concrete Engine, CBIR service and Presentation. They were based on two well-known design patterns: Dependency Injection and Inverse of Control. For experimental purposes we implemented the SURF local interest point detector as a feature extractor and $K$-means clustering as indexer. The presented architecture is intended for content-based retrieval systems simulation purposes as well as for real-world CBIR tasks.
Autonomy and Reliability of Continuous Active Learning for Technology-Assisted Review
Venue: arXiv cs.IR 2015
Year: 2015

We enhance the autonomy of the continuous active learning method shown by Cormack and Grossman (SIGIR 2014) to be effective for technology-assisted review, in which documents from a collection are retrieved and reviewed, using relevance feedback, until substantially all of the relevant documents have been reviewed. Autonomy is enhanced through the elimination of topic-specific and dataset-specific tuning parameters, so that the sole input required by the user is, at the outset, a short query, topic description, or single relevant document; and, throughout the review, ongoing relevance assessments of the retrieved documents. We show that our enhancements consistently yield superior results to Cormack and Grossman's version of continuous active learning, and other methods, not only on average, but on the vast majority of topics from four separate sets of tasks: the legal datasets examined by Cormack and Grossman, the Reuters RCV1-v2 subject categories, the TREC 6 AdHoc task, and the construction of the TREC 2002 filtering test collection.
A Refutation of the Clique-Based P=NP Proofs of LaPlante and Tamta-Pande-Dhami
Venue: arXiv cs.CC 2015
Year: 2015

In this work, we critique two papers, "A Polynomial-Time Solution to the Clique Problem" by Tamta, Pande, and Dhami, and "A Polynomial-Time Algorithm For Solving Clique Problems" by LaPlante. We summarize and analyze both papers, noting that the algorithms presented in both papers are flawed. We conclude that neither author has successfully established that P = NP.
Detection and Recognition of Malaysian Special License Plate Based On SIFT Features
Venue: arXiv cs.CV 2015
Year: 2015

Automated car license plate recognition systems are developed and applied for purpose of facilitating the surveillance, law enforcement, access control and intelligent transportation monitoring with least human intervention. In this paper, an algorithm based on SIFT feature points clustering and matching is proposed to address the issue of recognizing Malaysian special plates. These special plates do not follow the format of standard car plates as they may contain italic, cursive, connected and small letters. The algorithm is tested with 150 Malaysian special plate images under different environment and the promising experimental results demonstrate that the proposed algorithm is relatively robust.