OpenRaiser/Intern-Atlas huggingface dataset:
Ontology Usage at ZFIN
Venue: arXiv cs.DB 2010
Year: 2010

The Zebrafish Model Organism Database (ZFIN) provides a Web resource of zebrafish genomic, genetic, developmental, and phenotypic data. Four different ontologies are currently used to annotate data to the most specific term available facilitating a better comparison between inter-species data. In addition, ontologies are used to help users find and cluster data more quickly without the need of knowing the exact technical name for a term.
An Energy-efficient Clock Synchronization Protocol for Wireless Sensor Networks
Venue: arXiv cs.NI 2010
Year: 2010

The behavior of Wireless Sensor Networks (WSN) is nowadays widely analyzed. One of the most important issues is related to their energy consumption, as this has a major impact on the network lifetime. Another important application requirement is to ensure data sensing synchronization, which leads to additional energy consumption as a high number of messages is sent and received at each node. Our proposal consists in implementing a combined synchronization protocol based on the IEEE 1588 standard that was designed for wired networks and the PBS (Pairwise Broadcast Synchronization) protocol that was designed for sensor networks, as none of them is able to provide the needed synchronization accuracy for our application on its own. The main goals of our new synchronization protocol are: to ensure the accuracy of local clocks up to a tenth of a microsecond and to provide an important energy saving. Our results obtained using NS-2 (Network Simulator) show that the performance of our solution (IEEE 1588-PBS) matches our application requirements with regard to the synchronization, with a significant improvement in energy saving.
New Row-grouped CSR format for storing the sparse matrices on GPU with implementation in CUDA
Venue: arXiv cs.DC 2010
Year: 2010

In this article we present a new format for storing sparse matrices. The format is designed to perform well mainly on the GPU devices. We present its implementation in CUDA. The performance has been tested on 1,600 different types of matrices and we compare our format with the Hybrid format. We give detailed comparison of both formats and show their strong and weak parts.
Analyzing Zone Routing Protocol in MANET Applying Authentic Parameter
Venue: arXiv cs.NI 2010
Year: 2010

Routing is the main part of wireless adhoc network conventionally there are two approaches first one is Proactive and another one is Reactive. Both these approaches have some substantial disadvantage and to overcome hybrid routing protocols designed. ZRP (Zone Routing Protocol) is one of the hybrid routing protocols, it takes advantage of proactive approach by providing reliability within the scalable zone, and for beyond the scalable zone it looks for the reactive approach. It (ZRP) uses the proactive and the reactive routing according to the need of the application at that particular instance of time depending upon the prevailing scenario. This work revolves around the performance of ZRP against realistic parameters by varying various attributes such as Zone Radius of ZRP in different node density. Results vary as we change the node density on Qualnet 4.0 network simulator.
A Trust-Based Detection Algorithm of Selfish Packet Dropping Nodes in a Peer-to-Peer Wireless Mesh Network
Venue: arXiv cs.CR 2010
Year: 2010

Wireless mesh networks (WMNs) are evolving as a key technology for next-generation wireless networks showing raid progress and numerous applications. These networks have the potential to provide robust and high-throughput data delivery to wireless users. In a WMN, high speed routers equipped with advanced antennas, communicate with each other in a multi-hop fashion over wireless channels and form a broadband backhaul. However, the throughput of a WMN may be severely degraded due to presence of some selfish routers that avoid forwarding packets for other nodes even as they send their own traffic through the network. This paper presents an algorithm for detection of selfish nodes in a WMN that uses statistical theory of inference for reliable clustering of the nodes based on local observations. Simulation results show that the algorithm has a high detection rate and a low false positive rate.
Real-time Visual Tracking Using Sparse Representation
Venue: arXiv cs.CV 2010
Year: 2010

The $\ell_1$ tracker obtains robustness by seeking a sparse representation of the tracking object via $\ell_1$ norm minimization \cite{Xue_ICCV_09_Track}. However, the high computational complexity involved in the $ \ell_1 $ tracker restricts its further applications in real time processing scenario. Hence we propose a Real Time Compressed Sensing Tracking (RTCST) by exploiting the signal recovery power of Compressed Sensing (CS). Dimensionality reduction and a customized Orthogonal Matching Pursuit (OMP) algorithm are adopted to accelerate the CS tracking. As a result, our algorithm achieves a real-time speed that is up to $6,000$ times faster than that of the $\ell_1$ tracker. Meanwhile, RTCST still produces competitive (sometimes even superior) tracking accuracy comparing to the existing $\ell_1$ tracker. Furthermore, for a stationary camera, a further refined tracker is designed by integrating a CS-based background model (CSBM). This CSBM-equipped tracker coined as RTCST-B, outperforms most state-of-the-arts with respect to both accuracy and robustness. Finally, our experimental results on various video sequences, which are verified by a new metric---Tracking Success Probability (TSP), show the excellence of the proposed algorithms.
Throughput and Latency of Acyclic Erasure Networks with Feedback in a Finite Buffer Regime
Venue: arXiv cs.IT 2010
Year: 2010

The exact Markov modeling analysis of erasure networks with finite buffers is an extremely hard problem due to the large number of states in the system. In such networks, packets are lost due to either link erasures or blocking by the full buffers. In this paper, we propose a novel method that iteratively estimates the performance parameters of the network and more importantly reduces the computational complexity compared to the exact analysis. This is the first work that analytically studies the effect of finite memory on the throughput and latency in general wired acyclic networks with erasure links. As a case study, a random packet routing scheme with ideal feedback on the links is used. The proposed framework yields a fairly accurate estimate of the probability distribution of buffer occupancies at the intermediate nodes using which we can not only identify the congested and starving nodes but also obtain analytical expressions for throughput and average delay of a packet in the network. The theoretical framework presented here can be applied to many wired networks, from Internet to more futuristic applications such as networks-on-chip under various communication and network coding scenarios.
Managing Delegation in Access Control Models
Venue: arXiv cs.CR 2010
Year: 2010

In the field of access control, delegation is an important aspect that is considered as a part of the administration mechanism. Thus, a complete access control must provide a flexible administration model to manage delegation. Unfortunately, to our best knowledge, there is no complete model for describing all delegation requirements for role-based access control. Therefore, proposed models are often extended to consider new delegation characteristics, which is a complex task to manage and necessitate the redefinition of these models. In this paper we describe a new delegation approach for extended role-based access control models. We show that our approach is flexible and is sufficient to manage all delegation requirements.
Bacteria inspired patterns grown with hyperbolic cellular automata
Venue: arXiv cs.FL 2010
Year: 2010

In this paper we give three examples of expending patterns defined by hyperbolic cellular automata whose growth seems to be very similar to the growth of colonies of bacteria.
Modeling Social Networks with Overlapping Communities Using Hypergraphs and Their Line Graphs
Venue: arXiv cs.SI 2010
Year: 2010

We propose that hypergraphs can be used to model social networks with overlapping communities. The nodes of the hypergraphs represent the communities. The hyperlinks of the hypergraphs denote the individuals who may participate in multiple communities. The hypergraphs are not easy to analyze, however, the line graphs of hypergraphs are simple graphs or weighted graphs, so that the network theory can be applied. We define the overlapping depth $k$ of an individual by the number of communities that overlap in that individual, and we prove that the minimum adjacency eigenvalue of the corresponding line graph is not smaller than $-k_{max}$, which is the maximum overlapping depth of the whole network. Based on hypergraphs with preferential attachment, we establish a network model which incorporates overlapping communities with tunable overlapping parameters $k$ and $w$. By comparing with the Hyves social network, we show that our social network model possesses high clustering, assortative mixing, power-law degree distribution and short average path length.
Sesame: Self-Constructive System Energy Modeling for Battery-Powered Mobile Systems
Venue: arXiv cs.OS 2010
Year: 2010

System energy models are important for energy optimization and management in mobile systems. However, existing system energy models are built in lab with the help from a second computer. Not only are they labor-intensive; but also they will not adequately account for the great diversity in the hardware and usage of mobile systems. Moreover, existing system energy models are intended for energy estimation for time intervals of one second or longer; they do not provide the required rate for fine-grain use such as per-application energy accounting. In this work, we study a self-modeling paradigm in which a mobile system automatically generates its energy model without any external assistance. Our solution, Se-same, leverages the possibility of self power measurement through the smart battery interface and employs a suite of novel techniques to achieve accuracy and rate much higher than that of the smart battery interface. We report the implementation and evaluation of Se-same on a laptop and a smartphone. The experiment results show that Sesame generates system energy models of 95% accuracy at one estimation per second and 88% accuracy at one estimation per 10ms, without any external assistance. A five-day field studies with four laptop and four smartphones users further demonstrate the effectiveness, efficiency, and noninvasiveness of Sesame.
On the size of data structures used in symbolic model checking
Venue: arXiv cs.AI 2010
Year: 2010

Temporal Logic Model Checking is a verification method in which we describe a system, the model, and then we verify whether some properties, expressed in a temporal logic formula, hold in the system. It has many industrial applications. In order to improve performance, some tools allow preprocessing of the model, verifying on-line a set of properties reusing the same compiled model; we prove that the complexity of the Model Checking problem, without any preprocessing or preprocessing the model or the formula in a polynomial data structure, is the same. As a result preprocessing does not always exponentially improve performance. Symbolic Model Checking algorithms work by manipulating sets of states, and these sets are often represented by BDDs. It has been observed that the size of BDDs may grow exponentially as the model and formula increase in size. As a side result, we formally prove that a superpolynomial increase of the size of these BDDs is unavoidable in the worst case. While this exponential growth has been empirically observed, to the best of our knowledge it has never been proved so far in general terms. This result not only holds for all types of BDDs regardless of the variable ordering, but also for more powerful data structures, such as BEDs, RBCs, MTBDDs, and ADDs.
Secure Information Flow by Model Checking Pushdown System
Venue: arXiv cs.CR 2010
Year: 2010

We propose an approach on model checking information flow for imperative language with procedures. We characterize our model with pushdown system, which has a stack of unbounded length that naturally models the execution of procedural programs. Because the type-based static analysis is sometimes too conservative and rejects safe program as ill-typed, we take a semantic-based approach by self-composing symbolic pushdown system and specifying noninterference with LTL formula. Then we verify this LTL-expressed property via model checker Moped. Except for overcoming the conservative characteristic of type-based approach, our motivation also includes the insufficient state of arts on precise information flow analysis under inter-procedural setting. To remedy the inefficiency of model checking compared with type system, we propose both compact form and contracted form of self-composition. According to our experimental results, they can greatly increase the efficiency of realistic verification. Our method provides flexibility on separating program abstraction from noninterference verification, thus could be expected to use on different programming languages.
Incentive Games and Mechanisms for Risk Management
Venue: arXiv cs.GT 2010
Year: 2010

Incentives play an important role in (security and IT) risk management of a large-scale organization with multiple autonomous divisions. This paper presents an incentive mechanism design framework for risk management based on a game-theoretic approach. The risk manager acts as a mechanism designer providing rules and incentive factors such as assistance or subsidies to divisions or units, which are modeled as selfish players of a strategic (noncooperative) game. Based on this model, incentive mechanisms with various objectives are developed that satisfy efficiency, preference-compatibility, and strategy-proofness criteria. In addition, iterative and distributed algorithms are presented, which can be implemented under information limitations such as the risk manager not knowing the individual units' preferences. An example scenario illustrates the framework and results numerically. The incentive mechanism design approach presented is useful for not only deriving guidelines but also developing computer-assistance systems for large-scale risk management.
Set Covering with Ordered Replacement -- Additive and Multiplicative Gaps
Venue: arXiv cs.DM 2010
Year: 2010

We consider set covering problems where the underlying set system satisfies a particular replacement property w.r.t. a given partial order on the elements: Whenever a set is in the set system then a set stemming from it via the replacement of an element by a smaller element is also in the set system. Many variants of BIN PACKING that have appeared in the literature are such set covering problems with ordered replacement. We provide a rigorous account on the additive and multiplicative integrality gap and approximability of set covering with replacement. In particular we provide a polylogarithmic upper bound on the additive integrality gap that also yields a polynomial time additive approximation algorithm if the linear programming relaxation can be efficiently solved. We furthermore present an extensive list of covering problems that fall into our framework and consequently have polylogarithmic additive gaps as well.
Dynamic Knowledge Capitalization through Annotation among Economic Intelligence Actors in a Collaborative Environment
Venue: arXiv cs.AI 2010
Year: 2010

The shift from industrial economy to knowledge economy in today's world has revolutionalized strategic planning in organizations as well as their problem solving approaches. The point of focus today is knowledge and service production with more emphasis been laid on knowledge capital. Many organizations are investing on tools that facilitate knowledge sharing among their employees and they are as well promoting and encouraging collaboration among their staff in order to build the organization's knowledge capital with the ultimate goal of creating a lasting competitive advantage for their organizations. One of the current leading approaches used for solving organization's decision problem is the Economic Intelligence (EI) approach which involves interactions among various actors called EI actors. These actors collaborate to ensure the overall success of the decision problem solving process. In the course of the collaboration, the actors express knowledge which could be capitalized for future reuse. In this paper, we propose in the first place, an annotation model for knowledge elicitation among EI actors. Because of the need to build a knowledge capital, we also propose a dynamic knowledge capitalisation approach for managing knowledge produced by the actors. Finally, the need to manage the interactions and the interdependencies among collaborating EI actors, led to our third proposition which constitute an awareness mechanism for group work management.
Rules of Thumb for Information Acquisition from Large and Redundant Data
Venue: arXiv cs.IR 2010
Year: 2010

We develop an abstract model of information acquisition from redundant data. We assume a random sampling process from data which provide information with bias and are interested in the fraction of information we expect to learn as function of (i) the sampled fraction (recall) and (ii) varying bias of information (redundancy distributions). We develop two rules of thumb with varying robustness. We first show that, when information bias follows a Zipf distribution, the 80-20 rule or Pareto principle does surprisingly not hold, and we rather expect to learn less than 40% of the information when randomly sampling 20% of the overall data. We then analytically prove that for large data sets, randomized sampling from power-law distributions leads to "truncated distributions" with the same power-law exponent. This second rule is very robust and also holds for distributions that deviate substantially from a strict power law. We further give one particular family of powerlaw functions that remain completely invariant under sampling. Finally, we validate our model with two large Web data sets: link distributions to domains and tag distributions on delicious.com.
Local-Testability and Self-Correctability of q-ary Sparse Linear Codes
Venue: arXiv cs.CC 2010
Year: 2010

We prove that q-ary sparse codes with small bias are self-correctable and locally testable. We generalize a result of Kaufman and Sudan that proves the local testability and correctability of binary sparse codes with small bias. We use properties of q-ary Krawtchouk polynomials and the McWilliams identity -that relates the weight distribution of a code to the weight distribution of its dual- to derive bounds on the error probability of the randomized tester and self-corrector we are analyzing.
A robust ranking algorithm to spamming
Venue: arXiv cs.IR 2010
Year: 2010

Ranking problem of web-based rating system has attracted many attentions. A good ranking algorithm should be robust against spammer attack. Here we proposed a correlation based reputation algorithm to solve the ranking problem of such rating systems where user votes some objects with ratings. In this algorithm, reputation of user is iteratively determined by the correlation coefficient between his/her rating vector and the corresponding objects' weighted average rating vector. Comparing with iterative refinement (IR) and mean score algorithm, results for both artificial and real data indicate that, the present algorithm shows a higher robustness against spammer attack.
Element Retrieval using Namespace Based on keyword search over XML Documents
Venue: arXiv cs.IR 2010
Year: 2010

Querying over XML elements using keyword search is steadily gaining popularity. The traditional similarity measure is widely employed in order to effectively retrieve various XML documents. A number of authors have already proposed different similarity-measure methods that take advantage of the structure and content of XML documents. They do not, however, consider the similarity between latent semantic information of element texts and that of keywords in a query. Although many algorithms on XML element search are available, some of them have the high computational complexity due to searching a huge number of elements. In this paper, we propose a new algorithm that makes use of the semantic similarity between elements instead of between entire XML documents, considering not only the structure and content of an XML document, but also semantic information of namespaces in elements. We compare our algorithm with the three other algorithms by testing on the real datasets. The experiments have demonstrated that our proposed method is able to improve the query accuracy, as well as to reduce the running time.
Minimum regulation of uncoordinated matchings
Venue: arXiv cs.GT 2010
Year: 2010

Due to the lack of coordination, it is unlikely that the selfish players of a strategic game reach a socially good state. A possible way to cope with selfishness is to compute a desired outcome (if it is tractable) and impose it. However this answer is often inappropriate because compelling an agent can be costly, unpopular or just hard to implement. Since both situations (no coordination and full coordination) show opposite advantages and drawbacks, it is natural to study possible tradeoffs. In this paper we study a strategic game where the nodes of a simple graph G are independent agents who try to form pairs: e.g. jobs and applicants, tennis players for a match, etc. In many instances of the game, a Nash equilibrium significantly deviates from a social optimum. We analyze a scenario where we fix the strategy of some players; the other players are free to make their choice. The goal is to compel a minimum number of players and guarantee that any possible equilibrium of the modified game is a social optimum, i.e. created pairs must form a maximum matching of G. We mainly show that this intriguing problem is NP-hard and propose an approximation algorithm with a constant ratio.
Survey & Experiment: Towards the Learning Accuracy
Venue: arXiv cs.LG 2010
Year: 2010

To attain the best learning accuracy, people move on with difficulties and frustrations. Though one can optimize the empirical objective using a given set of samples, its generalization ability to the entire sample distribution remains questionable. Even if a fair generalization guarantee is offered, one still wants to know what is to happen if the regularizer is removed, and/or how well the artificial loss (like the hinge loss) relates to the accuracy. For such reason, this report surveys four different trials towards the learning accuracy, embracing the major advances in supervised learning theory in the past four years. Starting from the generic setting of learning, the first two trials introduce the best optimization and generalization bounds for convex learning, and the third trial gets rid of the regularizer. As an innovative attempt, the fourth trial studies the optimization when the objective is exactly the accuracy, in the special case of binary classification. This report also analyzes the last trial through experiments.