OpenRaiser/Intern-Atlas huggingface dataset:
Minimum Cycle Basis and All-Pairs Min Cut of a Planar Graph in Subquadratic Time
Venue: arXiv cs.DM 2009
Year: 2009

A minimum cycle basis of a weighted undirected graph $G$ is a basis of the cycle space of $G$ such that the total weight of the cycles in this basis is minimized. If $G$ is a planar graph with non-negative edge weights, such a basis can be found in $O(n^2)$ time and space, where $n$ is the size of $G$. We show that this is optimal if an explicit representation of the basis is required. We then present an $O(n^{3/2}\log n)$ time and $O(n^{3/2})$ space algorithm that computes a minimum cycle basis \emph{implicitly}. From this result, we obtain an output-sensitive algorithm that explicitly computes a minimum cycle basis in $O(n^{3/2}\log n + C)$ time and $O(n^{3/2} + C)$ space, where $C$ is the total size (number of edges and vertices) of the cycles in the basis. These bounds reduce to $O(n^{3/2}\log n)$ and $O(n^{3/2})$, respectively, when $G$ is unweighted. We get similar results for the all-pairs min cut problem since it is dual equivalent to the minimum cycle basis problem for planar graphs. We also obtain $O(n^{3/2}\log n)$ time and $O(n^{3/2})$ space algorithms for finding, respectively, the weight vector and a Gomory-Hu tree of $G$. The previous best time and space bound for these two problems was quadratic. From our Gomory-Hu tree algorithm, we obtain the following result: with $O(n^{3/2}\log n)$ time and $O(n^{3/2})$ space for preprocessing, the weight of a min cut between any two given vertices of $G$ can be reported in constant time. Previously, such an oracle required quadratic time and space for preprocessing. The oracle can also be extended to report the actual cut in time proportional to its size.
Mapping the Chinese Science Citation Database
Venue: arXiv cs.DL 2009
Year: 2009

Methods developed for mapping the journal structures contained in aggregated journal-journal citations in the Science Citation Index are applied to the Chinese Science Citation Database of the Chinese Academy of Sciences. This database covers 991 journals, of which only 37 had originally English titles. Using factor-analytical and graph-analytical techniques we show that this data is dually structured. The main structure is the intellectual organization of the journals in journal groups (as in the international SCI), but the university-based journals provide an institutional layer that orients this structure towards practical ends (e.g., agriculture). The Chinese Science Citation Database exhibits the characteristics of Mode 2 in the production of scientific knowledge more than its western counterparts. The contexts of application lead to correlation (interfactorial complexity) among the components.
The Construction and Globalization of the Knowledge Base in Inter-human Communication Systems
Venue: arXiv cs.CY 2009
Year: 2009

The relationship between the "knowledge base" and the "globalization" of communication systems is discussed from the perspective of communication theory. I argue that inter-human communication takes place at two levels. At the first level information is exchanged and provided with meaning and at the second level meaning can reflexively be communicated. Human language can be considered as the evolutionary achievement which enables us to use these two channels of communication simultaneously. Providing meaning from the perspective of hindsight is a recursive operation: a meaning that makes a difference can be considered as knowledge. If the production of knowledge is socially organized, the perspective of hindsight can further be codified. This adds globalization to the historically stabilized patterns of communications. Globalization can be expected to transform the communications in an evolutionary mode. However, the self-organization of a knowledge-based society remains an expectation with the status of a hypothesis.
Context and Keyword Extraction in Plain Text Using a Graph Representation
Venue: arXiv cs.IR 2009
Year: 2009

Document indexation is an essential task achieved by archivists or automatic indexing tools. To retrieve relevant documents to a query, keywords describing this document have to be carefully chosen. Archivists have to find out the right topic of a document before starting to extract the keywords. For an archivist indexing specialized documents, experience plays an important role. But indexing documents on different topics is much harder. This article proposes an innovative method for an indexing support system. This system takes as input an ontology and a plain text document and provides as output contextualized keywords of the document. The method has been evaluated by exploiting Wikipedia's category links as a termino-ontological resources.
A Note on the Injection Distance
Venue: arXiv cs.IT 2009
Year: 2009

Koetter and Kschischang showed in [R. Koetter and F.R. Kschischang, "Coding for Errors and Erasures in Random Network Coding," IEEE Trans. Inform. Theory, {54(8), 2008] that the network coding counterpart of Gabidulin codes performs asymptotically optimal with respect to the subspace distance. Recently, Silva and Kschischang introduced in [D. Silva and F.R. Kschischang, "On Metrics for Error Correction in Network Coding," To appear in IEEE Trans. Inform. Theory, ArXiv: 0805.3824v4[cs.IT], 2009] the injection distance to give a detailed picture of what happens in noncoherent network coding. We show that the above codes are also asymptotically optimal with respect to this distance.
Robust Video Watermarking using Multi-Band Wavelet Transform
Venue: arXiv cs.IT 2009
Year: 2009

This paper addresses copyright protection as a major security demand in digital marketplaces. Two watermarking techniques are proposed and compared for compressed and uncompressed video with the intention to show the advantages and the possible weaknesses in the schemes working in the frequency domain and in the spatial domain. In this paper a robust video watermarking method is presented. This method embeds data to the specific bands in the wavelet domain using motion estimation approach. The algorithm uses the HL and LH bands to add the watermark where the motion in these bands does not affect the quality of extracted watermark if the video is subjected to different types of malicious attacks. Watermark is embedded in an additive way using random Gaussian distribution in video sequences. The method is tested on different types of video (compressed DVD quality movie and uncompressed digital camera movie). The proposed watermarking method in frequency domain has strong robustness against some attacks such as frame dropping, frame filtering and lossy compression. The experimental results indicate that the similarity measure before and after certain attacks is very close to each other in frequency domain in comparison to the spatial domain.
Gesture Recognition with a Focus on Important Actions by Using a Path Searching Method in Weighted Graph
Venue: arXiv cs.CV 2009
Year: 2009

This paper proposes a method of gesture recognition with a focus on important actions for distinguishing similar gestures. The method generates a partial action sequence by using optical flow images, expresses the sequence in the eigenspace, and checks the feature vector sequence by applying an optimum path-searching method of weighted graph to focus the important actions. Also presented are the results of an experiment on the recognition of similar sign language words.
High Availability Cluster System for Local Disaster Recovery with Markov Modeling Approach
Venue: arXiv cs.DC 2009
Year: 2009

The need for high availability (HA) and disaster recovery (DR) in IT environment is more stringent than most of the other sectors of enterprises. Many businesses require the availability of business-critical applications 24 hours a day, seven days a week, and can afford no data loss in the event of a disaster. It is vital that the IT infrastructure is resilient with regard to disruption, even site failures, and that business operations can continue without significant impact. As a result, DR has gained great importance in IT. Clustering of multiple industries standard servers together to allow workload sharing and fail-over capabilities is a low cost approach. In this paper, we present the availability model through Semi-Markov Process (SMP) and also analyze the difference in downtime of the SMP model and the approximate Continuous Time Markov Chain (CTMC) model. To acquire system availability, we perform numerical analysis and SHARPE tool evaluation.
Markovian Testing Equivalence and Exponentially Timed Internal Actions
Venue: arXiv cs.LO 2009
Year: 2009

In the theory of testing for Markovian processes developed so far, exponentially timed internal actions are not admitted within processes. When present, these actions cannot be abstracted away, because their execution takes a nonzero amount of time and hence can be observed. On the other hand, they must be carefully taken into account, in order not to equate processes that are distinguishable from a timing viewpoint. In this paper, we recast the definition of Markovian testing equivalence in the framework of a Markovian process calculus including exponentially timed internal actions. Then, we show that the resulting behavioral equivalence is a congruence, has a sound and complete axiomatization, has a modal logic characterization, and can be decided in polynomial time.
Peer-to-Peer Cloud Provisioning: Service Discovery and Load-Balancing
Venue: arXiv cs.DC 2009
Year: 2009

This chapter presents: (i) a layered peer-to-peer Cloud provisioning architecture; (ii) a summary of the current state-of-the-art in Cloud provisioning with particular emphasis on service discovery and load-balancing; (iii) a classification of the existing peer-to-peer network management model with focus on extending the DHTs for indexing and managing complex provisioning information; and (iv) the design and implementation of novel, extensible software fabric (Cloud peer) that combines public/private clouds, overlay networking and structured peer-to-peer indexing techniques for supporting scalable and self-managing service discovery and load-balancing in Cloud computing environments. Finally, an experimental evaluation is presented that demonstrates the feasibility of building next generation Cloud provisioning systems based on peer-to-peer network management and information dissemination models. The experimental test-bed has been deployed on a public cloud computing platform, Amazon EC2, which demonstrates the effectiveness of the proposed peer-to-peer Cloud provisioning software fabric.
Survey of clustering algorithms for MANET
Venue: arXiv cs.DC 2009
Year: 2009

Many clustering schemes have been proposed for ad hoc networks. A systematic classification of these clustering schemes enables one to better understand and make improvements. In mobile ad hoc networks, the movement of the network nodes may quickly change the topology resulting in the increase of the overhead message in topology maintenance. Protocols try to keep the number of nodes in a cluster around a pre-defined threshold to facilitate the optimal operation of the medium access control protocol. The clusterhead election is invoked on-demand, and is aimed to reduce the computation and communication costs. A large variety of approaches for ad hoc clustering have been developed by researchers which focus on different performance metrics. This paper presents a survey of different clustering schemes.
Formal Aspects of Grid Brokering
Venue: arXiv cs.DC 2009
Year: 2009

Coordination in distributed environments, like Grids, involves selecting the most appropriate services, resources or compositions to carry out the planned activities. Such functionalities appear at various levels of the infrastructure and in various means forming a blurry domain, where it is hard to see how the participating components are related and what their relevant properties are. In this paper we focus on a subset of these problems: resource brokering in Grid middleware. This paper aims at establishing a semantical model for brokering and related activities by defining brokering agents at three levels of the Grid middleware for resource, host and broker selection. The main contribution of this paper is the definition and decomposition of different brokering components in Grids by providing a formal model using Abstract State Machines.
Pulse Shaping, Localization and the Approximate Eigenstructure of LTV Channels
Venue: arXiv cs.IT 2009
Year: 2009

In this article we show the relation between the theory of pulse shaping for WSSUS channels and the notion of approximate eigenstructure for time-varying channels. We consider pulse shaping for a general signaling scheme, called Weyl-Heisenberg signaling, which includes OFDM with cyclic prefix and OFDM/OQAM. The pulse design problem in the view of optimal WSSUS--averaged SINR is an interplay between localization and "orthogonality". The localization problem itself can be expressed in terms of eigenvalues of localization operators and is intimately connected to the concept of approximate eigenstructure of LTV channel operators. In fact, on the L_2-level both are equivalent as we will show. The concept of "orthogonality" in turn can be related to notion of tight frames. The right balance between these two sides is still an open problem. However, several statements on achievable values of certain localization measures and fundamental limits on SINR can already be made as will be shown in the paper.
JSC : A JavaScript Object System
Venue: arXiv cs.PL 2009
Year: 2009

The JSC language is a superset of JavaScript designed to ease the development of large web applications. This language extends JavaScripts own object system by isolating code in a class declaration, simplifying multiple inheritance and using method implementation agreements.
Representing human and machine dictionaries in Markup languages
Venue: arXiv cs.CL 2009
Year: 2009

In this chapter we present the main issues in representing machine readable dictionaries in XML, and in particular according to the Text Encoding Dictionary (TEI) guidelines.
New Learning and Testing Problems for Read-Once Functions
Venue: arXiv cs.CC 2009
Year: 2009

In the paper, we consider several types of queries for classical and new problems of learning and testing read-once functions. In several cases, the border between polynomial and exponential complexities is obtained.
Speech Recognition Oriented Vowel Classification Using Temporal Radial Basis Functions
Venue: arXiv cs.CL 2009
Year: 2009

The recent resurgence of interest in spatio-temporal neural network as speech recognition tool motivates the present investigation. In this paper an approach was developed based on temporal radial basis function "TRBF" looking to many advantages: few parameters, speed convergence and time invariance. This application aims to identify vowels taken from natural speech samples from the Timit corpus of American speech. We report a recognition accuracy of 98.06 percent in training and 90.13 in test on a subset of 6 vowel phonemes, with the possibility to expend the vowel sets in future.
Alternate methods of evaluation for web sites concordant to IAS/IFRS Standards
Venue: arXiv cs.OH 2009
Year: 2009

This work has as the principal theme, the study, analysis and implementation of the methodology for use the web sites in e-commerce. The authors try to deal with particular methodological and applied aspects inherent in the analysis of data from the interaction of man-Internet (Web-mining). The research methodology of this work will be focused on a prevalent optic multidisciplinary research based on the pillars of data mining and Web mining. The explosion of Internet and electronic commerce has made the most of business to have its own website. A company may engage internal costs for the development and operation of their website. The website can be designed for internal access (in which case it can be used for presentation and data storage company policies with references of customers) or for external access (they are created and used for promotional and advertising products and services company). The objective of this research, primarily concerns the definition of a repertoire of tools in analyzing e-business through the development process for web-usage mining; 2nd objective is oriented to management, recognizing and evaluating the web-sites in accountancy, as property intangible, which is a special case and very little studied in economic literature financial specialty, the authors try to achieve a national and international accounting treatment of the creation and development of web-sites.
Advanced Technology in Speech Disorder Therapy of Romanian Language
Venue: arXiv cs.OH 2009
Year: 2009

One of the key challenges of the society development is related to public health and one of its specific targets includes better treatments of diseases. It is true that there are affections which by their nature do not endanger the life of a person, but they may have negative implications during his/her lifetime. Various language or speech disorders are part of this category. Discovered and treated in time, they can be corrected, most often in childhood. Because the Romanian language is a phonetic one that has its own special linguistic particularities, there is a real need to develop advanced information systems, which can be used to assist and help specialists in different speech disorders therapy. The aim of this paper is to present a few CBTS developed for the treatment of various language and speech disorders specific to the Romanian language.
Retail Market analysis in targeting sales based on Consumer Behaviour using Fuzzy Clustering - A Rule Based Mode
Venue: arXiv cs.OH 2009
Year: 2009

Product Bundling and offering products to customers is of critical importance in retail marketing. In general, product bundling and offering products to customers involves two main issues, namely identification of product taste according to demography and product evaluation and selection to increase sales. The former helps to identify, analyze and understand customer needs according to the demo-graphical characteristics and correspondingly transform them into a set of specifications and offerings for people. The latter, concerns with how to determine the best product strategy and offerings for the customer in helping the retail market to improve their sales. Existing research has focused only on identifying patterns for a particular dataset and for a particular setting. This work aims to develop an explicit decision support for the retailers to improve their product segmentation for different settings based on the people characteristics and thereby promoting sales by efficient knowledge discovery from the existing sales and product records. The work presents a framework, which models an association relation mapping between the customers and the clusters of products they purchase in an existing location and helps in finding rules for a new location. The methodology is based on the integration of popular data mining approaches such as clustering and association rule mining. It focuses on the discovery of rules that vary according to the economic and demographic characteristics and concentrates on marketing of products based on the population.
New Model of Network- a Future Aspect of the Computer Networks
Venue: arXiv cs.NI 2009
Year: 2009

As the number and size of the Network increases, the deficiencies persist, including network security problems. But there is no shortage of technologies offered as universal remedy - EIGRP,BGP, OSPF, VoIP, IPv6, IPTV, MPLS, WiFi, to name a few. There are multiple factors for the current situation. Now a day during emergent and blossoming stages of network development is no longer sufficient when the networks are mature and have become everyday tool for social and business interactions. A new model of network is necessary to find solutions for today's pressing problems, especially those related to network security. In this paper out factors leading to current stagnation discusses critical assumptions behind current networks, how many of them are no longer valid and have become barriers for implementing real solutions. The paper concludes by offering new directions for future needs and solving current challenges.
New [48,16,16] Optimal Linear Binary Block Code
Venue: arXiv cs.IT 2009
Year: 2009

A new [48,16,16] optimal linear binary block code is given. To get this code a general construction is used which is also described in this paper. The construction of this new code settles an conjecture mentioned in a 2008 paper by Janosov et al. where the authors found an new optimal [47,15,16]-code, which is relevant to the applied construction.
Scope Logic: Extending Hoare Logic for Pointer Program Verification
Venue: arXiv cs.LO 2009
Year: 2009

This paper presents an extension to Hoare logic for pointer program verification. First, the Logic for Partial Function (LPF) used by VDM is extended to specify memory access using pointers and memory layout of composite types. Then, the concepts of data-retrieve functions (DRF) and memory-scope functions (MSF) are introduced in this paper. People can define DRFs to retrieve abstract values from interconnected concrete data objects. The definition of the corresponding MSF of a DRF can be derived syntactically from the definition of the DRF. This MSF computes the set of memory units accessed when the DRF retrieves an abstract value. This memory unit set is called the memory scope of the abstract value. Finally, the proof rule of assignment statements in Hoare's logic is modified to deal with pointers. The basic idea is that a virtual value keeps unmodified as long as no memory unit in its scope is over-written. Another proof rule is added for memory allocation statements. The consequence rule and the rules for control-flow statements are slightly modified. They are essentially same as their original version in Hoare logic. An example is presented to show the efficacy of this logic. We also give some heuristics on how to verify pointer programs.
Discovery of Elliptic Curve Cryptographic Private Key in O(n)
Venue: arXiv cs.CR 2009
Year: 2009

An algorithm is presented that in context of public key use of Elliptic Curve Cryptography allows discovery of the private key in worst case O(n).
Demand-Supply Optimization with Risk Management for a Multi-Connection Water Reservoir Network
Venue: arXiv cs.DS 2009
Year: 2009

In this paper, we propose a framework to solve a demand-supply optimization problem of long-term water resource allocation on a multi-connection reservoir network which, in two aspects, is different to the problem considered in previous works. First, while all previous works consider a problem where each reservoir can transfer water to only one fixed reservoir, we consider a multi-connection network being constructed in Thailand in which each reservoir can transfer water to many reservoirs in one period of time. Second, a demand-supply plan considered here is static, in contrast to a dynamic policy considered in previous works. Moreover, in order to efficiently develop a long-term static plan, a severe loss (a risk) is taken into account, i.e. a risk occurs if the real amount of water stored in each reservoir in each time period is less than what planned by the optimizer. The multi-connection function and the risk make the problem rather complex such that traditional stochastic dynamic programming and deterministic/heuristic approaches are inappropriate. Our framework is based on a novel convex programming formulation in which stochastic information can be naturally taken into account and an optimal solution is guaranteed to be found efficiently. Extensive experimental results show promising results of the framework.