Search

An automatic computer vision algorithm that detects individual paper fibres from an image, assesses the possibility of grasping the detected fibres with microgrippers and detects the suitable grasping points is presented. The goal of the algorithm is to enable automatic fibre manipulation for mechanical characterisation, which has traditionally been slow manual work. The algorithm classifies the objects in images based on their morphology, and detects the proper grasp points from the individual fibres by applying given geometrical constraints. The authors test the ability of the algorithm to detect the individual fibres with 35 images containing more than 500 fibres in total, and also compare the graspability analysis and the calculated grasp points with the results of an experienced human operator with 15 images that contain a total of almost 200 fibres. The detection results are outstanding, with fewer than 1% of fibres missed. The graspability analysis gives sensitivity of 0.83 and specificity of 0.92, and the average distance between the grasp points of the human and the algorithm is 220 µm. Also, the choices made by the algorithm are much more consistent than the human choices. [ABSTRACT FROM AUTHOR]

Nowadays, with the development of computer science and technology, computer intelligent algorithms are more and more widely used in various industries. Every calculation formula in the computer intelligent algorithm has systematic logic and singleness, in order to expound the dynamic algorithm of football training optimized by the computer intelligent algorithm in detail. In this paper, the monitoring system using the computer intelligent algorithm can dynamically observe people or objects and systematically analyze them. This paper mainly studies the research of a football training dynamic monitoring system based on the computer intelligent algorithm and the design and optimization of the computer intelligent dynamic monitoring system in football training. Finally, the overall composition of the computer intelligent dynamic monitoring system and the application of the optimized computer intelligent dynamic monitoring system to the analysis of sample data are studied. [ABSTRACT FROM AUTHOR]

In many applications, top-k query is an important operation to return a set of interesting points in a potentially huge data space. It is analyzed in this paper that the existing algorithms cannot process top- k query on massive data efficiently. This paper proposes a novel table-scan-based T2S algorithm to efficiently compute top-k results on massive data. T2S first constructs the presorted table, whose tuples are arranged in the order of the round-robin retrieval on the sorted lists. T2S maintains only fixed number of tuples to compute results. The early termination checking for T2S is presented in this paper, along with the analysis of scan depth. The selective retrieval is devised to skip the tuples in the presorted table which are not top-k results. The theoretical analysis proves that selective retrieval can reduce the number of the retrieved tuples significantly. The construction and incremental-update/batch-processing methods for the used structures are proposed in this paper. The extensive experimental results, conducted on synthetic and real-life data sets, show that T2S has a significant advantage over the existing algorithms. [ABSTRACT FROM AUTHOR]

: In computational science literature including, e.g., bioinformatics, computational statistics or machine learning, most published articles are devoted to the development of “new methods”, while comparison studies are generally appreciated by readers but surprisingly given poor consideration by many journals. This paper stresses the importance of neutral comparison studies for the objective evaluation of existing methods and the establishment of standards by drawing parallels with clinical research. The goal of the paper is twofold. Firstly, we present a survey of recent computational papers on supervised classification published in seven high-ranking computational science journals. The aim is to provide an up-to-date picture of current scientific practice with respect to the comparison of methods in both articles presenting new methods and articles focusing on the comparison study itself. Secondly, based on the results of our survey we critically discuss the necessity, impact and limitations of neutral comparison studies in computational sciences. We define three reasonable criteria a comparison study has to fulfill in order to be considered as neutral, and explicate general considerations on the individual components of a “tidy neutral comparison study”. R codes for completely replicating our statistical analyses and figures are available from the companion website http://www.ibe.med.uni-muenchen.de/organisation/mitarbeiter/020_professuren/boulesteix/plea2013. [ABSTRACT FROM AUTHOR]

Given a distributed computation and a global predicate, predicate detection involves determining whether there exists at least one consistent cut (or global state) of the computation that satisfies the predicate. On the other hand, computation slicing is concerned with computing the smallest subcomputation (with the least number of consistent cuts) that contains all consistent cuts of the computation satisfying the predicate. In this paper, we investigate the relationship between predicate detection and computation slicing and show that the two problems are actually equivalent. Specifically, given an algorithm to detect a predicate b in a computation C, we derive an algorithm to compute the slice of C with respect to b. The time complexity of the (derived) slicing algorithm is O(n∣E∣T), where n is the number of processes, E is the set of events, and O(T) is the time complexity of the detection algorithm. We discuss how the "equivalence" result of this paper can be utilized to derive a faster algorithm for solving the genera/predicate detection problem in many cases. Slicing algorithms described in our earlier papers are all offline in nature. In this paper, we also present two online algorithms for computing the slice. The first algorithm can be used to compute the slice for a general predicate. Its amortized time complexity is O(n(c+n)T) per event, where c is the average concurrency in the computation and O(T) is the time complexity of the detection algorithm. The second algorithm can be used to compute the slice for a regular predicate. Its amortized time complexity is only O(n2) per event. [ABSTRACT FROM AUTHOR]

The object deployment of a distributed software has a great impact on its performance. In this paper an analytical model for performance evaluation of different object deployments, is presented. The key advantage of the proposed model over the traditional Queuing Network models is the usefulness in the deployment optimization when the search space is huge and automatic instantiation of Queuing performance models corresponding to an object deployment is costly. Since our model produces an optimal deployment corresponding to each input load separately, the runtime behavior of the software corresponding to each input load should be profiled using simulation first. In this paper a translation scheme for generating the simulate-able Labeled Transition Systems (LTS) from scenarios is also presented. Moreover, two deployment algorithms (a GA-based and an INLP-based) are implemented and the results are compared. [ABSTRACT FROM AUTHOR]

In this paper, we develop two automated authorship attribution schemes, one based on Multiple Discriminant Analysis (MDA) and the other based on a Support Vector Machine (SVM). The classification features we exploit are based on word frequencies in the text. We adopt an approach of preprocessing each text by stripping it of all characters except a-z and space. This is in order to increase the portability of the software to different types of texts. We test the methodology on a corpus of undisputed English texts, and use leave-one-out cross validation to demonstrate classification accuracies in excess of 90%. We further test our methods on the Federalist Papers, which have a partly disputed authorship and a fair degree of scholarly consensus. And finally, we apply our methodology to the question of the authorship of the Letter to the Hebrews by comparing it against a number of original Greek texts of known authorship. These tests identify where some of the limitations lie, motivating a number of open questions for future work. An open source implementation of our methodology is freely available for use at https://github.com/matthewberryman/author-detection. [ABSTRACT FROM AUTHOR]

Real social networks contain many communities, where members within each community are densely connected with each other, while they are sparsely connected with the members outside of the community. Since each member can join multiple communities simultaneously, communities in social networks are usually overlapping with each other. How to efficiently and effectively identify overlapping communities in a large social network becomes a fundamental problem in the big data era. Most existing studies on community finding focused on non-overlapping communities based on several well-known community fitness metrics. However, recent investigations have shown that these fitness metrics may suffer free rider and separation effects where the overlapping region of two communities always belongs to the denser one, rather to both of them. In this paper, we study the overlapping community detection problem in social networks that not only takes the quality of the found overlapping communities but also incorporate both free rider and separation effects on the found communities into consideration. Specifically, in this paper, we first propose a novel community fitness metric - triangle based fitness metric, for overlapping community detection that can minimize the free rider and separation effects on found overlapping communities, and show that the problem is NP-hard. We then propose an efficient yet scalable algorithm for the problem that can deliver a feasible solution. We finally validate the effectiveness of the proposed fitness metric and evaluate the performance of the proposed algorithm, through conducting extensive experiments on real-world datasets with over 100 million vertices and edges. Experimental results demonstrate that the proposed algorithm is very promising. [ABSTRACT FROM AUTHOR]

The problem of counting triangles in graphs has been well studied in the literature. However, all existing algorithms, exact or approximate, spend at least linear time in the size of the graph (except a recent theoretical result), which can be prohibitive on today's large graphs. Nevertheless, we observe that the ideas in many existing triangle counting algorithms can be coupled with random sampling to yield potentially sublinear-time algorithms that return an approximation of the triangle count without looking at the whole graph. This paper makes these random sampling algorithms more explicit, and presents an experimental and analytical comparison of different approaches, identifying the best performers among a number of candidates. [ABSTRACT FROM AUTHOR]

The commencement of decryption process of Advanced Encryption Standard (AES) algorithm is dependent on availability of the last round key. In this paper, we propose a look-ahead technique for increasing the speed of implementation of AES key schedule using which the last round key can be made available fast. The other round keys can also be computed in a parallel path using the proposed technique. Applications such as key search engines need to be agile to key changes for decrypting given encrypted messages using all the keys in the available key space so that fast decryption is possible. The FPGA implementation results using Xilinx XC5VLX85 are also provided. [ABSTRACT FROM AUTHOR]

Science is conducted collaboratively, often requiring the sharing of knowledge about computational experiments. When experiments include only datasets, they can be shared using Uniform Resource Identifiers (URIs) or Digital Object Identifiers (DOIs). An experiment, however, seldom includes only datasets, but more often includes software, its past execution, provenance, and associated documentation. The Research Object has recently emerged as a comprehensive and systematic method for aggregation and identification of diverse elements of computational experiments. While a necessary method, mere aggregation is not sufficient for the sharing of computational experiments. Other users must be able to easily recompute on these shared research objects. Computational provenance is often the key to enable such reuse. In this paper, we show how reusable research objects can utilize provenance to correctly repeat a previous reference execution, to construct a subset of a research object for partial reuse, and to reuse existing contents of a research object for modified reuse. We describe two methods to summarize provenance that aid in understanding the contents and past executions of a research object. The first method obtains a process-view by collapsing low-level system information, and the second method obtains a summary graph by grouping related nodes and edges with the goal to obtain a graph view similar to application workflow. Through detailed experiments, we show the efficacy and efficiency of our algorithms. [ABSTRACT FROM AUTHOR]

Copyright of Revista Virtual Universidad Católica del Norte is the property of Revista Virtual Universidad Catolica del Norte and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)

Load balancing is the major benefit of any distributed system. To facilitate this advantage, task duplication and migration methodologies are employed. As this paper deals with dependent tasks (DAG), we used duplication. Task duplication reduces the overall schedule length of DAG along-with load balancing. This paper proposes a new task duplication algorithm at the time of tasks assignment on various processors. With the intention of conducting proposed algorithm performance computation; simulation has been done on the Netbeans IDE. The mesh topology of a distributed system is simulated at this juncture. For task duplication, overall schedule length of DAG is the main parameter that decides the performance of a proposed duplication algorithm. After obtaining the results we compared our performance with arbitrary task assignment, CAWF and HEFT-TD algorithms. Additionally, we also compared the complexity of the proposed algorithm with the Duplication Based Bottom Up scheduling (DBUS) and Heterogeneous Earliest Finish Time with Task Duplication (HEFT-TD). [ABSTRACT FROM AUTHOR]

Semantic Relatedness computation has been a fundamental as well as an essential step for domains like Information Retrieval, Natural Language Processing, Semantic Web, etc. Many techniques for Semantic Relatedness calculation in a single domain have been proposed. However, these techniques give inappropriate results for the massive multidomain dataset because they provide a relation between concepts across different domains, which are not related to each other. Their similarities should be minimized. In this paper, a novel method, "modified Balanced Mutual Information(MBMI)," to calculate the semantic relatedness of multidomain data has been proposed. In this proposed method, to get semantic relatedness, concepts are extracted, followed by a fuzzy vector from a given corpus. A comparison of the proposed method with other existing methods has been performed. We used medical and computer science articles as our dataset. The proposed method shows better results for multidomain data. [ABSTRACT FROM AUTHOR]

The generation of SAT instances is an important issue in computer science, and it is useful for researchers to verify the effectiveness of SAT solvers. Addressing this issue could inspire researchers to propose new search strategies. SAT problems exist in various real-world applications, some of which have more than one solution. However, although several algorithms for generating random SAT instances have been proposed, few can be used to generate hard instances that have multiple predefined solutions. In this paper, we propose the KHidden-M algorithm to generate SAT instances with multiple predefined solutions that could be hard to solve by the local search strategy when the number of predefined solutions is small enough and the Hamming distance between them is not less than half of the solution length. Specifically, first, we generate an SAT instance that is satisfied by all of the predefined solutions. Next, if the generated SAT instance does not satisfy the hardness condition, then a strategy will be conducted to adjust clauses through multiple iterations to improve the hardness of the whole instance. We propose three strategies to generate the SAT instance in the first part. The first strategy is called the random strategy, which randomly generates clauses that are satisfied by all of the predefined solutions. The other two strategies are called the estimating strategy and greedy strategy, and using them, we attempt to generate an instance that directly satisfies or is closer to the hardness condition for the local search strategy. We employ two SAT solvers (i.e., WalkSAT and Kissat) to investigate the hardness of the SAT instances generated by our algorithm in the experiments. The experimental results show the effectiveness of the random, estimating and greedy strategies. Compared to the state-of-the-art algorithm for generating SAT instances with predefined solutions, namely, M-hidden, our algorithm could be more effective in generating hard SAT instances. [ABSTRACT FROM AUTHOR]

Segmentation of handwritten text into lines, words and characters is one of the important steps in the handwritten text recognition process. In this paper, we propose a float fill algorithm for segmentation of unconstrained Devanagari text into words. Here, a text image is directly segmented into individual words. Rectangular boundaries are drawn around the words and horizontal lines are detected with template matching. A mask is designed for detecting the horizontal line and is applied to each word from left to right and top to bottom of the document. Header lines are removed for character separation. A new segment code features are extracted for each character. In this paper, we present the results of multiple classifier combination for offline handwritten Devanagari characters. The use of regular expressions in handwritten characters is a novel concept and they are defined in a manner so that they can become more robust to noise. We have achieved an accuracy of 94% for word level segmentation, 95% for coarse classification and 85% for fine classification of character recognition. On experimentation with a dataset of 5000 samples of characters, the overall recognition rate observed is 95% as we considered top five choice results. The proposed combined classifier can be applied to handwritten character recognition of any other language like English, Chinese, Arabic, etc. and can recognize the characters with same accuracy.18 For printed characters we have achieved accuracy of 100%, only by applying the regular expression classifier.17 [ABSTRACT FROM AUTHOR]

This paper introduces a systematic approach to designing high-performance parallel adders based on Counter Tree Diagrams (CTDs). By using CTDs, we can describe addition algorithms at various levels of abstraction. A high-level CTD represents a network of coarse-grained components associated with word-level operands, whereas a low-level CTD represents a network of primitive components that can be directly mapped onto physical devices. The level of abstraction in circuit representation can be changed by decomposition of CTDs. We can derive possible variations of adder structures by decomposing a high-level CTD into low-level CTDs in a formal manner. In this paper, we focus on an application of CTDs to the design of redundant arithmetic adders with limited carry propagation. For any redundant number representation, we can obtain the optimal adder structure by trying every possible CTD decomposition and CTD variable encoding. The potential of the proposed approach is demonstrated through an experimental synthesis of Redundant-Binary (RB) adders with CMOS standard cell libraries. We can successfully obtain RB adders that achieve an about 30-40 percent improvement in terms of power-delay product compared with conventional designs. [ABSTRACT FROM AUTHOR]

Most weak memory consistency models are incapable of supporting a solution to mutual exclusion using only read and write operations to shared variables. Processor Consistency-Goodman's version (PC-G) is an exception. Ahamad et al. showed that Peterson's mutual exclusion algorithm is correct for PC-G, but Lamport's bakery algorithm is not. This paper derives a lower bound on the number of and type of (single or multiwriter) variables that a mutual exclusion algorithm must use in order to be correct for PC-G. Specifically, any such solution for n processes must use at least one multiwriter variable and n single-writer variables. Peterson's algorithm for two processes uses one multiwriter and two single-writer variables, and therefore establishes that this bound is tight for two processes. This paper presents a new n-process algorithm for mutual exclusion that is correct for PC-G and achieves the bound for any n. While Peterson's algorithm is fair, this extension to arbitrary n is not fair. Six known algorithms that use the same number and type of variables are shown to fail to guarantee mutual exclusion when the memory consistency model is only PC-G, as opposed to the Sequential Consistency model for which they were designed. A corollary of our investigation is that, in contrast to Sequential Consistency, multiwriter variables cannot be implemented from single-writer variables in a PC-G system. [ABSTRACT FROM AUTHOR]

Many commercial products and academic research activities are embracing behavior analysis as a technique for improving detection of attacks of many sorts—from retweet boosting, hashtag hijacking to link advertising. Traditional approaches focus on detecting dense blocks in the adjacency matrix of graph data, and recently, the tensors of multimodal data. No method gives a principled way to score the suspiciousness of dense blocks with different numbers of modes and rank them to draw human attention accordingly. In this paper, we first give a list of axioms that any metric of suspiciousness should satisfy; we propose an intuitive, principled metric that satisfies the axioms, and is fast to compute; moreover, we propose CROSSSPOT, an algorithm to spot dense blocks that are worth inspecting, typically indicating fraud or some other noteworthy deviation from the usual, and sort them in the order of importance (“suspiciousness”). Finally, we apply CROSSSPOT to the real data, where it improves the F1 score over previous techniques by 68 percent and finds suspicious behavioral patterns in social datasets spanning 0.3 billion posts. [ABSTRACT FROM AUTHOR]

Max-flow has been adopted for semi-supervised data modelling, yet existing algorithms were derived only for the learning from static data. This paper proposes an online max-flow algorithm for the semi-supervised learning from data streams. Consider a graph learned from labelled and unlabelled data, and the graph being updated dynamically for accommodating online data adding and retiring. In learning from the resulting non stationary graph, we augment and de-augment paths to update max-flow with a theoretical guarantee that the updated max-flow equals to that from batch retraining. For classification, we compute min-cut over current max-flow, so that minimized number of similar sample pairs are classified into distinct classes. Empirical evaluation on real-world data reveals that our algorithm outperforms state-of-the-art stream classification algorithms. [ABSTRACT FROM AUTHOR]

Due to the fact that existing database systems are increasingly more difficult to use, improving the quality and the usability of database systems has gained tremendous momentum over the last few years. In particular, the feature of explaining why some expected tuples are missing in the result of a query has received more attention. In this paper, we study the problem of explaining missing answers to top-k queries in the context of SQL (i.e., with selection, projection, join, and aggregation). To approach this problem, we use the query-refinement method. That is, given as inputs the original top-k SQL query and a set of missing tuples, our algorithms return to the user a refined query that includes both the missing tuples and the original query results. Case studies and experimental results show that our algorithms are able to return high quality explanations efficiently. [ABSTRACT FROM AUTHOR]

Flash storage devices are widely used for mobile consumer electronics due to small size, low power consumption, and high performance. Generally, the flash storage device consists of NAND flash memories. Compared to traditional magnetic disks, NAND flash memory requires an additional erase operation and its blocks have limited erase cycles. For extending its endurance, various wearleveling algorithms have been proposed. However, they invoke many read/write/erase operations and use many memory resources for managing their block states because they do not consider the property of the flash translation layer. To solve these problems, a new wear-leveling algorithm for the log-based flash translation layer is proposed in this paper. In the log-based flash translation layer, since log blocks are frequently updated and erased, the cold block rarely removed is reserved for a next log block so that all the blocks are evenly erased. In addition, the proposed algorithm reduces the usage of memory resources by exploiting k-bitwise erase table that only needs small k-bit erase flags for managing its block erase state. Through various experiments with related wear-leveling algorithms, this paper shows the superiority of the proposed wear-leveling algorithm. [ABSTRACT FROM AUTHOR]

The accuracy and diversity of recommendation algorithms have always been the research hotspot of recommender systems. A good recommender system should not only have high accuracy and diversity, but also have adequate robustness against spammer attacks. However, the issue of recommendation robustness has received relatively little attention in the literature. In this paper, we systematically study the influences of different spammer behaviors on the recommendation results in various recommendation algorithms. We further propose an improved algorithm by incorporating the inner-similarity of user’s purchased items in the classic KNN approach. The new algorithm effectively enhances the robustness against spammer attacks and thus outperforms traditional algorithms in recommendation accuracy and diversity when spammers exist in the online commercial systems. [ABSTRACT FROM AUTHOR]

In this paper, an Arcak-type generalized $$H_2$$ filter is designed for a class of static neural networks with time-varying delay. By employing some inequalities and constructing a suitable Lyapunov functional, a delay-dependent condition is derived by means of linear matrix inequalities such that the filtering error system is globally asymptotically stable and a prescribed generalized $$H_2$$ performance is achieved. It is shown that the design of such a desired filter for a delayed static neural network is successfully transformed into solving a convex optimization problem subject to some linear matrix inequalities. It is thus facilitated readily by some standard algorithms. A numerical example is finally provided to show the effectiveness of the developed approach. A comparison on the generalized $$H_2$$ performance for different gain parameters of the activation function is also given. [ABSTRACT FROM AUTHOR]

The architecture of decentralization makes future wireless networks more flexible and scalable. However, due to the lack of the central authority (e.g., BS or AP), the limitation of spectrum resource, and the coupling among different users, designing efficient resource allocation strategies for decentralized networks faces a great challenge. In this paper, we address the distributed channel selection and power control problem for a decentralized network consisting of multiple users, i.e., transmit-receiver pairs. Particularly, we first take the users' interactions into account and formulate the distributed resource allocation problem as a non-cooperative transmission control game (NTCG). Then, a utility-based transmission control algorithm (UTC) is developed based on the formulated game. Our proposed algorithm is completely distributed as there is no information exchange among different users and hence, is especially appropriate for this decentralized network. Furthermore, we prove that the global optimal solution can be asymptotically obtained with the devised algorithm, and more importantly, in contrast to existing utility-based algorithms, our method does not require that the converging point is one Nash equilibrium (NE) of the formulated game. In this light, our algorithm can be adopted to achieve efficient resource allocation in more general use cases. [ABSTRACT FROM AUTHOR]

In computer science, digital image processing is the use of computer algorithms to perform image processing on digital images. The Image processing as a subgroup or background of digital signal processing has many advantages over analog image processing. The Digital image processing allows the use of a wide range of algorithms for input data and avoids problems such as noise accumulation and signal distortion during the processing process. Because images are defined in two dimensions (perhaps more than two dimensions), image processing can be formatted into multi-dimensional systems. In this paper an effective Mathematical morphology model was proposed to enhance the quality of images. In this mode, the image is pre-processed and then the gradient is changed using a mathematical image system. Then, the edges are detected by the margin detection method based on the statistical data. This method removes the shadow contours caused by the lights, directly separates the boundaries of the objects and has an impact on the background noise suppression. [ABSTRACT FROM AUTHOR]

In computer science, cycle detection is the algorithmic problem of finding a cycle in a sequence of iterated function values. The analysis of cycles in network has different application in the design and development in communication systems such as the investigation of topological features and consideration of reliability and fault tolerance. There are various problems related to the analysis of cycles in network among which the most important one is the detection of cycles in graph. In this paper, we proposed SUS_dcycle method which is a detection algorithm for detecting cycle in a directed graph, with the help of linked list in order to discover new lists in run time. This algorithm is used to detect the cycle in any type of directed graph. The proposed algorithm differs from other existing algorithms through its ability to count the total number of cycles present in any type of directed graphs. Also the study of earlier works says that this is a novel approach for the prescribed task and complex problems may use it as a subroutine application for effective results. In advanced computing, time-space trade-off is an important factor to efficiently deal with the problems. This method may solve the above said purpose. [ABSTRACT FROM AUTHOR]

An understanding of how individuals shape and impact the evolution of society is vastly limited due to the unavailability of large-scale reliable datasets that can simultaneously capture information regarding individual movements and social interactions. We believe that the popular Indian film industry, “Bollywood”, can provide a social network apt for such a study. Bollywood provides massive amounts of real, unbiased data that spans more than 100 years, and hence this network has been used as a model for the present paper. The nodes which maintain a moderate degree or widely cooperate with the other nodes of the network tend to be more fit (measured as the success of the node in the industry) in comparison to the other nodes. The analysis carried forth in the current work, using a conjoined framework of complex network theory and random matrix theory, aims to quantify the elements that determine the fitness of an individual node and the factors that contribute to the robustness of a network. The authors of this paper believe that the method of study used in the current paper can be extended to study various other industries and organizations. [ABSTRACT FROM AUTHOR]

Using statistical textons for texture classification has shown great success recently. The maximal response 8 (Statistical_MR8), image patch (Statistical_Joint) and locally invariant fractal (Statistical_Fractal) are typical statistical texton algorithms and state-of-the-art texture classification methods. However, there are two limitations when using these methods. First, it needs a training stage to build a texton library, thus the recognition accuracy will be highly depended on the training samples; second, during feature extraction, local feature is assigned to a texton by searching for the nearest texton in the whole library, which is time consuming when the library size is big and the dimension of feature is high. To address the above two issues, in this paper, three binary texton counterpart methods were proposed, Binary_MR8, Binary_Joint, and Binary_Fractal. These methods do not require any training step but encode local feature into binary representation directly. The experimental results on the CUReT, UIUC and KTH-TIPS databases show that binary texton could get sound results with fast feature extraction, especially when the image size is not big and the quality of image is not poor. [ABSTRACT FROM AUTHOR]

In this paper, a new heat-map-based algorithm is proposed for group activity recognition. The proposed algorithm first models human trajectories as series of heat sources and then applies a thermal diffusion process to create a heat map (HM) for representing the group activities. Based on this HM, a new key-point-based (KPB) method is used for handling the alignments among HMs with different scales and rotations. A surface-fitting (SF) method is also proposed for recognizing group activities. Our proposed HM feature can efficiently embed the temporal motion information of the group activities while the proposed KPB and SF methods can effectively utilize the characteristics of the HM for activity recognition. refid="sec4"Section IV demonstrates the effectiveness of our proposed algorithms. [ABSTRACT FROM PUBLISHER]

Crowdsourcing has been shown to be effective in a wide range of applications, and is seeing increasing use. A large-scale crowdsourcing task often consists of thousands or millions of atomic tasks, each of which is usually a simple task such as binary choice or simple voting. To distribute a large-scale crowdsourcing task to limited crowd workers, a common practice is to pack a set of atomic tasks into a task bin and send to a crowd worker in a batch. It is challenging to decompose a large-scale crowdsourcing task and execute batches of atomic tasks, which ensures reliable answers at a minimal total cost. Large batches lead to unreliable answers of atomic tasks, while small batches incur unnecessary cost. In this paper, we investigate a general crowdsourcing task decomposition problem, called the Smart Large-scAle task DE composer (SLADE) problem, which aims to decompose a large-scale crowdsourcing task to achieve the desired reliability at a minimal cost. We prove the NP-hardness of the SLADE problem and propose solutions in both homogeneous and heterogeneous scenarios. For the homogeneous SLADE problem, where all the atomic tasks share the same reliability requirement, we propose a greedy heuristic algorithm and an efficient and effective approximation framework using an optimal priority queue (OPQ) structure with provable approximation ratio. For the heterogeneous SLADE problem, where the atomic tasks can have different reliability requirements, we extend the OPQ-based framework leveraging a partition strategy, and also prove its approximation guarantee. Finally, we verify the effectiveness and efficiency of the proposed solutions through extensive experiments on representative crowdsourcing platforms. [ABSTRACT FROM AUTHOR]

Recent smart devices have adopted heterogeneous multi-core processors which have high-performance big cores and low-power small cores. Unfortunately, the conventional task scheduler for heterogeneous multi-core processors does not provide appropriate amount of CPU resources for multimedia applications (whose QoS is important to users), resulting in energy waste; it often executes multimedia applications and non-multimedia applications on the same core. In this paper, we propose an advanced task scheduler for heterogeneous multi-core processors, which provides appropriate amount of CPU resources for multimedia applications. Our proposed task scheduler isolates multimedia applications from non-multimedia applications at runtime, exploiting the fact that multimedia applications have a specific thread for video/audio playback (to play video/audio, a multimedia application should use a function that generates the specific thread). Since multimedia applications usually require a smaller amount of CPU resources than non-multimedia applications due to dedicated hardware decoders, our proposed task scheduler allocates the former to the small cores and the latter to the big cores. In our experiments on an Android-based development board, our proposed task scheduler saves system-wide (not just CPU) energy consumption by 8.9 percent, on average, compared to the conventional task scheduler, preserving QoS of multimedia applications. In addition, it improves performance of non-multimedia applications by 13.7 percent, on average, compared to the conventional task scheduler. [ABSTRACT FROM PUBLISHER]

The phenomenon of digital computation is explained (often differently) in computer science, computer engineering and more broadly in cognitive science. Although the semantics and implications of malfunctions have received attention in the philosophy of biology and philosophy of technology, errors in computational systems remain of interest only to computer science. Miscomputation has not gotten the philosophical attention it deserves. Our paper fills this gap by offering a taxonomy of miscomputations. This taxonomy is underpinned by a conceptual analysis of the design and implementation of conventional computational systems at various levels of abstraction. It shows that 'malfunction' as it is typically used in the philosophy of artefacts only represents one type of miscomputation. [ABSTRACT FROM AUTHOR]

Most digital cameras use an array of alternating color filters to capture the varied colors in a scene with a single sensor chip. Reconstruction of a full color image from such a color mosaic is what constitutes demosaicing. In this paper, a technique is proposed that performs this demosaicing in a way that incurs a very low computational cost. This is done through a (dual-tree complex) wavelet interpretation of the demosaicing problem. By using a novel locally adaptive approach for demosaicing (complex) wavelet coefficients, we show that many of the common demosaicing artifacts can be avoided in an efficient way. Results demonstrate that the proposed method is competitive with respect to the current state of the art, but incurs a lower computational cost. The wavelet approach also allows for computationally effective denoising or deblurring approaches. [ABSTRACT FROM AUTHOR]

In this paper, we investigate the capacitated two-parallel machines scheduling problem, where one machine is only available for a special period of time after which it can no longer process any job while the other machine is continuously available. Our objective is to minimize the completion time of the machine which is continuously available. The offline version of the problem is equivalent to the minimization version of the Subset-Sum problem. We first show the lower bound of the online version is infinite. We also consider the semi-online version with known the total job processing time in advance, for which both lower bound and semi-online algorithms are given. [ABSTRACT FROM AUTHOR]

Given a tree T=( V, E) of n nodes such that each node v is associated with a value-weight pair ( val, w), where value val is a real number and weight w is a non-negative integer, the density of T is defined as $\frac{\sum_{v\in V}{\mathit{val}}_{v}}{\sum_{v\in V}w_{v}}$. A subtree of T is a connected subgraph ( V′, E′) of T, where V′⊆ V and E′⊆ E. Given two integers w and w, the weight-constrained maximum-density subtree problem on T is to find a maximum-density subtree T′=( V′, E′) satisfying w≤∑ w≤ w. In this paper, we first present an O( w n)-time algorithm to find a weight-constrained maximum-density path in a tree T, and then present an O( w n)-time algorithm to find a weight-constrained maximum-density subtree in T. Finally, given a node subset S⊂ V, we also present an O( w n)-time algorithm to find a weight-constrained maximum-density subtree in T which covers all the nodes in S. [ABSTRACT FROM AUTHOR]

In this paper, we discuss one of the most important issues in Sensor-Grid, i.e., to develop a fast and flexible content-based publish/subscribe information dissemination (CBPSID) system for automatic fusion, interpretation, sharing and delivery of huge sensor data to consumers as the entire Sensor-Grid environment is very dynamic. Existing works to develop the CBPSID system in Sensor-Grid mostly focus on reducing the effort to define and maintain subscriptions and to handle the difficulty of dynamic changes of publishers and consumers data. However, the performance of a CBPSID system in Sensor-Grid is bounded by the expensive matching/evaluation cost of events. Existing event-matching algorithms are not very efficient, especially for interval range predicates or overlapping predicates in subscriptions which are practical in Sensor-Grid as well as other application areas. So in this paper we discuss the above challenge and propose a dynamic and fast event-matching algorithm called CGIM for the CBPSID system in Sensor-Grid. The algorithm supports range predicates or overlapping predicates very well and provides single and composite event matching. It uses two approaches, called SGIM and DGIM, to group the subscriptions by the predicates and dynamically identifies appropriate number of groups considering different statistical distributions of subscriptions at run time. Also, we present an experimental evaluation of the proposed algorithm in a Sensor-Grid based u-Healthcare scenario using synthetic workloads and compare its performance with existing algorithms. The experimental results show that our algorithm significantly reduces the evaluation cost (on average using SGIM by 79% and DGIM by 88%) comparing with others and guarantees the scalability with respect to the number of subscriptions as well as the number of predicates and events. In addition, further experiments were conducted by applying the CGIM algorithm in other application areas, e.g. in the publish/subscribe system for online job sites, to show its diverse utilization and scalability. [ABSTRACT FROM AUTHOR]

For some time it has been known that the standard method for collecting link-traffic measurements in IP networks-the Simple Network Management Protocol or SNMP-is flawed. It has often been noted that SNMP is subject to missing data, and that its measurements contain errors. However, very little work has been aimed at assessing the magnitude of these errors. This paper develops a simple, easily applicable technique for measuring SNMP errors, and uses it in a case study to assess errors in a common SNMP collection tool. The results indicate that most link-load measurement errors are relatively small, but the distribution has a heavy-tail, and that a few measurement errors can be as large as the measurements themselves. The approach also allows us to go some way towards explaining the cause of the errors. [ABSTRACT FROM AUTHOR]

In a recent paper we have introduced a new class of search directions for solving linear optimization (LO) problems. These directions are based on an algebraic equivalent transformation of the nonlinear equation from the system which defines the central path. However, from the implementation point of view predictor-corrector algorithms proved to be the most efficient among the class of interior point methods (IPMs). Therefore, we have defined also other variants of this class of algorithms, for example a weighted path-following algorithm, and a predictor-corrector algorithm for LO problems. Recently, the technique of finding search directions has been applied with success for linearly constrained convex optimization (LCCO), by Zhang, Bai and Wang. In this paper we define a new predictor-corrector algorithm for solving LCCO problems. We obtain new search directions by applying the method of algebraic equivalent transformation in this case too. Polynomial complexity of this algorithm is proved. [ABSTRACT FROM AUTHOR]

Researchers have explored the application of combinatorial interaction testing (CIT) methods to construct samples to drive systematic testing of software system configurational Applying CIT to highly-configurable software systems is complicated by the fact that, in many such systems, there are constraints between specific configuration parameters that render certain combinations invalid. Many CIT algorithms lack a mechanism to avoid these. In recent work, automated constraint solving methods have been combined with search-based CIT construction methods to address the constraint problem with promising results. However, these techniques can incur a nontrivial overhead. In this paper, we build upon our previous work to develop a family of greedy CIT sample generation algorithms that exploit calculations made by modern Boolean satisfiability (SAT) solvers to prune the search space of the CIT problem. We perform a comparative evaluation of the cost effectiveness of these algorithms on four real-world highly-configurable software systems and on a population of synthetic examples that share the characteristics of these systems. In combination, our techniques reduce the cost of CIT in the presence of constraints to 30 percent of the cost of widely used unconstrained CIT methods without sacrificing the quality of the solutions. [ABSTRACT FROM AUTHOR]

Asian options are popular financial derivative securities. Unfortunately, no exact pricing formulas exist for their price under continuous-time models. Asian options can also be priced on the lattice, which is a discretized version of the continuous- time model. But only exponential-time algorithms exist if the options are priced on the lattice without approximations. Although efficient approximation methods are available, they lack accuracy guarantees in general. This paper proposes a novel lattice structure for pricing Asian options. The resulting pricing algorithm is exact (i.e., without approximations), converges to the value under the continuous-time model, and runs in subexponential time. This is the first exact, convergent lattice algorithm to break the long-standing exponential-time barrier. [ABSTRACT FROM AUTHOR]

The recent Maximum Weighted Likelihood (MWL) [18], [19] has provided a general learning paradigm for density-mixture model selection and learning, in which weight design, however, is a key issue. This paper will therefore explore such a design, and through which a heuristic extended Expectation-Maximization (X-EM) algorithm is presented accordingly. Unlike the EM algorithm [1], the X-EM algorithm is able to perform model selection by fading the redundant components out from a density mixture, meanwhile estimating the model parameters appropriately. The numerical simulations demonstrate the efficacy of our algorithm. [ABSTRACT FROM AUTHOR]

Given a user-specified minimum correlation threshold θ and a market-basket database with N items and T transactions, an all-strong-pairs correlation query finds all item pairs with correlations above the threshold θ. However, when the number of items and transactions are large, the computation cost of this query can be very high. The goal of this paper is to provide computationally efficient algorithms to answer the all-strong-pairs correlation query. Indeed, we identify an upper bound of Pearson's correlation coefficient for binary variables. This upper bound is not only much cheaper to compute than Pearson's correlation coefficient, but also exhibits special monotone properties which allow pruning of many item pairs even without computing their upper bounds. A Two-step All- strong-Pairs corElation queRy (TAPER) algorithm is proposed to exploit these properties in a filter-and-refine manner. Furthermore, we provide an algebraic cost model which shows that the computation savings from pruning is independent of or improves when the number of items is increased in data sets with Zipf-like or linear rank-support distributions. Experimental results from synthetic and real-world data sets exhibit similar trends and show that the TAPER algorithm can be an order of magnitude faster than brute-force alternatives. Finally, we demonstrate that the algorithmic ideas developed in the TAPER algorithm can be extended to efficiently compute negative correlation and uncentered Pearson's correlation coefficient. [ABSTRACT FROM AUTHOR]

This paper presents an application for generating a dynamic selection screen in ABAP and the need and advantages of this solution instead of the manual modification of the coding itself for adding one or more parameters in the whole logic of the program. Depending on data found in a customizing table, we would like to generate a program with a selection screen, containing select options based on the criteria specified in the customizing table. The presented solution can be adapted to any dynamically generated ABAP program, according to the desired selection screen elements, and may be used as a template even for other programs. The advantages of the proposed solution are also presented along with the disadvantages, underlining the particularities of the ABAP programming language. [ABSTRACT FROM AUTHOR]

The past decade or so has seen a dramatic change in the way that economists can learn by watching our planet from above. A revolution has taken place in remote sensing and allied fields such as computer science, engineering, and geography. Petabytes of satellite imagery have become publicly accessible at increasing resolution, many algorithms for extracting meaningful social science information from these images are now routine, and modern cloud-based processing power allows these algorithms to be run at global scale. This paper seeks to introduce economists to the science of remotely sensed data, and to give a flavor of how this new source of data has been used by economists so far and what might be done in the future. [ABSTRACT FROM AUTHOR]

The well-known periodic task model of Liu and Layland [10] assumes a worst-case execution time bound for every task and may be too pessimistic if the worst-case execution time of a task is much longer than the average. In this paper, we give a multiframe real-time task model which allows the execution time of a task to vary from one instance to another by specifying the execution time of a task in terms of a sequence of numbers. We investigate the schedulability problem for this model for the preemptive fixed priority scheduling policy. We show that a significant improvement in the utilization bound can be established in our model. [ABSTRACT FROM AUTHOR]

Due to low quality of crowdsourced labelers, the integrated label of each example is usually inferred from its multiple noisy labels provided by different labelers. This paper proposes a novel algorithm, Ground Truth Inference using Clustering (GTIC), to improve the quality of integrated labels for multi-class labeling. For a K labeling case, GTIC utilizes the multiple noisy label sets of examples to generate features. Then, it uses a K-Means algorithm to cluster all examples into K different groups, each of which is mapped to a specific class. Examples in the same cluster are assigned a corresponding class label. We compare GTIC with four existing multi-class ground truth inference algorithms, majority voting (MV), Dawid & Skene's (DS), ZenCrowd (ZC) and Spectral DS (SDS), on one synthetic and eight real-world datasets. Experimental results show that the performance of GTIC is significantly superior to the others in terms of both accuracy and M-AUC. Besides, the running time of GTIC is about twenty times faster than EM-based complicated inference algorithms. [ABSTRACT FROM PUBLISHER]

Given a set of objects \mathcal O , each with d numeric attributes, a top-k preference scores these objects using a linear combination of their attribute values, where the weight on each attribute reflects the interest in this attribute. Given a query preference q , a top- k query finds the k objects in q , a reverse top- k query finds all preferences q\in \mathcal Q for which o becomes one of the top $k$ objects with respect to $q$ . Previous solutions to these problems are effective only in low dimensions. In this paper, we develop a solution for much higher dimensions (up to high tens), if many preferences exhibit sparsity —i.e., each specifies non-zero weights for only a handful (say $5$ - $7$ ) of attributes (though the subsets of such attributes and their weights can vary greatly). Our idea is to select carefully a set of low-dimensional core subspaces to “cover” the sparse preferences in a workload. These subspaces allow us to index them more effectively than the full-dimensional space. Being multi-dimensional, each subspace covers many possible preferences; furthermore, multiple subspaces can jointly cover a preference, thereby expanding the coverage beyond each subspace’s dimensionality. Experimental evaluation validates our solution’s effectiveness and advantages over previous solutions. [ABSTRACT FROM AUTHOR]