OpenRaiser/Intern-Atlas huggingface dataset:
A nonenumerative algorithm to find the k longest (shortest) paths in a DAG
Venue: arXiv cs.DS 2013
Year: 2013

In this paper, we present a novel and efficient algorithm to find the k longest (shortest) paths between sources and sinks in a directed acyclic graph (DAG). The algorithm does not enumerate paths therefore it is especially useful for very large k values. It is based on the Valued-Sum-of-Product (VSOP) tool, which is an extension of Zero-suppressed Binary Decision Diagrams (ZBDDs). We assessed the performance of this algorithm with a DAG model of a path-intensive combinational circuit, viz. c6288, that has \sim10^{20} paths. We found that it took about 64 minutes to compute all paths in this DAG along with their lengths.
MANCaLog: A Logic for Multi-Attribute Network Cascades (Technical Report)
Venue: arXiv cs.AI 2013
Year: 2013

The modeling of cascade processes in multi-agent systems in the form of complex networks has in recent years become an important topic of study due to its many applications: the adoption of commercial products, spread of disease, the diffusion of an idea, etc. In this paper, we begin by identifying a desiderata of seven properties that a framework for modeling such processes should satisfy: the ability to represent attributes of both nodes and edges, an explicit representation of time, the ability to represent non-Markovian temporal relationships, representation of uncertain information, the ability to represent competing cascades, allowance of non-monotonic diffusion, and computational tractability. We then present the MANCaLog language, a formalism based on logic programming that satisfies all these desiderata, and focus on algorithms for finding minimal models (from which the outcome of cascades can be obtained) as well as how this formalism can be applied in real world scenarios. We are not aware of any other formalism in the literature that meets all of the above requirements.
Prior-independent Auctions for Risk-averse Agents
Venue: arXiv cs.GT 2013
Year: 2013

We study simple and approximately optimal auctions for agents with a particular form of risk-averse preferences. We show that, for symmetric agents, the optimal revenue (given a prior distribution over the agent preferences) can be approximated by the first-price auction (which is prior independent), and, for asymmetric agents, the optimal revenue can be approximated by an auction with simple form. These results are based on two technical methods. The first is for upper-bounding the revenue from a risk-averse agent. The second gives a payment identity for mechanisms with pay-your-bid semantics.
Zipf's law and L. Levin's probability distributions
Venue: arXiv cs.IT 2013
Year: 2013

Zipf's law in its basic incarnation is an empirical probability distribution governing the frequency of usage of words in a language. As Terence Tao recently remarked, it still lacks a convincing and satisfactory mathematical explanation. In this paper I suggest that at least in certain situations, Zipf's law can be explained as a special case of the a priori distribution introduced and studied by L. Levin. The Zipf ranking corresponding to diminishing probability appears then as the ordering determined by the growing Kolmogorov complexity. One argument justifying this assertion is the appeal to a recent interpretation by Yu. Manin and M. Marcolli of asymptotic bounds for error--correcting codes in terms of phase transition. In the respective partition function, Kolmogorov complexity of a code plays the role of its energy. This version contains minor corrections and additions.
A Self-Organizing Neural Scheme for Door Detection in Different Environments
Venue: arXiv cs.CV 2013
Year: 2013

Doors are important landmarks for indoor mobile robot navigation and also assist blind people to independently access unfamiliar buildings. Most existing algorithms of door detection are limited to work for familiar environments because of restricted assumptions about color, texture and shape. In this paper we propose a novel approach which employs feature based classification and uses the Kohonen Self-Organizing Map (SOM) for the purpose of door detection. Generic and stable features are used for the training of SOM that increase the performance significantly: concavity, bottom-edge intensity profile and door edges. To validate the robustness and generalizability of our method, we collected a large dataset of real world door images from a variety of environments and different lighting conditions. The algorithm achieves more than 95% detection which demonstrates that our door detection method is generic and robust with variations of color, texture, occlusions, lighting condition, scales, and viewpoints.
Investigating the performance of Correspondence Algorithms in Vision based Driver-assistance in Indoor Environment
Venue: arXiv cs.CV 2013
Year: 2013

This paper presents the experimental comparison of fourteen stereo matching algorithms in variant illumination conditions. Different adaptations of global and local stereo matching techniques are chosen for evaluation The variant strength and weakness of the chosen correspondence algorithms are explored by employing the methodology of the prediction error strategy. The algorithms are gauged on the basis of their performance on real world data set taken in various indoor lighting conditions and at different times of the day
EELA Operations: A standalone regional dashboard implementation
Venue: arXiv cs.SE 2013
Year: 2013

Grid operators in EGEE use a dedicated dashboard as their central operational tool, stable and scalable for the last 5 years despite continuous upgrade from specifications by users, monitoring tools or data providers. In EGEE-III, regionalisation of operations led the tool developers to conceive a standalone instance of this tool. Hereby, we will present the concept and the EELA-II implementation. Indeed, there-engineering of this tool led to an easily deployable package that canconnect to EELA-II specific information sources such as EVENTUM, EELAGOCDB like or SAM EELA instance through the three components of thepackage: the generic and scalable data access mechanism, Lavoisier; thewidely spread php framework Symfony, for configuration flexibility and a Mysql database.
Validation of the IS Impact Model for Measuring the Impact of e-Learning Systems in KSA Universities: Student Perspective
Venue: arXiv cs.CY 2013
Year: 2013

The IS-Impact Measurement Model, developed by Gable, Sedera and Chan in 2008, represents the to-date and expected stream of net profits from a given information system (IS), as perceived by all major user classes. Although this model has been stringently validated in previous studies, its generalizability and verified effectiveness are enhanced through this new application in e-learning. This paper focuses on the re-validation of the findings of the IS-Impact Model in two universities in the Kingdom of Saudi Arabia (KSA). Among the users of 2 universities e-learning systems, 528 students were recruited. A formative validation measurement with SmartPLS, a graphical structural equation modeling tool was used to analyse the collected data. On the basis of the SmartPLS results, as well as with the aid of data-supported IS impact measurements and dimensions, we confirmed the validity of the IS-Impact Model for assessing the effect of e-learning systems in KSA universities. The newly constructed model is more understandable, its use was proved as robust and applicable to various circumstances.
Similarity Assessment through blocking and affordance assignment in Textual CBR
Venue: arXiv cs.IR 2013
Year: 2013

It has been conceived that children learn new objects through their affordances, that is, the actions that can be taken on them. We suggest that web pages also have affordances defined in terms of the users' information need they meet. An assumption of the proposed approach is that different parts of a text may not be equally important / relevant to a given query. Judgment on the relevance of a web document requires, therefore, a thorough look into its parts, rather than treating it as a monolithic content. We propose a method to extract and assign affordances to texts and then use these affordances to retrieve the corresponding web pages. The overall approach presented in the paper relies on case-based representations that bridge the queries to the affordances of web documents. We tested our method on the tourism domain and the results are promising.
The Sum-over-Forests density index: identifying dense regions in a graph
Venue: arXiv cs.LG 2013
Year: 2013

This work introduces a novel nonparametric density index defined on graphs, the Sum-over-Forests (SoF) density index. It is based on a clear and intuitive idea: high-density regions in a graph are characterized by the fact that they contain a large amount of low-cost trees with high outdegrees while low-density regions contain few ones. Therefore, a Boltzmann probability distribution on the countable set of forests in the graph is defined so that large (high-cost) forests occur with a low probability while short (low-cost) forests occur with a high probability. Then, the SoF density index of a node is defined as the expected outdegree of this node in a non-trivial tree of the forest, thus providing a measure of density around that node. Following the matrix-forest theorem, and a statistical physics framework, it is shown that the SoF density index can be easily computed in closed form through a simple matrix inversion. Experiments on artificial and real data sets show that the proposed index performs well on finding dense regions, for graphs of various origins.
Pruning a poset with veins
Venue: arXiv cs.DM 2013
Year: 2013

We recall some abstract connectivity concepts, and apply them to special chains in partially ordered sets, called veins, that are defined as order-convex chains that are contained in every maximal chain they meet. Veins enable us to define a new partial order on the same underlying set, called the pruning order. The associated pruned poset is simpler than the initial poset, but irreducible, coirreducible, and doubly-irreducible elements are preserved by the operation of pruning.
The Complexity of Scheduling for p-norms of Flow and Stretch
Venue: arXiv cs.DS 2013
Year: 2013

We consider computing optimal k-norm preemptive schedules of jobs that arrive over time. In particular, we show that computing the optimal k-norm of flow schedule, is strongly NP-hard for k in (0, 1) and integers k in (1, infinity). Further we show that computing the optimal k-norm of stretch schedule, is strongly NP-hard for k in (0, 1) and integers k in (1, infinity).
Cliques in complex networks reveal link formation and community evolution
Venue: arXiv cs.SI 2013
Year: 2013

Missing link prediction in indirected and un-weighted network is an open and challenge problem which has been studied intensively in recent years. In this paper, we studied the relationships between community structure and link formation and proposed a Fast Block probabilistic Model(FBM). In accordance with the experiments on four real world networks, we have yielded very good accuracy of missing link prediction and huge improvement in computing efficiency compared to conventional methods. By analyzing the mechanism of link formation, we also discovered that clique structure plays a significant role to help us understand how links grow in communities. Therefore, we summarized three principles which are proved to be able to well explain the mechanism of link formation and network evolution from the theory of graph topology.
On Lower Bound Methods for Tree-like Cutting Plane Proofs
Venue: arXiv cs.CC 2013
Year: 2013

In the book Boolean Function Complexity by Stasys Jukna, two lower bound techniques for Tree-like Cutting Plane proofs (henceforth, "Tree-CP proofs") using Karchmer-Widgerson type communication games (henceforth, "KW games") are presented: The first, applicable to Tree-CP proofs with bounded coefficients, translates Omega(t) deterministic lower bounds on KW games to 2^Omega(t/log n) lower bounds on Tree-CP proof size. The second, applicable to Tree-CP proofs with unbounded coefficients, translates Omega(t) randomized lower bounds on KW games to 2^Omega(t/log^2 n) lower bounds on Tree-CP proof size. The textbook proof in the latter case uses a O(log^2 n)-bit randomized protocol for the GreaterThan function. However, Nisan mentioned using the ideas of Feige, et al. to construct a O(log n + log(1/epsilon))-bit randomized protocol for GreaterThan. Nisan did not explicitly give the proof, though later results in his paper assume such a protocol. In this short exposition, we present the full O(log n + log(1/epsilon))-bit randomized protocol for the GreaterThan function based on the ideas of Feige, et al. for "noisy binary search." As an application, we show how to translate Omega(t) randomized lower bounds on KW games to 2^Omega(t/log n) lower bounds on Tree-CP proof size in the unbounded coefficient case. This equates randomness with coefficient size for the Tree-CP/KW game lower bound method. We believe that, while the O(log n + log(1/epsilon))-bit randomized protocol for GreaterThan is a "known" result, the explicit connection to Tree-CP proof size lower bounds given here is new.
Performance Analysis of Clustering Protocol Using Fuzzy Logic for Wireless Sensor Network
Venue: arXiv cs.NI 2013
Year: 2013

In order to gather information more efficiently, wireless sensor networks (WSNs) are partitioned into clusters. Most proposed clustering algorithms do not consider the location of the base station. This situation causes hot spot problems in multi-hop WSNs. In this paper, we analyze a fuzzy clustering algorithm (FCA) which aims to prolong the lifetime of WSNs. This algorithm adjusts the cluster-head radius considering the residual energy and distance to the base station parameters of the sensor nodes. This helps to decrease the intra-cluster work of the sensor nodes which are closer to the base station or have lower battery level. Fuzzy logic is utilized for handling the uncertainties in cluster-head radius estimation. We compare this algorithm with the low energy adaptive clustering hierarchy (LEACH) algorithm according to the parameters of first node dies half of the nodes alive and energy-efficiency metrics. Our simulation results show that the fuzzy clustering approach performs better than LEACH. Therefore, the FCA is a stable and energy-efficient clustering algorithm.
Performance Analysis of Bio-Inspired Routing Protocols based on Random Waypoint Mobility Model
Venue: arXiv cs.NI 2013
Year: 2013

A mobile ad hoc network (MANET) is a non-centralised, multihop, wireless network that lacks a common infrastructure and hence it needs self-organisation. The biggest challenge in MANETs is to find a path between communicating nodes, which is the MANET routing problem. Biology-inspired techniques such as ant colony optimisation (ACO) which have proven to be very adaptable in other problem domains, have been applied to the MANET routing problem as it forms a good fit to the problem. The general characteristics of these biological systems, which include their capability for self-organisation, self-healing and local decision making, make them suitable for routing in MANETs. In this paper, we discuss a few ACO based protocols, namely AntNet, hybrid ACO (AntHocNet), ACO based routing algorithm (ARA), imProved ant colony optimisation routing algorithm for mobile ad hoc NETworks (PACONET), ACO based on demand distance vector (Ant-AODV) and ACO based dynamic source routing (Ant-DSR), and determine their performance in terms of quality of service (QoS) parameters, such as end-to-end delay and packet delivery ratio, using Network Simulator 2 (NS2). We also compare them with well known protocols, ad hoc on demand distance vector (AODV) and dynamic source routing (DSR), based on the random waypoint mobility model. The simulation results show how this biology-inspired approach helps in improving QoS parameters.
Source Coding with in-Block Memory and Causally Controllable Side Information
Venue: arXiv cs.IT 2013
Year: 2013

The recently proposed set-up of source coding with a side information "vending machine" allows the decoder to select actions in order to control the quality of the side information. The actions can depend on the message received from the encoder and on the previously measured samples of the side information, and are cost constrained. Moreover, the final estimate of the source by the decoder is a function of the encoder's message and depends causally on the side information sequence. Previous work by Permuter and Weissman has characterized the rate-distortion-cost function in the special case in which the source and the "vending machine" are memoryless. In this work, motivated by the related channel coding model introduced by Kramer, the rate-distortion-cost function characterization is extended to a model with in-block memory. Various special cases are studied including block-feedforward and side information repeat request models.
Graph 3-coloring with a hybrid self-adaptive evolutionary algorithm
Venue: arXiv cs.NE 2013
Year: 2013

This paper proposes a hybrid self-adaptive evolutionary algorithm for graph coloring that is hybridized with the following novel elements: heuristic genotype-phenotype mapping, a swap local search heuristic, and a neutral survivor selection operator. This algorithm was compared with the evolutionary algorithm with the SAW method of Eiben et al., the Tabucol algorithm of Hertz and de Werra, and the hybrid evolutionary algorithm of Galinier and Hao. The performance of these algorithms were tested on a test suite consisting of randomly generated 3-colorable graphs of various structural features, such as graph size, type, edge density, and variability in sizes of color classes. Furthermore, the test graphs were generated including the phase transition where the graphs are hard to color. The purpose of the extensive experimental work was threefold: to investigate the behavior of the tested algorithms in the phase transition, to identify what impact hybridization with the DSatur traditional heuristic has on the evolutionary algorithm, and to show how graph structural features influence the performance of the graph-coloring algorithms. The results indicate that the performance of the hybrid self-adaptive evolutionary algorithm is comparable with, or better than, the performance of the hybrid evolutionary algorithm which is one of the best graph-coloring algorithms today. Moreover, the fact that all the considered algorithms performed poorly on flat graphs confirms that this type of graphs is really the hardest to color.
DAGGER: A Scalable Index for Reachability Queries in Large Dynamic Graphs
Venue: arXiv cs.DB 2013
Year: 2013

With the ubiquity of large-scale graph data in a variety of application domains, querying them effectively is a challenge. In particular, reachability queries are becoming increasingly important, especially for containment, subsumption, and connectivity checks. Whereas many methods have been proposed for static graph reachability, many real-world graphs are constantly evolving, which calls for dynamic indexing. In this paper, we present a fully dynamic reachability index over dynamic graphs. Our method, called DAGGER, is a light-weight index based on interval labeling, that scales to million node graphs and beyond. Our extensive experimental evaluation on real-world and synthetic graphs confirms its effectiveness over baseline methods.
Stratified SIFT Matching for Human Iris Recognition
Venue: arXiv cs.CV 2013
Year: 2013

This paper proposes an efficient three fold stratified SIFT matching for iris recognition. The objective is to filter wrongly paired conventional SIFT matches. In Strata I, the keypoints from gallery and probe iris images are paired using traditional SIFT approach. Due to high image similarity at different regions of iris there may be some impairments. These are detected and filtered by finding gradient of paired keypoints in Strata II. Further, the scaling factor of paired keypoints is used to remove impairments in Strata III. The pairs retained after Strata III are likely to be potential matches for iris recognition. The proposed system performs with an accuracy of 96.08% and 97.15% on publicly available CASIAV3 and BATH databases respectively. This marks significant improvement of accuracy and FAR over the existing SIFT matching for iris.
A Multi-GPU Programming Library for Real-Time Applications
Venue: arXiv cs.DC 2013
Year: 2013

We present MGPU, a C++ programming library targeted at single-node multi-GPU systems. Such systems combine disproportionate floating point performance with high data locality and are thus well suited to implement real-time algorithms. We describe the library design, programming interface and implementation details in light of this specific problem domain. The core concepts of this work are a novel kind of container abstraction and MPI-like communication methods for intra-system communication. We further demonstrate how MGPU is used as a framework for porting existing GPU libraries to multi-device architectures. Putting our library to the test, we accelerate an iterative non-linear image reconstruction algorithm for real-time magnetic resonance imaging using multiple GPUs. We achieve a speed-up of about 1.7 using 2 GPUs and reach a final speed-up of 2.1 with 4 GPUs. These promising results lead us to conclude that multi-GPU systems are a viable solution for real-time MRI reconstruction as well as signal-processing applications in general.
FAST CLOUD: Pushing the Envelope on Delay Performance of Cloud Storage with Coding
Venue: arXiv cs.NI 2013
Year: 2013

Our paper presents solutions that can significantly improve the delay performance of putting and retrieving data in and out of cloud storage. We first focus on measuring the delay performance of a very popular cloud storage service Amazon S3. We establish that there is significant randomness in service times for reading and writing small and medium size objects when assigned distinct keys. We further demonstrate that using erasure coding, parallel connections to storage cloud and limited chunking (i.e., dividing the object into a few smaller objects) together pushes the envelope on service time distributions significantly (e.g., 76%, 80%, and 85% reductions in mean, 90th, and 99th percentiles for 2 Mbyte files) at the expense of additional storage (e.g., 1.75x). However, chunking and erasure coding increase the load and hence the queuing delays while reducing the supportable rate region in number of requests per second per node. Thus, in the second part of our paper we focus on analyzing the delay performance when chunking, FEC, and parallel connections are used together. Based on this analysis, we develop load adaptive algorithms that can pick the best code rate on a per request basis by using off-line computed queue backlog thresholds. The solutions work with homogeneous services with fixed object sizes, chunk sizes, operation type (e.g., read or write) as well as heterogeneous services with mixture of object sizes, chunk sizes, and operation types. We also present a simple greedy solution that opportunistically uses idle connections and picks the erasure coding rate accordingly on the fly. Both backlog and greedy solutions support the full rate region and provide best mean delay performance when compared to the best fixed coding rate policy. Our evaluations show that backlog based solutions achieve better delay performance at higher percentile values than the greedy solution.