OpenRaiser/Intern-Atlas huggingface dataset:
Fast Rendezvous with Advice
Venue: arXiv cs.DS 2014
Year: 2014

Two mobile agents, starting from different nodes of an $n$-node network at possibly different times, have to meet at the same node. This problem is known as rendezvous. Agents move in synchronous rounds using a deterministic algorithm. In each round, an agent decides to either remain idle or to move to one of the adjacent nodes. Each agent has a distinct integer label from the set $\{1,...,L\}$, which it can use in the execution of the algorithm, but it does not know the label of the other agent. If $D$ is the distance between the initial positions of the agents, then $Ω(D)$ is an obvious lower bound on the time of rendezvous. However, if each agent has no initial knowledge other than its label, time $O(D)$ is usually impossible to achieve. We study the minimum amount of information that has to be available a priori to the agents to achieve rendezvous in optimal time $Θ(D)$. This information is provided to the agents at the start by an oracle knowing the entire instance of the problem, i.e., the network, the starting positions of the agents, their wake-up rounds, and both of their labels. The oracle helps the agents by providing them with the same binary string called advice, which can be used by the agents during their navigation. The length of this string is called the size of advice. Our goal is to find the smallest size of advice which enables the agents to meet in time $Θ(D)$. We show that this optimal size of advice is $Θ(D\log(n/D)+\log\log L)$. The upper bound is proved by constructing an advice string of this size, and providing a natural rendezvous algorithm using this advice that works in time $Θ(D)$ for all networks. The matching lower bound, which is the main contribution of this paper, is proved by exhibiting classes of networks for which it is impossible to achieve rendezvous in time $Θ(D)$ with smaller advice.
When and Where: Predicting Human Movements Based on Social Spatial-Temporal Events
Venue: arXiv cs.SI 2014
Year: 2014

Predicting both the time and the location of human movements is valuable but challenging for a variety of applications. To address this problem, we propose an approach considering both the periodicity and the sociality of human movements. We first define a new concept, Social Spatial-Temporal Event (SSTE), to represent social interactions among people. For the time prediction, we characterise the temporal dynamics of SSTEs with an ARMA (AutoRegressive Moving Average) model. To dynamically capture the SSTE kinetics, we propose a Kalman Filter based learning algorithm to learn and incrementally update the ARMA model as a new observation becomes available. For the location prediction, we propose a ranking model where the periodicity and the sociality of human movements are simultaneously taken into consideration for improving the prediction accuracy. Extensive experiments conducted on real data sets validate our proposed approach.
Bi-directioal Motion Detection: A Neural Intelligent Model For Perception of Cognitive Robots
Venue: arXiv cs.RO 2014
Year: 2014

In this paper, a new neuronal circuit, based on the spiking neuronal network model, is proposed in order to detect the movement direction of dynamic objects wandering around cognitive robots. Capability of our new approach in bi-directional movement detection is beholden to its symmetric configuration of the proposed circuit. With due attention to magnificence of handling of blocking problems in neuronal networks such as epilepsy, mounting both excitatory and inhibitory stimuli has been taken into account. Investigations upon applied implementation of aforementioned strategy on PIONEER cognitive robot reveals that the strategy leads to alleviation of potential level in the sensory networks. Furthermore, investigation on intrinsic delay of the circuit reveals not only the noticeable switching rate which could be acquired but the high-efficient coupling of the circuit with the other high-speed ones.
Noiseless coding theorem proved by induction for finite stationary memoryless information sources
Venue: arXiv cs.IT 2014
Year: 2014

Noiseless coding theorem for finite stationary memoryless information sources is proved by using induction on the number of source symbols and the inequality of geometric and harmonic means.
Large-scale Supervised Hierarchical Feature Learning for Face Recognition
Venue: arXiv cs.CV 2014
Year: 2014

This paper proposes a novel face recognition algorithm based on large-scale supervised hierarchical feature learning. The approach consists of two parts: hierarchical feature learning and large-scale model learning. The hierarchical feature learning searches feature in three levels of granularity in a supervised way. First, face images are modeled by receptive field theory, and the representation is an image with many channels of Gaussian receptive maps. We activate a few most distinguish channels by supervised learning. Second, the face image is further represented by patches of picked channels, and we search from the over-complete patch pool to activate only those most discriminant patches. Third, the feature descriptor of each patch is further projected to lower dimension subspace with discriminant subspace analysis. Learned feature of activated patches are concatenated to get a full face representation.A linear classifier is learned to separate face pairs from same subjects and different subjects. As the number of face pairs are extremely large, we introduce ADMM (alternative direction method of multipliers) to train the linear classifier on a computing cluster. Experiments show that more training samples will bring notable accuracy improvement. We conduct experiments on FRGC and LFW. Results show that the proposed approach outperforms existing algorithms under the same protocol notably. Besides, the proposed approach is small in memory footprint, and low in computing cost, which makes it suitable for embedded applications.
KMC 2: Fast and resource-frugal $k$-mer counting
Venue: arXiv cs.DS 2014
Year: 2014

Motivation: Building the histogram of occurrences of every $k$-symbol long substring of nucleotide data is a standard step in many bioinformatics applications, known under the name of $k$-mer counting. Its applications include developing de Bruijn graph genome assemblers, fast multiple sequence alignment and repeat detection. The tremendous amounts of NGS data require fast algorithms for $k$-mer counting, preferably using moderate amounts of memory. Results: We present a novel method for $k$-mer counting, on large datasets at least twice faster than the strongest competitors (Jellyfish~2, KMC~1), using about 12\,GB (or less) of RAM memory. Our disk-based method bears some resemblance to MSPKmerCounter, yet replacing the original minimizers with signatures (a carefully selected subset of all minimizers) and using $(k, x)$-mers allows to significantly reduce the I/O, and a highly parallel overall architecture allows to achieve unprecedented processing speeds. For example, KMC~2 allows to count the 28-mers of a human reads collection with 44-fold coverage (106\,GB of compressed size) in about 20 minutes, on a 6-core Intel i7 PC with an SSD. Availability: KMC~2 is freely available at http://sun.aei.polsl.pl/kmc. Contact: sebastian.deorowicz@polsl.pl
A Framework for Specific Term Recommendation Systems
Venue: arXiv cs.IR 2014
Year: 2014

In this paper we present the IRSA framework that enables the automatic creation of search term suggestion or recommendation systems (TS). Such TS are used to operationalize interactive query expansion and help users in refining their information need in the query formulation phase. Our recent research has shown TS to be more effective when specific to a certain domain. The presented technical framework allows owners of Digital Libraries to create their own specific TS constructed via OAI-harvested metadata with very little effort.
Establishing an Online Access Panel for Interactive Information Retrieval Research
Venue: arXiv cs.IR 2014
Year: 2014

We propose an online access panel to support the evaluation process of Interactive Information Retrieval (IIR) systems - called IIRpanel. By maintaining an online access panel with users of IIR systems we assume that the recurring effort to recruit participants for web-based as well as for lab studies can be minimized. We target on using the online access panel not only for our own development processes but to open it for other interested researchers in the field of IIR. In this paper we present the concept of IIRpanel as well as first implementation details.
Dictionary Learning and Tensor Decomposition via the Sum-of-Squares Method
Venue: arXiv cs.DS 2014
Year: 2014

We give a new approach to the dictionary learning (also known as "sparse coding") problem of recovering an unknown $n\times m$ matrix $A$ (for $m \geq n$) from examples of the form \[ y = Ax + e, \] where $x$ is a random vector in $\mathbb R^m$ with at most $τm$ nonzero coordinates, and $e$ is a random noise vector in $\mathbb R^n$ with bounded magnitude. For the case $m=O(n)$, our algorithm recovers every column of $A$ within arbitrarily good constant accuracy in time $m^{O(\log m/\log(τ^{-1}))}$, in particular achieving polynomial time if $τ= m^{-δ}$ for any $δ>0$, and time $m^{O(\log m)}$ if $τ$ is (a sufficiently small) constant. Prior algorithms with comparable assumptions on the distribution required the vector $x$ to be much sparser---at most $\sqrt{n}$ nonzero coordinates---and there were intrinsic barriers preventing these algorithms from applying for denser $x$. We achieve this by designing an algorithm for noisy tensor decomposition that can recover, under quite general conditions, an approximate rank-one decomposition of a tensor $T$, given access to a tensor $T'$ that is $τ$-close to $T$ in the spectral norm (when considered as a matrix). To our knowledge, this is the first algorithm for tensor decomposition that works in the constant spectral-norm noise regime, where there is no guarantee that the local optima of $T$ and $T'$ have similar structures. Our algorithm is based on a novel approach to using and analyzing the Sum of Squares semidefinite programming hierarchy (Parrilo 2000, Lasserre 2001), and it can be viewed as an indication of the utility of this very general and powerful tool for unsupervised learning problems.
Cops and Robbers, Game Theory and Zermelo's Early Results
Venue: arXiv cs.DM 2014
Year: 2014

We provide a game theoretic framework for the game of cops and robbers (CR). Within this framework we study certain assumptions which underlie the concepts of optimal strategies and capture time. We also point out a connection of these concepts to early work by Zermelo and D. Konig. Finally, we discuss the relationship between CR and related pursuit games to reachability games.
KNET: A General Framework for Learning Word Embedding using Morphological Knowledge
Venue: arXiv cs.CL 2014
Year: 2014

Neural network techniques are widely applied to obtain high-quality distributed representations of words, i.e., word embeddings, to address text mining, information retrieval, and natural language processing tasks. Recently, efficient methods have been proposed to learn word embeddings from context that captures both semantic and syntactic relationships between words. However, it is challenging to handle unseen words or rare words with insufficient context. In this paper, inspired by the study on word recognition process in cognitive psychology, we propose to take advantage of seemingly less obvious but essentially important morphological knowledge to address these challenges. In particular, we introduce a novel neural network architecture called KNET that leverages both contextual information and morphological word similarity built based on morphological knowledge to learn word embeddings. Meanwhile, the learning architecture is also able to refine the pre-defined morphological knowledge and obtain more accurate word similarity. Experiments on an analogical reasoning task and a word similarity task both demonstrate that the proposed KNET framework can greatly enhance the effectiveness of word embeddings.
Deterministic Near-Optimal P2P Streaming
Venue: arXiv cs.NI 2014
Year: 2014

We consider streaming over a peer-to-peer network with homogeneous nodes in which a single source broadcasts a data stream to all the users in the system. Peers are allowed to enter or leave the system (adversarially) arbitrarily. Previous approaches for streaming in this setting have either used randomized distribution graphs or structured trees with randomized maintenance algorithms. Randomized graphs handle peer churn well but have poor connectivity guarantees, while structured trees have good connectivity but have proven hard to maintain under peer churn. We improve upon both approaches by presenting a novel distribution structure with a deterministic and distributed algorithm for maintenance under peer churn; our result is inspired by a recent work proposing deterministic algorithms for rumor spreading in graphs. A key innovation in our approach is in having redundant links in the distribution structure. While this leads to a reduction in the maximum streaming rate possible, we show that for the amount of redundancy used, the delay guarantee of the proposed algorithm is near optimal. We introduce a tolerance parameter that captures the worst-case transient streaming rate received by the peers during churn events and characterize the fundamental tradeoff between rate, delay and tolerance. A natural generalization of the deterministic algorithm achieves this tradeoff near optimally. Finally, the proposed deterministic algorithm is robust enough to handle various generalizations: ability to deal with heterogeneous node capacities of the peers and more complicated streaming patterns where multiple source transmissions are present.
Secure Routing Path Using Trust Values for Wireless Sensor Networks
Venue: arXiv cs.CR 2014
Year: 2014

Traditional cryptography-based security mechanisms such as authentication and authorization are not effective against insider attacks like wormhole, sinkhole, selective forwarding attacks, etc., Trust based approaches have been widely used to counter insider attacks in wireless sensor networks. It provides a quantitative way to evaluate the trustworthiness of sensor nodes. An untrustworthy node can wreak considerable damage and adversely affect the quality and reliability of data. Therefore, analysing the trust level of a node is important. In this paper we focused about indirect trust mechanism, in which each node monitors the forwarding behavior of its neighbors in order to detect any node that behaves selfishly and does not forward the packets it receives. For this, we used a link state routing protocol based indirect trusts which forms the shortest route and finds the best trustworthy route among them by comparing the values of all the calculated route trusts as for each route present in the network. And finally, we compare our work with similar routing protocols and show its advantages over them.
Assamese-English Bilingual Machine Translation
Venue: arXiv cs.CL 2014
Year: 2014

Machine translation is the process of translating text from one language to another. In this paper, Statistical Machine Translation is done on Assamese and English language by taking their respective parallel corpus. A statistical phrase based translation toolkit Moses is used here. To develop the language model and to align the words we used two another tools IRSTLM, GIZA respectively. BLEU score is used to check our translation system performance, how good it is. A difference in BLEU scores is obtained while translating sentences from Assamese to English and vice-versa. Since Indian languages are morphologically very rich hence translation is relatively harder from English to Assamese resulting in a low BLEU score. A statistical transliteration system is also introduced with our translation system to deal basically with proper nouns, OOV (out of vocabulary) words which are not present in our corpus.
A class of $p$-ary cyclic codes and their weight enumerators
Venue: arXiv cs.IT 2014
Year: 2014

Let $m$, $k$ be positive integers such that $\frac{m}{\gcd(m,k)}\geq 3$, $p$ be an odd prime and $π$ be a primitive element of $\mathbb{F}_{p^m}$. Let $h_1(x)$ and $h_2(x)$ be the minimal polynomials of $-π^{-1}$ and $π^{-\frac{p^k+1}{2}}$ over $\mathbb{F}_p$, respectively. In the case of odd $\frac{m}{\gcd(m,k)}$, when $k$ is even, $\gcd(m,k)$ is odd or when $\frac{k}{\gcd(m,k)}$ is odd, Zhou et~al. in \cite{zhou} obtained the weight distribution of a class of cyclic codes $\mathcal{C}$ over $\mathbb{F}_p$ with parity-check polynomial $h_1(x)h_2(x)$. In this paper, we further investigate this class of cyclic codes $\mathcal{C}$ over $\mathbb{F}_p$ in the rest case of odd $\frac{m}{\gcd(m,k)}$ and the case of even $\frac{m}{\gcd(m,k)}$. Moreover, we determine the weight distribution of cyclic codes $\mathcal{C}$.
Analyzing Chromatin Using Tiled Binned Scatterplot Matrices
Venue: arXiv cs.CE 2014
Year: 2014

Background: Over the last years, more and more biological data became available. Besides the pure amount of new data, also its dimensionality - the number of different attributes per data point - increased. Recently, especially the amount of data on chromatin and its modifications increased considerably. In the field of epigenetics, appropriate visualization tools designed for highlighting the different aspects of epigenetic data are currently not available. Results: We present a tool called TiBi-Scatter enabling correlation analysis in 2D. This approach allows for analyzing multidimensional data while keeping the use of resources such as memory small. Thus, it is in particular applicable to large data sets. Conclusions: TiBi-Scatter is a resource-friendly and easy to use tool that allows for the hypothesis-free analysis of large multidimensional biological data sets.
Visualization and Correction of Automated Segmentation, Tracking and Lineaging from 5-D Stem Cell Image Sequences
Venue: arXiv cs.GR 2014
Year: 2014

Results: We present an application that enables the quantitative analysis of multichannel 5-D (x, y, z, t, channel) and large montage confocal fluorescence microscopy images. The image sequences show stem cells together with blood vessels, enabling quantification of the dynamic behaviors of stem cells in relation to their vascular niche, with applications in developmental and cancer biology. Our application automatically segments, tracks, and lineages the image sequence data and then allows the user to view and edit the results of automated algorithms in a stereoscopic 3-D window while simultaneously viewing the stem cell lineage tree in a 2-D window. Using the GPU to store and render the image sequence data enables a hybrid computational approach. An inference-based approach utilizing user-provided edits to automatically correct related mistakes executes interactively on the system CPU while the GPU handles 3-D visualization tasks. Conclusions: By exploiting commodity computer gaming hardware, we have developed an application that can be run in the laboratory to facilitate rapid iteration through biological experiments. There is a pressing need for visualization and analysis tools for 5-D live cell image data. We combine accurate unsupervised processes with an intuitive visualization of the results. Our validation interface allows for each data set to be corrected to 100% accuracy, ensuring that downstream data analysis is accurate and verifiable. Our tool is the first to combine all of these aspects, leveraging the synergies obtained by utilizing validation information from stereo visualization to improve the low level image processing tasks.
Gender Prediction in Social Media
Venue: arXiv cs.SI 2014
Year: 2014

In this paper, we explore the task of gender classification using limited network data with an application to Fotolog. We take a heuristic approach to automating gender inference based on username, followers and network structure. We test our approach on a subset of 100,000 nodes and analyze our results to find that there is a lot of value in these limited information and that there is great promise in further pursuing this approach to classification.
Time lower bounds for nonadaptive turnstile streaming algorithms
Venue: arXiv cs.DS 2014
Year: 2014

We say a turnstile streaming algorithm is "non-adaptive" if, during updates, the memory cells written and read depend only on the index being updated and random coins tossed at the beginning of the stream (and not on the memory contents of the algorithm). Memory cells read during queries may be decided upon adaptively. All known turnstile streaming algorithms in the literature are non-adaptive. We prove the first non-trivial update time lower bounds for both randomized and deterministic turnstile streaming algorithms, which hold when the algorithms are non-adaptive. While there has been abundant success in proving space lower bounds, there have been no non-trivial update time lower bounds in the turnstile model. Our lower bounds hold against classically studied problems such as heavy hitters, point query, entropy estimation, and moment estimation. In some cases of deterministic algorithms, our lower bounds nearly match known upper bounds.
The data-exchange chase under the microscope
Venue: arXiv cs.DB 2014
Year: 2014

In this paper we take closer look at recent developments for the chase procedure, and provide additional results. Our analysis allows us create a taxonomy of the chase variations and the properties they satisfy. Two of the most central problems regarding the chase is termination, and discovery of restricted classes of sets of dependencies that guarantee termination of the chase. The search for the restricted classes has been motivated by a fairly recent result that shows that it is undecidable to determine whether the chase with a given dependency set will terminate on a given instance. There is a small dissonance here, since the quest has been for classes of sets of dependencies guaranteeing termination of the chase on all instances, even though the latter problem was not known to be undecidable. We resolve the dissonance in this paper by showing that determining whether the chase with a given set of dependencies terminates on all instances is coRE-complete. For the hardness proof we use a reduction from word rewriting systems, thereby also showing the close connection between the chase and word rewriting. The same reduction also gives us the aforementioned instance-dependent RE-completeness result as a byproduct. For one of the restricted classes guaranteeing termination on all instances, the stratified sets dependencies, we provide new complexity results for the problem of testing whether a given set of dependencies belongs to it. These results rectify some previous claims that have occurred in the literature.