OpenRaiser/Intern-Atlas huggingface dataset:
Low and Upper Bound of Approximate Sequence for the Entropy Rate of Binary Hidden Markov Processes
Venue: arXiv cs.IT 2011
Year: 2011

In the paper, the approximate sequence for entropy of some binary hidden Markov models has been found to have two bound sequences, the low bound sequence and the upper bound sequence. The error bias of the approximate sequence is bound by a geometric sequence with a scale factor less than 1 which decreases quickly to zero. It helps to understand the convergence of entropy rate of generic hidden Markov models, and it provides a theoretical base for estimating the entropy rate of some hidden Markov models at any accuracy.
On group feedback vertex set parameterized by the size of the cutset
Venue: arXiv cs.DS 2011
Year: 2011

We study the parameterized complexity of a robust generalization of the classical Feedback Vertex Set problem, namely the Group Feedback Vertex Set problem; we are given a graph G with edges labeled with group elements, and the goal is to compute the smallest set of vertices that hits all cycles of G that evaluate to a non-null element of the group. This problem generalizes not only Feedback Vertex Set, but also Subset Feedback Vertex Set, Multiway Cut and Odd Cycle Transversal. Completing the results of Guillemot [Discr. Opt. 2011], we provide a fixed-parameter algorithm for the parameterization by the size of the cutset only. Our algorithm works even if the group is given as a polynomial-time oracle.
Percentile Ranks and the Integrated Impact Indicator (I3)
Venue: arXiv cs.CY 2011
Year: 2011

We tested Rousseau's (in press) recent proposal to define percentile classes in the case of the Integrated Impact Indicator (I3) so that the largest number in a set always belongs to the highest (100th) percentile rank class. In the case a set of nine uncited papers and one with citation, however, the uncited papers would all be placed in the 90th percentile rank. A lowly-cited document set would thus be advantaged when compared with a highly-cited one. Notwithstanding our reservations, we extended the program for computing I3 in Web-of-Science data (at http://www.leydesdorff.net/software/i3) with this option; the quantiles without a correction are now the default. As Rousseau mentions, excellence indicators (e.g., the top-10%) can be considered as special cases of I3: only two percentile rank classes are distinguished for the evaluation. Both excellence and impact indicators can be tested statistically using the z-test for independent proportions.
Fast B-spline Curve Fitting by L-BFGS
Venue: arXiv cs.GR 2011
Year: 2011

We propose a novel method for fitting planar B-spline curves to unorganized data points. In traditional methods, optimization of control points and foot points are performed in two very time-consuming steps in each iteration: 1) control points are updated by setting up and solving a linear system of equations; and 2) foot points are computed by projecting each data point onto a B-spline curve. Our method uses the L-BFGS optimization method to optimize control points and foot points simultaneously and therefore it does not need to perform either matrix computation or foot point projection in every iteration. As a result, our method is much faster than existing methods.
A Comparative Study of Location Management Schemes: Challenges and Guidelines
Venue: arXiv cs.NI 2011
Year: 2011

One of the key issues in mobile communication is to find the current location of mobile terminal (MT) to deliver the services, which is called as location management (LM). Increasing users and diverse services demand for a high-quality skeleton for LM. As an MT moves within a cellular network, it registers its new location to the nearest base station (BS). When a call arrives for an MT, the network searches the target MT in the area where it was last registered. This paper presents comprehensive classification of existing major LM schemes, their comparative study and factors influencing their performance. Finally, guidelines for developing and rating a LM scheme are suggested with the help of LPCIC rule, which is the main contribution of this paper.
Simulating City-level Airborne Infectious Diseases
Venue: arXiv cs.OH 2011
Year: 2011

With the exponential growth in the world population and the constant increase in human mobility, the danger of outbreaks of epidemics is rising. Especially in high density urban areas such as public transport and transfer points, where people come in close proximity of each other, we observe a dramatic increase in the transmission of airborne viruses and related pathogens. It is essential to have a good understanding of the `transmission highways' in such areas, in order to prevent or to predict the spreading of infectious diseases. The approach we take is to combine as much information as is possible, from all relevant sources and integrate this in a simulation environment that allows for scenario testing and decision support. In this paper we lay out a novel approach to study Urban Airborne Disease spreading by combining traffic information, with geo-spatial data, infection dynamics and spreading characteristics.
Distributed Data Collection and Storage Algorithms for Collaborative Learning Vision Sensor Devices with Applications to Pilgrimage
Venue: arXiv cs.NI 2011
Year: 2011

This work presents novel distributed data collection systems and storage algorithms for collaborative learning wireless sensor networks (WSNs). In a large WSN, consider $n$ collaborative sensor devices distributed randomly to acquire information and learn about a certain field. Such sensors have less power, small bandwidth, and short memory, and they might disappear from the network after certain time of operations. The goal of this work is to design efficient strategies to learn about the field by collecting sensed data from these $n$ sensors with less computational overhead and efficient storage encoding operations. In this data collection system, we propose two distributed data storage algorithms (DSA's) to solve this problem with the means of network flooding and connectivity among sensor devices. In the first algorithm denoted, DSA-I, it's assumed that the total number of nodes is known for each node in the network. We show that this algorithm is efficient in terms of the encoding/decoding operations. Furthermore, every node uses network flooding to disseminate its data throughout the network using mixing time approximately O(n). In the second algorithm denoted, DSA-II, it's assumed that the total number of nodes is not known for each learning sensor, hence dissemination of the data does not depend on the value of $n$. In this case we show that the encoding operations take $O(Cμ^2)$, where $μ$ is the mean degree of the network graph and $C$ is a system parameter. Performance of these two algorithms match the derived theoretical results. Finally, we show how to deploy these algorithms for monitoring and measuring certain phenomenons in American-made camp tents located in Minna field in south-east side of Makkah.
A-GPS Assisted Wi-Fi Access Point Discovery on Mobile Devices for Energy Saving
Venue: arXiv cs.NI 2011
Year: 2011

Mobile devices have been shipped with multiple wireless network interfaces in order to meet their diverse communication and networking demands. In this paper, we propose an A-GPS assisted scheme that discovers the nearest Wi-Fi network access points (APs) by using user's location information. This allows the user to switch to the Wi-Fi interface in an intelligent manner when she/he arrives at the nearest Wi-Fi network AP. Therefore, it avoids the long periods in idle state and greatly reduces the number of unnecessary Wi-Fi scans on the mobile device. The experimental results demonstrate that our scheme effectively saves energy for mobile devices integrated with Wi-Fi and cellular interfaces.
Towards Cost-Effective Storage Provisioning for DBMSs
Venue: arXiv cs.DB 2011
Year: 2011

Data center operators face a bewildering set of choices when considering how to provision resources on machines with complex I/O subsystems. Modern I/O subsystems often have a rich mix of fast, high performing, but expensive SSDs sitting alongside with cheaper but relatively slower (for random accesses) traditional hard disk drives. The data center operators need to determine how to provision the I/O resources for specific workloads so as to abide by existing Service Level Agreements (SLAs), while minimizing the total operating cost (TOC) of running the workload, where the TOC includes the amortized hardware costs and the run time energy costs. The focus of this paper is on introducing this new problem of TOC-based storage allocation, cast in a framework that is compatible with traditional DBMS query optimization and query processing architecture. We also present a heuristic-based solution to this problem, called DOT. We have implemented DOT in PostgreSQL, and experiments using TPC-H and TPC-C demonstrate significant TOC reduction by DOT in various settings.
RTED: A Robust Algorithm for the Tree Edit Distance
Venue: arXiv cs.DB 2011
Year: 2011

We consider the classical tree edit distance between ordered labeled trees, which is defined as the minimum-cost sequence of node edit operations that transform one tree into another. The state-of-the-art solutions for the tree edit distance are not satisfactory. The main competitors in the field either have optimal worst-case complexity, but the worst case happens frequently, or they are very efficient for some tree shapes, but degenerate for others. This leads to unpredictable and often infeasible runtimes. There is no obvious way to choose between the algorithms. In this paper we present RTED, a robust tree edit distance algorithm. The asymptotic complexity of RTED is smaller or equal to the complexity of the best competitors for any input instance, i.e., RTED is both efficient and worst-case optimal. We introduce the class of LRH (Left-Right-Heavy) algorithms, which includes RTED and the fastest tree edit distance algorithms presented in literature. We prove that RTED outperforms all previously proposed LRH algorithms in terms of runtime complexity. In our experiments on synthetic and real world data we empirically evaluate our solution and compare it to the state-of-the-art.
Putting Lipstick on Pig: Enabling Database-style Workflow Provenance
Venue: arXiv cs.DB 2011
Year: 2011

Workflow provenance typically assumes that each module is a "black-box", so that each output depends on all inputs (coarse-grained dependencies). Furthermore, it does not model the internal state of a module, which can change between repeated executions. In practice, however, an output may depend on only a small subset of the inputs (fine-grained dependencies) as well as on the internal state of the module. We present a novel provenance framework that marries database-style and workflow-style provenance, by using Pig Latin to expose the functionality of modules, thus capturing internal state and fine-grained dependencies. A critical ingredient in our solution is the use of a novel form of provenance graph that models module invocations and yields a compact representation of fine-grained workflow provenance. It also enables a number of novel graph transformation operations, allowing to choose the desired level of granularity in provenance querying (ZoomIn and ZoomOut), and supporting "what-if" workflow analytic queries. We implemented our approach in the Lipstick system and developed a benchmark in support of a systematic performance evaluation. Our results demonstrate the feasibility of tracking and querying fine-grained workflow provenance.
T-Learning
Venue: arXiv cs.LG 2011
Year: 2011

Traditional Reinforcement Learning (RL) has focused on problems involving many states and few actions, such as simple grid worlds. Most real world problems, however, are of the opposite type, Involving Few relevant states and many actions. For example, to return home from a conference, humans identify only few subgoal states such as lobby, taxi, airport etc. Each valid behavior connecting two such states can be viewed as an action, and there are trillions of them. Assuming the subgoal identification problem is already solved, the quality of any RL method---in real-world settings---depends less on how well it scales with the number of states than on how well it scales with the number of actions. This is where our new method T-Learning excels, by evaluating the relatively few possible transits from one state to another in a policy-independent way, rather than a huge number of state-action pairs, or states in traditional policy-dependent ways. Illustrative experiments demonstrate that performance improvements of T-Learning over Q-learning can be arbitrarily large.
Automatic Generation of C-code or PLD Circuits under SFC Graphical Environment
Venue: arXiv cs.SY 2011
Year: 2011

This paper proposes a framework for automatic development of control systems from a high level specification based in Grafcet formalism. Grafcet, or Sequential Function Charts (SFC), is a special class of Petri Nets and is becoming the standard representation for sequential control systems. The proposed framework accepts a graphical (through ISaGRAPH) or textual behavioural specification of the control system to be implemented. It follows the usual procedure in software specification: the first step is to formally validate the initial specification. Then the initial specification is translated through automated processes into an implementation. At the moment there are two possible output languages: C and Palasm [1]. The target processor for the C code language are microcontroller based systems that require extended time constrains and access to external peripherals. The goal of including PLD's is the possibility of automatically design mixed hardware and software systems.
A Group Key Management Protocol Based on Weight-Balanced 2-3 Tree for Wireless Sensor Networks
Venue: arXiv cs.CR 2011
Year: 2011

Multicast in Wireless Sensor Networks (WSNs) is an attractive mechanism for delivering data to multiple receivers as it saves bandwidth. To guarantee the security of multicast, the group key is used to encrypt and decrypt the packages. However, providing key management services in WSNs is complicated because sensor nodes possess limited resources of computing, storage and communication. To address the balance between security and limited resources, a multicast group key management protocol based on the weight-balanced 2-3 tree is proposed to generate, distribute, and update the group key securely and efficiently. The decentralized group key management method is employed. A weight-balanced 2-3 key tree is formed in every subgroup. Instead of using the conventional symmetric and non-symmetric encryption algorithms, the Maximum Distance Separable (MDS) code technique is used to distribute the multicast key dynamically. During the key updating, a series of adjustment rules are summarized to keep the tree weight-balanced, where pseudo-nodes as leaves are added to reduce the computation and communication complexity. Compared with some other group key management protocols, our scheme shows higher superiority on security and performance.
Conditional Plausibility Measures and Bayesian Networks
Venue: arXiv cs.AI 2011
Year: 2011

A general notion of algebraic conditional plausibility measures is defined. Probability measures, ranking functions, possibility measures, and (under the appropriate definitions) sets of probability measures can all be viewed as defining algebraic conditional plausibility measures. It is shown that algebraic conditional plausibility measures can be represented using Bayesian networks.
The study of distributed computing algorithms by multithread applications
Venue: arXiv cs.DC 2011
Year: 2011

The material in this note is used as an introduction to distributed algorithms in a four year course on software and automatic control system in the computer technology department of the Komsomolsk-on-Amur state technical university. All our the program examples are written in Borland C/C++ 5.02 for Windows 95/98/2000/NT/XP, and hence suit to compile and execute by Visual C/C++. We consider the following approaches of the distributed computing: the conversion of recursive algorithms to multithread applications, a realization of the pairing algorithm, the building of wave systems by Petri nets and object oriented programming.
Isotropy, entropy, and energy scaling
Venue: arXiv cs.IT 2012
Year: 2012

Two principles explain emergence. First, in the Receipt's reference frame, Deg(S) = 4/3 Deg(R), where Supply S is an isotropic radiative energy source, Receipt R receives S's energy, and Deg is a system's degrees of freedom based on its mean path length. S's 1/3 more degrees of freedom relative to R enables R's growth and increasing complexity. Second, rho(R) = Deg(R) times rho(r), where rho(R) represents the collective rate of R and rho(r) represents the rate of an individual in R: as Deg(R) increases due to the first principle, the multiplier effect of networking in R increases. A universe like ours with isotropic energy distribution, in which both principles are operative, is therefore predisposed to exhibit emergence, and, for reasons shown, a ubiquitous role for the natural logarithm.
A Comparison of Performance Measures for Online Algorithms
Venue: arXiv cs.DS 2012
Year: 2012

This paper provides a systematic study of several proposed measures for online algorithms in the context of a specific problem, namely, the two server problem on three colinear points. Even though the problem is simple, it encapsulates a core challenge in online algorithms which is to balance greediness and adaptability. We examine Competitive Analysis, the Max/Max Ratio, the Random Order Ratio, Bijective Analysis and Relative Worst Order Analysis, and determine how these measures compare the Greedy Algorithm, Double Coverage, and Lazy Double Coverage, commonly studied algorithms in the context of server problems. We find that by the Max/Max Ratio and Bijective Analysis, Greedy is the best of the three algorithms. Under the other measures, Double Coverage and Lazy Double Coverage are better, though Relative Worst Order Analysis indicates that Greedy is sometimes better. Only Bijective Analysis and Relative Worst Order Analysis indicate that Lazy Double Coverage is better than Double Coverage. Our results also provide the first proof of optimality of an algorithm under Relative Worst Order Analysis.
Fusion de classifieurs pour la classification d'images sonar
Venue: arXiv cs.CV 2012
Year: 2012

In this paper, we present some high level information fusion approaches for numeric and symbolic data. We study the interest of such method particularly for classifier fusion. A comparative study is made in a context of sea bed characterization from sonar images. The classi- fication of kind of sediment is a difficult problem because of the data complexity. We compare high level information fusion and give the obtained performance.
A Spectral Algorithm for Learning Hidden Markov Models
Venue: arXiv cs.LG 2012
Year: 2012

Hidden Markov Models (HMMs) are one of the most fundamental and widely used statistical tools for modeling discrete time series. In general, learning HMMs from data is computationally hard (under cryptographic assumptions), and practitioners typically resort to search heuristics which suffer from the usual local optima issues. We prove that under a natural separation condition (bounds on the smallest singular value of the HMM parameters), there is an efficient and provably correct algorithm for learning HMMs. The sample complexity of the algorithm does not explicitly depend on the number of distinct (discrete) observations---it implicitly depends on this quantity through spectral properties of the underlying HMM. This makes the algorithm particularly applicable to settings with a large number of observations, such as those in natural language processing where the space of observation is sometimes the words in a language. The algorithm is also simple, employing only a singular value decomposition and matrix multiplications.
Lower Bounds on Performance of Metric Tree Indexing Schemes for Exact Similarity Search in High Dimensions
Venue: arXiv cs.DS 2012
Year: 2012

Within a mathematically rigorous model, we analyse the curse of dimensionality for deterministic exact similarity search in the context of popular indexing schemes: metric trees. The datasets $X$ are sampled randomly from a domain $Ω$, equipped with a distance, $ρ$, and an underlying probability distribution, $μ$. While performing an asymptotic analysis, we send the intrinsic dimension $d$ of $Ω$ to infinity, and assume that the size of a dataset, $n$, grows superpolynomially yet subexponentially in $d$. Exact similarity search refers to finding the nearest neighbour in the dataset $X$ to a query point $ω\inΩ$, where the query points are subject to the same probability distribution $μ$ as datapoints. Let $\mathscr F$ denote a class of all 1-Lipschitz functions on $Ω$ that can be used as decision functions in constructing a hierarchical metric tree indexing scheme. Suppose the VC dimension of the class of all sets $\{ω\colon f(ω)\geq a\}$, $a\in\R$ is $o(n^{1/4}/\log^2n)$. (In view of a 1995 result of Goldberg and Jerrum, even a stronger complexity assumption $d^{O(1)}$ is reasonable.) We deduce the $Ω(n^{1/4})$ lower bound on the expected average case performance of hierarchical metric-tree based indexing schemes for exact similarity search in $(Ω,X)$. In paricular, this bound is superpolynomial in $d$.
Balanced allocation: Memory performance tradeoffs
Venue: arXiv cs.DS 2012
Year: 2012

Suppose we sequentially put $n$ balls into $n$ bins. If we put each ball into a random bin then the heaviest bin will contain ${\sim}\log n/\log\log n$ balls with high probability. However, Azar, Broder, Karlin and Upfal [SIAM J. Comput. 29 (1999) 180--200] showed that if each time we choose two bins at random and put the ball in the least loaded bin among the two, then the heaviest bin will contain only ${\sim}\log\log n$ balls with high probability. How much memory do we need to implement this scheme? We need roughly $\log\log\log n$ bits per bin, and $n\log\log\log n$ bits in total. Let us assume now that we have limited amount of memory. For each ball, we are given two random bins and we have to put the ball into one of them. Our goal is to minimize the load of the heaviest bin. We prove that if we have $n^{1-δ}$ bits then the heaviest bin will contain at least $Ω(δ\log n/\log\log n)$ balls with high probability. The bound is tight in the communication complexity model.
The Ergodic Capacity of Phase-Fading Interference Networks
Venue: arXiv cs.IT 2012
Year: 2012

We identify the role of equal strength interference links as bottlenecks on the ergodic sum capacity of a $K$ user phase-fading interference network, i.e., an interference network where the fading process is restricted primarily to independent and uniform phase variations while the channel magnitudes are held fixed across time. It is shown that even though there are $K(K-1)$ cross-links, only about $K/2$ disjoint and equal strength interference links suffice to determine the capacity of the network regardless of the strengths of the rest of the cross channels. This scenario is called a \emph{minimal bottleneck state}. It is shown that ergodic interference alignment is capacity optimal for a network in a minimal bottleneck state. The results are applied to large networks. It is shown that large networks are close to bottleneck states with a high probability, so that ergodic interference alignment is close to optimal for large networks. Limitations of the notion of bottleneck states are also highlighted for channels where both the phase and the magnitudes vary with time. It is shown through an example that for these channels, joint coding across different bottleneck states makes it possible to circumvent the capacity bottlenecks.