OpenRaiser/Intern-Atlas huggingface dataset:
Evolutionary algorithm based adaptive navigation in information retrieval interfaces
Venue: arXiv cs.IR 2015
Year: 2015

In computer interfaces in general, especially in information retrieval tasks, it is important to be able to quickly find and retrieve information. State of the art approach, used, for example, in search engines, is not effective as it introduces losses of meanings due to context to keywords back and forth translation. Authors argue it increases the time and reduces the accuracy of information retrieval compared to what it could be in the system that employs modern information retrieval and text mining methods while presenting results in an adaptive human- computer interface where system effectively learns what operator needs through iterative interaction. In current work, a combination of adaptive navigational interface and real time collaborative feedback analysis for documents relevance weighting is proposed as an viable alternative to prevailing "telegraphic" approach in information retrieval systems. Adaptive navigation is provided through a dynamic links panel controlled by an evolutionary algorithm. Documents relevance is initially established with standard information retrieval techniques and is further refined in real time through interaction of users with the system. Introduced concepts of multidimensional Knowledge Map and Weighted Point of Interest allow finding relevant documents and users with common interests through a trivial calculation. Browsing search approach, the ability of the algorithm to adapt navigation to users interests, collaborative refinement and the self-organising features of the system are the main factors making such architecture effective in various fields where non-structured knowledge shall be represented to the users.
Facility location with double-peaked preference
Venue: arXiv cs.GT 2015
Year: 2015

We study the problem of locating a single facility on a real line based on the reports of self-interested agents, when agents have double-peaked preferences, with the peaks being on opposite sides of their locations. We observe that double-peaked preferences capture real-life scenarios and thus complement the well-studied notion of single-peaked preferences. We mainly focus on the case where peaks are equidistant from the agents' locations and discuss how our results extend to more general settings. We show that most of the results for single-peaked preferences do not directly apply to this setting; this makes the problem essentially more challenging. As our main contribution, we present a simple truthful-in-expectation mechanism that achieves an approximation ratio of 1+b/c for both the social and the maximum cost, where b is the distance of the agent from the peak and c is the minimum cost of an agent. For the latter case, we provide a 3/2 lower bound on the approximation ratio of any truthful-in-expectation mechanism. We also study deterministic mechanisms under some natural conditions, proving lower bounds and approximation guarantees. We prove that among a large class of reasonable mechanisms, there is no deterministic mechanism that outperforms our truthful-in-expectation mechanism.
Journal Portfolio Analysis for Countries, Cities, and Organizations: Maps and Comparisons
Venue: arXiv cs.DL 2015
Year: 2015

Using Web-of-Science data, portfolio analysis in terms of journal coverage can be projected on a base map for units of analysis such as countries, cities, universities, and firms. The units of analysis under study can be compared statistically across the 10,000+ journals. The interdisciplinarity of the portfolios is measured using Rao-Stirling diversity or Zhang et al.'s (in press) improved measure 2D3. At the country level we find regional differentiation (e.g., Latin-American or Asian countries), but also a major divide between advanced and less-developed countries. Israel and Israeli cities outperform other nations and cities in terms of diversity. Universities appear to be specifically related to firms when a number of these units are exploratively compared. The instrument is relatively simple and straightforward, and one can generalize the application to any document set retrieved from WoS. Further instruction is provided online at http://www.leydesdorff.net/portfolio .
Quicksort, Largest Bucket, and Min-Wise Hashing with Limited Independence
Venue: arXiv cs.DS 2015
Year: 2015

Randomized algorithms and data structures are often analyzed under the assumption of access to a perfect source of randomness. The most fundamental metric used to measure how "random" a hash function or a random number generator is, is its independence: a sequence of random variables is said to be $k$-independent if every variable is uniform and every size $k$ subset is independent. In this paper we consider three classic algorithms under limited independence. We provide new bounds for randomized quicksort, min-wise hashing and largest bucket size under limited independence. Our results can be summarized as follows. -Randomized quicksort. When pivot elements are computed using a $5$-independent hash function, Karloff and Raghavan, J.ACM'93 showed $O ( n \log n)$ expected worst-case running time for a special version of quicksort. We improve upon this, showing that the same running time is achieved with only $4$-independence. -Min-wise hashing. For a set $A$, consider the probability of a particular element being mapped to the smallest hash value. It is known that $5$-independence implies the optimal probability $O (1 /n)$. Broder et al., STOC'98 showed that $2$-independence implies it is $O(1 / \sqrt{|A|})$. We show a matching lower bound as well as new tight bounds for $3$- and $4$-independent hash functions. -Largest bucket. We consider the case where $n$ balls are distributed to $n$ buckets using a $k$-independent hash function and analyze the largest bucket size. Alon et. al, STOC'97 showed that there exists a $2$-independent hash function implying a bucket of size $Ω( n^{1/2})$. We generalize the bound, providing a $k$-independent family of functions that imply size $Ω( n^{1/k})$.
Application of Independent Component Analysis Techniques in Speckle Noise Reduction of Retinal OCT Images
Venue: arXiv cs.CV 2015
Year: 2015

Optical Coherence Tomography (OCT) is an emerging technique in the field of biomedical imaging, with applications in ophthalmology, dermatology, coronary imaging etc. OCT images usually suffer from a granular pattern, called speckle noise, which restricts the process of interpretation. Therefore the need for speckle noise reduction techniques is of high importance. To the best of our knowledge, use of Independent Component Analysis (ICA) techniques has never been explored for speckle reduction of OCT images. Here, a comparative study of several ICA techniques (InfoMax, JADE, FastICA and SOBI) is provided for noise reduction of retinal OCT images. Having multiple B-scans of the same location, the eye movements are compensated using a rigid registration technique. Then, different ICA techniques are applied to the aggregated set of B-scans for extracting the noise-free image. Signal-to-Noise-Ratio (SNR), Contrast-to-Noise-Ratio (CNR) and Equivalent-Number-of-Looks (ENL), as well as analysis on the computational complexity of the methods, are considered as metrics for comparison. The results show that use of ICA can be beneficial, especially in case of having fewer number of B-scans.
Multipartite Monotones for Secure Sampling by Public Discussion From Noisy Correlations
Venue: arXiv cs.IT 2015
Year: 2015

We address the problem of quantifying the cryptographic content of probability distributions, in relation to an application to secure multi-party sampling against a passive t-adversary. We generalize a recently introduced notion of assisted common information of a pair of correlated sources to that of K sources and define a family of monotone rate regions indexed by K. This allows for a simple characterization of all t-private distributions that can be statistically securely sampled without any auxiliary setup of pre-shared noisy correlations. We also give a new monotone called the residual total correlation that admits a simple operational interpretation. Interestingly, for sampling with non-trivial setups (K > 2) in the public discussion model, our definition of a monotone region differs from the one by Prabhakaran and Prabhakaran (ITW 2012).
LDPC Code Design for Noncoherent Physical Layer Network Coding
Venue: arXiv cs.IT 2015
Year: 2015

This work considers optimizing LDPC codes in the physical-layer network coded two-way relay channel using noncoherent FSK modulation. The error-rate performance of channel decoding at the relay node during the multiple-access phase was improved through EXIT-based optimization of Tanner graph variable node degree distributions. Codes drawn from the DVB-S2 and WiMAX standards were used as a basis for design and performance comparison. The computational complexity characteristics of the standard codes were preserved in the optimized codes by maintaining the extended irregular repeat-accumulate (eIRA). The relay receiver performance was optimized considering two modulation orders M = {4, 8} using iterative decoding in which the decoder and demodulator refine channel estimates by exchanging information. The code optimization procedure yielded unique optimized codes for each case of modulation order and available channel state information. Performance of the standard and optimized codes were measured using Monte Carlo simulation in the flat Rayleigh fading channel, and error rate improvements up to 1.2 dB are demonstrated depending on system parameters.
Rotor-routing orbits in directed graphs and the Picard group
Venue: arXiv cs.DM 2015
Year: 2015

In [5], Holroyd, Levine, Mészáros, Peres, Propp and Wilson characterize recurrent chip-and-rotor configurations for strongly connected digraphs. However, the number of steps needed to recur, and the number of orbits is left open for general digraphs. Recently, these questions were answered by Pham [6], using linear algebraic methods. We give new, purely combinatorial proofs for these formulas. We also relate rotor-router orbits to the chip-firing game: The number of recurrent rotor-router unicycle-orbits equals the order of the Picard group of the graph, defined in the sense of [1], and during a period, the same chip-moves happen, as during firing the period vector in the chip-firing game.
Co-Primary Multi-Operator Resource Sharing for Small Cell Networks
Venue: arXiv cs.NI 2015
Year: 2015

To tackle the challenge of providing higher data rates within limited spectral resources we consider the case of multiple operators sharing a common pool of radio resources. Four algorithms are proposed to address co-primary multi-operator radio resource sharing under heterogeneous traffic in both centralized and distributed scenarios. The performance of these algorithms is assessed through extensive system-level simulations for two indoor small cell layouts. It is assumed that the spectral allocations of the small cells are orthogonal to the macro network layer and thus, only the small cell traffic is modeled. The main performance metrics are user throughput and the relative amount of shared spectral resources. The numerical results demonstrate the importance of coordination among co-primary operators for an optimal resource sharing. Also, maximizing the spectrum sharing percentage generally improves the achievable throughput gains over non-sharing.
Self-Inverse Functions and Palindromic Circuits
Venue: arXiv cs.ET 2015
Year: 2015

We investigate the subclass of reversible functions that are self-inverse and relate them to reversible circuits that are equal to their reverse circuit, which are called palindromic circuits. We precisely determine which self-inverse functions can be realized as a palindromic circuit. For those functions that cannot be realized as a palindromic circuit, we find alternative palindromic representations that require an extra circuit line or quantum gates in their construction. Our analyses make use of involutions in the symmetric group $S_{2^n}$ which are isomorphic to self-inverse reversible function on $n$ variables.
On the relative proof complexity of deep inference via atomic flows
Venue: arXiv cs.LO 2015
Year: 2015

We consider the proof complexity of the minimal complete fragment, KS, of standard deep inference systems for propositional logic. To examine the size of proofs we employ atomic flows, diagrams that trace structural changes through a proof but ignore logical information. As results we obtain a polynomial simulation of versions of Resolution, along with some extensions. We also show that these systems, as well as bounded-depth Frege systems, cannot polynomially simulate KS, by giving polynomial-size proofs of certain variants of the propositional pigeonhole principle in KS.
Analysis of Lithography Based Approaches In development of Semi Conductors
Venue: arXiv cs.OH 2015
Year: 2015

The end of the 19th century brought about a change in the dynamics of computing by the development of the microprocessor. Huge bedroom size computers began being replaced by portable, smaller sized desktops. Today the world is dominated by silicon, which has circumscribed chip development for computers through microprocessors. Majority of the integrated circuits that are manufactured at present are developed using the concept of Lithography. This paper presents a detailed analysis of multiple Lithography methodologies as a means for advanced integrated circuit development. The study paper primarily restricts to examples in the context of Lithography, surveying the various existing techniques of Lithography in literature, examining feasible and efficient methods, highlighting the various pros and cons of each of them.
Achieving All with No Parameters: Adaptive NormalHedge
Venue: arXiv cs.LG 2015
Year: 2015

We study the classic online learning problem of predicting with expert advice, and propose a truly parameter-free and adaptive algorithm that achieves several objectives simultaneously without using any prior information. The main component of this work is an improved version of the NormalHedge.DT algorithm (Luo and Schapire, 2014), called AdaNormalHedge. On one hand, this new algorithm ensures small regret when the competitor has small loss and almost constant regret when the losses are stochastic. On the other hand, the algorithm is able to compete with any convex combination of the experts simultaneously, with a regret in terms of the relative entropy of the prior and the competitor. This resolves an open problem proposed by Chaudhuri et al. (2009) and Chernov and Vovk (2010). Moreover, we extend the results to the sleeping expert setting and provide two applications to illustrate the power of AdaNormalHedge: 1) competing with time-varying unknown competitors and 2) predicting almost as well as the best pruning tree. Our results on these applications significantly improve previous work from different aspects, and a special case of the first application resolves another open problem proposed by Warmuth and Koolen (2014) on whether one can simultaneously achieve optimal shifting regret for both adversarial and stochastic losses.
Scheduling Storms and Streams in the Cloud
Venue: arXiv cs.NI 2015
Year: 2015

Motivated by emerging big streaming data processing paradigms (e.g., Twitter Storm, Streaming MapReduce), we investigate the problem of scheduling graphs over a large cluster of servers. Each graph is a job, where nodes represent compute tasks and edges indicate data-flows between these compute tasks. Jobs (graphs) arrive randomly over time, and upon completion, leave the system. When a job arrives, the scheduler needs to partition the graph and distribute it over the servers to satisfy load balancing and cost considerations. Specifically, neighboring compute tasks in the graph that are mapped to different servers incur load on the network; thus a mapping of the jobs among the servers incurs a cost that is proportional to the number of "broken edges". We propose a low complexity randomized scheduling algorithm that, without service preemptions, stabilizes the system with graph arrivals/departures; more importantly, it allows a smooth trade-off between minimizing average partitioning cost and average queue lengths. Interestingly, to avoid service preemptions, our approach does not rely on a Gibbs sampler; instead, we show that the corresponding limiting invariant measure has an interpretation stemming from a loss system.
Study on Sparse Representation based Classification for Biometric Verification
Venue: arXiv cs.CV 2015
Year: 2015

In this paper, we propose a multimodal verification system integrating face and ear based on sparse representation based classification (SRC). The face and ear query samples are first encoded separately to derive sparsity-based match scores, and which are then combined with sum-rule fusion for verification. Apart from validating the encouraging performance of SRC-based multimodal verification, this paper also dedicates to provide a clear understanding about the characteristics of SRC-based biometric verification. To this end, two sparsity-based metrics, i.e. spare coding error (SCE) and sparse contribution rate (SCR), are involved, together with face and ear unimodal SRC-based verification. As for the issue that SRC-based biometric verification may suffer from heavy computational burden and verification accuracy degradation with increase of enrolled subjects, we argue that it could be properly resolved by exploiting small random dictionary for sparsity-based score computation, which consists of training samples from a limited number of randomly selected subjects. Experimental results demonstrate the superiority of SRC-based multimodal verification compared to the state-of-the-art multimodal methods like likelihood ratio (LLR), support vector machine (SVM), and the sum-rule fusion methods using cosine similarity, meanwhile the idea of using small random dictionary is feasible in both effectiveness and efficiency.
A new network-based algorithm for human activity recognition in video
Venue: arXiv cs.CV 2015
Year: 2015

In this paper, a new network-transmission-based (NTB) algorithm is proposed for human activity recognition in videos. The proposed NTB algorithm models the entire scene as an error-free network. In this network, each node corresponds to a patch of the scene and each edge represents the activity correlation between the corresponding patches. Based on this network, we further model people in the scene as packages while human activities can be modeled as the process of package transmission in the network. By analyzing these specific "package transmission" processes, various activities can be effectively detected. The implementation of our NTB algorithm into abnormal activity detection and group activity recognition are described in detail in the paper. Experimental results demonstrate the effectiveness of our proposed algorithm.
On the representation of the search region in multi-objective optimization
Venue: arXiv cs.DM 2015
Year: 2015

Given a finite set $N$ of feasible points of a multi-objective optimization (MOO) problem, the search region corresponds to the part of the objective space containing all the points that are not dominated by any point of $N$, i.e. the part of the objective space which may contain further nondominated points. In this paper, we consider a representation of the search region by a set of tight local upper bounds (in the minimization case) that can be derived from the points of $N$. Local upper bounds play an important role in methods for generating or approximating the nondominated set of an MOO problem, yet few works in the field of MOO address their efficient incremental determination. We relate this issue to the state of the art in computational geometry and provide several equivalent definitions of local upper bounds that are meaningful in MOO. We discuss the complexity of this representation in arbitrary dimension, which yields an improved upper bound on the number of solver calls in epsilon-constraint-like methods to generate the nondominated set of a discrete MOO problem. We analyze and enhance a first incremental approach which operates by eliminating redundancies among local upper bounds. We also study some properties of local upper bounds, especially concerning the issue of redundant local upper bounds, that give rise to a new incremental approach which avoids such redundancies. Finally, the complexities of the incremental approaches are compared from the theoretical and empirical points of view.
Sampling with Walsh Transforms
Venue: arXiv cs.IT 2015
Year: 2015

With the advent of massive data outputs at a regular rate, admittedly, signal processing technology plays an increasingly key role. Nowadays, signals are not merely restricted to physical sources, they have been extended to digital sources as well. Under the general assumption of discrete statistical signal sources, we propose a practical problem of sampling incomplete noisy signals for which we do not know a priori and the sample size is bounded. We approach this sampling problem by Shannon's channel coding theorem. We use an extremal binary channel with high probability of transmission error, which is rare in communication theory. Our main result demonstrates that it is the large Walsh coefficient(s) that characterize(s) discrete statistical signals, regardless of the signal sources. Note that this is a known fact in specific application domains such as images. By the connection of Shannon's theorem, we establish the necessary and sufficient condition for our generic sampling problem for the first time. Finally, we discuss the cryptographic significance of sparse Walsh transform.
Distortive Effects of Initial-Based Name Disambiguation on Measurements of Large-Scale Coauthorship Networks
Venue: arXiv cs.DL 2015
Year: 2015

Scholars have often relied on name initials to resolve name ambiguities in large-scale coauthorship network research. This approach bears the risk of incorrectly merging or splitting author identities. The use of initial-based disambiguation has been justified by the assumption that such errors would not affect research findings too much. This paper tests this assumption by analyzing coauthorship networks from five academic fields - biology, computer science, nanoscience, neuroscience, and physics - and an interdisciplinary journal, PNAS. Name instances in datasets of this study were disambiguated based on heuristics gained from previous algorithmic disambiguation solutions. We use disambiguated data as a proxy of ground-truth to test the performance of three types of initial-based disambiguation. Our results show that initial-based disambiguation can misrepresent statistical properties of coauthorship networks: it deflates the number of unique authors, number of component, average shortest paths, clustering coefficient, and assortativity, while it inflates average productivity, density, average coauthor number per author, and largest component size. Also, on average, more than half of top 10 productive or collaborative authors drop off the lists. Asian names were found to account for the majority of misidentification by initial-based disambiguation due to their common surname and given name initials.