OpenRaiser/Intern-Atlas huggingface dataset:
Computation in Large-Scale Scientific and Internet Data Applications is a Focus of MMDS 2010
Venue: arXiv cs.DS 2010
Year: 2010

The 2010 Workshop on Algorithms for Modern Massive Data Sets (MMDS 2010) was held at Stanford University, June 15--18. The goals of MMDS 2010 were (1) to explore novel techniques for modeling and analyzing massive, high-dimensional, and nonlinearly-structured scientific and Internet data sets; and (2) to bring together computer scientists, statisticians, applied mathematicians, and data analysis practitioners to promote cross-fertilization of ideas. MMDS 2010 followed on the heels of two previous MMDS workshops. The first, MMDS 2006, addressed the complementary perspectives brought by the numerical linear algebra and theoretical computer science communities to matrix algorithms in modern informatics applications; and the second, MMDS 2008, explored more generally fundamental algorithmic and statistical challenges in modern large-scale data analysis.
Travel Time Estimation Using Floating Car Data
Venue: arXiv cs.LG 2010
Year: 2010

This report explores the use of machine learning techniques to accurately predict travel times in city streets and highways using floating car data (location information of user vehicles on a road network). The aim of this report is twofold, first we present a general architecture of solving this problem, then present and evaluate few techniques on real floating car data gathered over a month on a 5 Km highway in New Delhi.
Differential Privacy versus Quantitative Information Flow
Venue: arXiv cs.IT 2010
Year: 2010

Differential privacy is a notion of privacy that has become very popular in the database community. Roughly, the idea is that a randomized query mechanism provides sufficient privacy protection if the ratio between the probabilities of two different entries to originate a certain answer is bound by e^ε. In the fields of anonymity and information flow there is a similar concern for controlling information leakage, i.e. limiting the possibility of inferring the secret information from the observables. In recent years, researchers have proposed to quantify the leakage in terms of the information-theoretic notion of mutual information. There are two main approaches that fall in this category: One based on Shannon entropy, and one based on Rényi's min entropy. The latter has connection with the so-called Bayes risk, which expresses the probability of guessing the secret. In this paper, we show how to model the query system in terms of an information-theoretic channel, and we compare the notion of differential privacy with that of mutual information. We show that the notion of differential privacy is strictly stronger, in the sense that it implies a bound on the mutual information, but not viceversa.
Selection in Scientific Networks
Venue: arXiv cs.SI 2010
Year: 2010

One of the most interesting scientific challenges nowadays deals with the analysis and the understanding of complex networks' dynamics. A major issue is the definition of new frameworks for the exploration of the dynamics at play in real dynamic networks. Here, we focus on scientific communities by analyzing the "social part" of Science through a descriptive approach that aims at identifying the social determinants (e.g. goals and potential interactions among individuals) behind the emergence and the resilience of scientific communities. We consider that scientific communities are at the same time communities of practice (through co-authorship) and that they exist also as representations in the scientists' mind, since references to other scientists' works is not merely an objective link to a relevant work, but it reveals social objects that one manipulates and refers to. In this paper we identify the patterns about the evolution of a scientific field by analyzing a portion of the arXiv repository covering a period of 10 years of publications in physics. As a citation represents a deliberative selection related to the relevance of a work in its scientific domain, our analysis approaches the co-existence between co-authorship and citation behaviors in a community by focusing on the most proficient and cited authors interactions patterns. We focus in turn, on how these patterns are affected by the selection process of citations. Such a selection a) produces self-organization because it is played by a group of individuals which act, compete and collaborate in a common environment in order to advance Science and b) determines the success (emergence) of both topics and scientists working on them. The dataset is analyzed a) at a global level, e.g. the network evolution, b) at the meso-level, e.g. communities emergence, and c) at a micro-level, e.g. nodes' aggregation patterns.
Encryption of Binary and Non-Binary Data Using Chained Hadamard Transforms
Venue: arXiv cs.CR 2010
Year: 2010

This paper presents a new chaining technique for the use of Hadamard transforms for encryption of both binary and non-binary data. The lengths of the input and output sequence need not be identical. The method may be used also for hashing.
Impact of Mistiming on the Achievable Information Rate of Rake Receivers in DS-UWB Systems
Venue: arXiv cs.IT 2010
Year: 2010

In this paper, we investigate the impact of mistiming on the performance of Rake receivers in direct-sequence ultra-wideband (DS-UWB) systems from the perspective of the achievable information rate. A generalized expression for the performance degradation due to mistiming is derived. Monte Carlo simulations based on this expression are then conducted, which demonstrate that the performance loss has little relationship with the target achievable information rate, but varies significantly with the system bandwidth and the multipath diversity order, which reflects design trade-offs among the system timing requirement, the bandwidth and the implementation complexity. In addition, the performance degradations of Rake receivers with different multipath component selection schemes and combining techniques are compared. Among these receivers, the widely used maximal ratio combining (MRC) selective-Rake (S-Rake) suffers the largest performance loss in the presence of mistiming.
Non-redundant random generation from weighted context-free languages
Venue: arXiv cs.DS 2010
Year: 2010

We address the non-redundant random generation of k words of length n from a context-free language. Additionally, we want to avoid a predefined set of words. We study the limits of a rejection-based approach, whose time complexity is shown to grow exponentially in k in some cases. We propose an alternative recursive algorithm, whose careful implementation allows for a non-redundant generation of k words of size n in O(kn log n) arithmetic operations after the precomputation of O(n) numbers. The overall complexity is therefore dominated by the generation of k words, and the non-redundancy comes at a negligible cost.
Online traffic state estimation based on floating car data
Venue: arXiv cs.OH 2010
Year: 2010

Besides the traditional data collection by stationary detectors, recent advances in wireless and sensor technologies have promoted new potentials for a vehicle-based data collection and local dissemination of information. By means of microscopic traffic simulations we study the problem of online estimation of the current traffic situation based on floating car data. Our focus is on the estimation on the up- and downstream jam fronts determining the extension of traffic congestion. We study the impact of delayed information transmission by short-range communication via wireless LAN in contrast to instantaneous information transmission to the roadside units by means of mobile radio. The delayed information transmission leads to systematic estimation errors which cannot be compensated for by a higher percentage of probe vehicles. Additional flow measurements from stationary detectors allow for a model-based prediction which is effective for much lower floating car percentages than 1%.
How I won the "Chess Ratings - Elo vs the Rest of the World" Competition
Venue: arXiv cs.LG 2010
Year: 2010

This article discusses in detail the rating system that won the kaggle competition "Chess Ratings: Elo vs the rest of the world". The competition provided a historical dataset of outcomes for chess games, and aimed to discover whether novel approaches can predict the outcomes of future games, more accurately than the well-known Elo rating system. The winning rating system, called Elo++ in the rest of the article, builds upon the Elo rating system. Like Elo, Elo++ uses a single rating per player and predicts the outcome of a game, by using a logistic curve over the difference in ratings of the players. The major component of Elo++ is a regularization technique that avoids overfitting these ratings. The dataset of chess games and outcomes is relatively small and one has to be careful not to draw "too many conclusions" out of the limited data. Many approaches tested in the competition showed signs of such an overfitting. The leader-board was dominated by attempts that did a very good job on a small test dataset, but couldn't generalize well on the private hold-out dataset. The Elo++ regularization takes into account the number of games per player, the recency of these games and the ratings of the opponents. Finally, Elo++ employs a stochastic gradient descent scheme for training the ratings, and uses only two global parameters (white's advantage and regularization constant) that are optimized using cross-validation.
Improving random number generators by chaotic iterations. Application in data hiding
Venue: arXiv cs.CR 2010
Year: 2010

In this paper, a new pseudo-random number generator (PRNG) based on chaotic iterations is proposed. This method also combines the digits of two XORshifts PRNGs. The statistical properties of this new generator are improved: the generated sequences can pass all the DieHARD statistical test suite. In addition, this generator behaves chaotically, as defined by Devaney. This makes our generator suitable for cryptographic applications. An illustration in the field of data hiding is presented and the robustness of the obtained data hiding algorithm against attacks is evaluated.
Distributed Detection over Random Networks: Large Deviations Performance Analysis
Venue: arXiv cs.IT 2010
Year: 2010

We study the large deviations performance, i.e., the exponential decay rate of the error probability, of distributed detection algorithms over random networks. At each time step $k$ each sensor: 1) averages its decision variable with the neighbors' decision variables; and 2) accounts on-the-fly for its new observation. We show that distributed detection exhibits a "phase change" behavior. When the rate of network information flow (the speed of averaging) is above a threshold, then distributed detection is asymptotically equivalent to the optimal centralized detection, i.e., the exponential decay rate of the error probability for distributed detection equals the Chernoff information. When the rate of information flow is below a threshold, distributed detection achieves only a fraction of the Chernoff information rate; we quantify this achievable rate as a function of the network rate of information flow. Simulation examples demonstrate our theoretical findings on the behavior of distributed detection over random networks.
Automatic Estimation of the Exposure to Lateral Collision in Signalized Intersections using Video Sensors
Venue: arXiv cs.AI 2010
Year: 2010

Intersections constitute one of the most dangerous elements in road systems. Traffic signals remain the most common way to control traffic at high-volume intersections and offer many opportunities to apply intelligent transportation systems to make traffic more efficient and safe. This paper describes an automated method to estimate the temporal exposure of road users crossing the conflict zone to lateral collision with road users originating from a different approach. This component is part of a larger system relying on video sensors to provide queue lengths and spatial occupancy that are used for real time traffic control and monitoring. The method is evaluated on data collected during a real world experiment.
Distributed and Optimal Reduced Primal-Dual Algorithm for Uplink OFDM Resource Allocation
Venue: arXiv cs.NI 2010
Year: 2010

Orthogonal Frequency Division Multiplexing (OFDM) is the key component of many emerging broadband wireless access standards. The resource allocation in OFDM uplink, however, is challenging due to heterogeneity of users' Quality of Service requirements, channel conditions, and individual resource constraints. We formulate the resource allocation problem as a non-strictly convex optimization problem, which typically has multiple global optimal solutions. We then propose a reduced primal-dual algorithm, which is distributed, low in computational complexity, and probably globally convergent to a global optimal solution. The performance of the algorithm is studied through a realistic OFDM simulator. Compared with the previously proposed centralized optimal algorithm, our algorithm not only significantly reduces the message overhead but also requires less iterations to converge.
Upper Tag Ontology (UTO) For Integrating Social Tagging Data
Venue: arXiv cs.IR 2010
Year: 2010

Data integration and mediation have become central concerns of information technology over the past few decades. With the advent of the Web and the rapid increases in the amount of data and the number of Web documents and users, researchers have focused on enhancing the interoperability of data through the development of metadata schemes. Other researchers have looked to the wealth of metadata generated by bookmarking sites on the Social Web. While several existing ontologies capitalize on the semantics of metadata created by tagging activities, the Upper Tag Ontology (UTO) emphasizes the structure of tagging activities to facilitate modeling of tagging data and the integration of data from different bookmarking sites as well as the alignment of tagging ontologies. UTO is described and its utility in harvesting, modeling, integrating, searching and analyzing data is demonstrated with metadata harvested from three major social tagging systems (Delicious, Flickr and YouTube).
Weighted citation: An indicator of an article's prestige
Venue: arXiv cs.DL 2010
Year: 2010

We propose using the technique of weighted citation to measure an article's prestige. The technique allocates a different weight to each reference by taking into account the impact of citing journals and citation time intervals. Weighted citation captures prestige, whereas citation counts capture popularity. We compare the value variances for popularity and prestige for articles published in the Journal of the American Society for Information Science and Technology from 1998 to 2007, and find that the majority have comparable status.
Tight Bounds for Lp Samplers, Finding Duplicates in Streams, and Related Problems
Venue: arXiv cs.DS 2010
Year: 2010

In this paper, we present near-optimal space bounds for Lp-samplers. Given a stream of updates (additions and subtraction) to the coordinates of an underlying vector x \in R^n, a perfect Lp sampler outputs the i-th coordinate with probability |x_i|^p/||x||_p^p. In SODA 2010, Monemizadeh and Woodruff showed polylog space upper bounds for approximate Lp-samplers and demonstrated various applications of them. Very recently, Andoni, Krauthgamer and Onak improved the upper bounds and gave a O(ε^{-p} log^3 n) space εrelative error and constant failure rate Lp-sampler for p \in [1,2]. In this work, we give another such algorithm requiring only O(ε^{-p} log^2 n) space for p \in (1,2). For p \in (0,1), our space bound is O(ε^{-1} log^2 n), while for the $p=1$ case we have an O(log(1/ε)ε^{-1} log^2 n) space algorithm. We also give a O(log^2 n) bits zero relative error L0-sampler, improving the O(log^3 n) bits algorithm due to Frahling, Indyk and Sohler. As an application of our samplers, we give better upper bounds for the problem of finding duplicates in data streams. In case the length of the stream is longer than the alphabet size, L1 sampling gives us an O(log^2 n) space algorithm, thus improving the previous O(log^3 n) bound due to Gopalan and Radhakrishnan. In the second part of our work, we prove an Omega(log^2 n) lower bound for sampling from 0, \pm 1 vectors (in this special case, the parameter p is not relevant for Lp sampling). This matches the space of our sampling algorithms for constant ε> 0. We also prove tight space lower bounds for the finding duplicates and heavy hitters problems. We obtain these lower bounds using reductions from the communication complexity problem augmented indexing.
Rewriting and Well-Definedness within a Proof System
Venue: arXiv cs.LO 2010
Year: 2010

Term rewriting has a significant presence in various areas, not least in automated theorem proving where it is used as a proof technique. Many theorem provers employ specialised proof tactics for rewriting. This results in an interleaving between deduction and computation (i.e., rewriting) steps. If the logic of reasoning supports partial functions, it is necessary that rewriting copes with potentially ill-defined terms. In this paper, we provide a basis for integrating rewriting with a deductive proof system that deals with well-definedness. The definitions and theorems presented in this paper are the theoretical foundations for an extensible rewriting-based prover that has been implemented for the set theoretical formalism Event-B.
General Recursion and Formal Topology
Venue: arXiv cs.LO 2010
Year: 2010

It is well known that general recursion cannot be expressed within Martin-Loef's type theory and various approaches have been proposed to overcome this problem still maintaining the termination of the computation of the typable terms. In this work we propose a new approach to this problem based on the use of inductively generated formal topologies.
Optimal competitive online ray search with an error-prone robot
Venue: arXiv cs.CG 2010
Year: 2010

We consider the problem of finding a door along a wall with a blind robot that neither knows the distance to the door nor the direction towards of the door. This problem can be solved with the well-known doubling strategy yielding an optimal competitive factor of 9 with the assumption that the robot does not make any errors during its movements. We study the case that the robot's movement is erroneous. In this case the doubling strategy is no longer optimal. We present optimal competitive strategies that take the error assumption into account. The analysis technique can be applied to different error models.
Computing Differential Equations for Integrals Associated to Smooth Fano Polytopes
Venue: arXiv cs.SC 2010
Year: 2010

We give an approximate algorithm of computing holonomic systems of linear differential equations for definite integrals with parameters. We show that this algorithm gives a correct answer in finite steps, but we have no general stopping condition. We apply the approximate method to find differential equations for integrals associated to smooth Fano polytopes. They are interested in the study of K3 surfaces and the toric mirror symmetry. In this class of integrals, we can apply Stienstra's rank formula to our algorithm, which gives a stopping condition of the approximate algorithm.
A new conception for computing gröbner basis and its applications
Venue: arXiv cs.SC 2010
Year: 2010

This paper presents a conception for computing gröbner basis. We convert some of gröbner-computing algorithms, e.g., F5, extended F5 and GWV algorithms into a special type of algorithm. The new algorithm's finite termination problem can be described by equivalent conditions, so all the above algorithms can be determined when they terminate finitely. At last, a new criterion is presented. It is an improvement for the Rewritten and Signature Criterion.
Ontology-based Queries over Cancer Data
Venue: arXiv cs.AI 2010
Year: 2010

The ever-increasing amount of data in biomedical research, and in cancer research in particular, needs to be managed to support efficient data access, exchange and integration. Existing software infrastructures, such caGrid, support access to distributed information annotated with a domain ontology. However, caGrid's current querying functionality depends on the structure of individual data resources without exploiting the semantic annotations. In this paper, we present the design and development of an ontology-based querying functionality that consists of: the generation of OWL2 ontologies from the underlying data resources metadata and a query rewriting and translation process based on reasoning, which converts a query at the domain ontology level into queries at the software infrastructure level. We present a detailed analysis of our approach as well as an extensive performance evaluation. While the implementation and evaluation was performed for the caGrid infrastructure, the approach could be applicable to other model and metadata-driven environments for data sharing.
Mining Multi-Level Frequent Itemsets under Constraints
Venue: arXiv cs.DB 2010
Year: 2010

Mining association rules is a task of data mining, which extracts knowledge in the form of significant implication relation of useful items (objects) from a database. Mining multilevel association rules uses concept hierarchies, also called taxonomies and defined as relations of type 'is-a' between objects, to extract rules that items belong to different levels of abstraction. These rules are more useful, more refined and more interpretable by the user. Several algorithms have been proposed in the literature to discover the multilevel association rules. In this article, we are interested in the problem of discovering multi-level frequent itemsets under constraints, involving the user in the research process. We proposed a technique for modeling and interpretation of constraints in a context of use of concept hierarchies. Three approaches for discovering multi-level frequent itemsets under constraints were proposed and discussed: Basic approach, "Test and Generate" approach and Pruning based Approach.
Strategic programming on graph rewriting systems
Venue: arXiv cs.PL 2010
Year: 2010

We describe a strategy language to control the application of graph rewriting rules, and show how this language can be used to write high-level declarative programs in several application areas. This language is part of a graph-based programming tool built within the port-graph transformation and visualisation environment PORGY.
Automated Symbolic Analysis of ARBAC-Policies (Extended Version)
Venue: arXiv cs.CR 2010
Year: 2010

One of the most widespread framework for the management of access-control policies is Administrative Role Based Access Control (ARBAC). Several automated analysis techniques have been proposed to help maintaining desirable security properties of ARBAC policies. One limitation of many available techniques is that the sets of users and roles are bounded. In this paper, we propose a symbolic framework to overcome this difficulty. We design an automated security analysis technique, parametric in the number of users and roles, by adapting recent methods for model checking infinite state systems that use first-order logic and state-of-the-art theorem proving techniques. Preliminary experiments with a prototype implementations seem to confirm the scalability of our technique.
Manipulating Multistage Interconnection Networks Using Fundamental Arrangements
Venue: arXiv cs.NI 2010
Year: 2010

Optimizing interconnection networks is a prime object in switching schemes. In this work the authors present a novel approach for obtaining a required channel arrangement in a multi-stage interconnection network, using a new concept - a fundamental arrangement. The fundamental arrangement is an initial N-1 stage switch arrangement that allows obtaining any required output channel arrangement given an input arrangement, using N/2 binary switches at each stage. The paper demonstrates how a fundamental arrangement can be achieved and how, once this is done, any required arrangement may be obtained within 2(N-1) steps.