OpenRaiser/Intern-Atlas huggingface dataset:
Impliance: A Next Generation Information Management Appliance
Venue: arXiv cs.DB 2006
Year: 2006

ably successful in building a large market and adapting to the changes of the last three decades, its impact on the broader market of information management is surprisingly limited. If we were to design an information management system from scratch, based upon today's requirements and hardware capabilities, would it look anything like today's database systems?" In this paper, we introduce Impliance, a next-generation information management system consisting of hardware and software components integrated to form an easy-to-administer appliance that can store, retrieve, and analyze all types of structured, semi-structured, and unstructured information. We first summarize the trends that will shape information management for the foreseeable future. Those trends imply three major requirements for Impliance: (1) to be able to store, manage, and uniformly query all data, not just structured records; (2) to be able to scale out as the volume of this data grows; and (3) to be simple and robust in operation. We then describe four key ideas that are uniquely combined in Impliance to address these requirements, namely the ideas of: (a) integrating software and off-the-shelf hardware into a generic information appliance; (b) automatically discovering, organizing, and managing all data - unstructured as well as structured - in a uniform way; (c) achieving scale-out by exploiting simple, massive parallel processing, and (d) virtualizing compute and storage resources to unify, simplify, and streamline the management of Impliance. Impliance is an ambitious, long-term effort to define simpler, more robust, and more scalable information systems for tomorrow's enterprises.
A New Era in Citation and Bibliometric Analyses: Web of Science, Scopus, and Google Scholar
Venue: arXiv cs.DL 2006
Year: 2006

Academic institutions, federal agencies, publishers, editors, authors, and librarians increasingly rely on citation analysis for making hiring, promotion, tenure, funding, and/or reviewer and journal evaluation and selection decisions. The Institute for Scientific Information's (ISI) citation databases have been used for decades as a starting point and often as the only tools for locating citations and/or conducting citation analyses. ISI databases (or Web of Science), however, may no longer be adequate as the only or even the main sources of citations because new databases and tools that allow citation searching are now available. Whether these new databases and tools complement or represent alternatives to Web of Science (WoS) is important to explore. Using a group of 15 library and information science faculty members as a case study, this paper examines the effects of using Scopus and Google Scholar (GS) on the citation counts and rankings of scholars as measured by WoS. The paper discusses the strengths and weaknesses of WoS, Scopus, and GS, their overlap and uniqueness, quality and language of the citations, and the implications of the findings for citation analysis. The project involved citation searching for approximately 1,100 scholarly works published by the study group and over 200 works by a test group (an additional 10 faculty members). Overall, more than 10,000 citing and purportedly citing documents were examined. WoS data took about 100 hours of collecting and processing time, Scopus consumed 200 hours, and GS a grueling 3,000 hours.
Alignment of Speech to Highly Imperfect Text Transcriptions
Venue: arXiv cs.SD 2006
Year: 2006

We introduce a novel and inexpensive approach for the temporal alignment of speech to highly imperfect transcripts from automatic speech recognition (ASR). Transcripts are generated for extended lecture and presentation videos, which in some cases feature more than 30 speakers with different accents, resulting in highly varying transcription qualities. In our approach we detect a subset of phonemes in the speech track, and align them to the sequence of phonemes extracted from the transcript. We report on the results for 4 speech-transcript sets ranging from 22 to 108 minutes. The alignment performance is promising, showing a correct matching of phonemes within 10, 20, 30 second error margins for more than 60%, 75%, 90% of text, respectively, on average.
Exact solutions for the two- and all-terminal reliabilities of the Brecht-Colbourn ladder and the generalized fan
Venue: arXiv cs.PF 2006
Year: 2006

The two- and all-terminal reliabilities of the Brecht-Colbourn ladder and the generalized fan have been calculated exactly for arbitrary size as well as arbitrary individual edge and node reliabilities, using transfer matrices of dimension four at most. While the all-terminal reliabilities of these graphs are identical, the special case of identical edge ($p$) and node ($ρ$) reliabilities shows that their two-terminal reliabilities are quite distinct, as demonstrated by their generating functions and the locations of the zeros of the reliability polynomials, which undergo structural transitions at $ρ= \displaystyle {1/2}$.
Reducing SAT to 2-SAT
Venue: arXiv cs.CC 2007
Year: 2007

Description of a polynomial time reduction of SAT to 2-SAT of polynomial size.
Optimal Synthesis of Multiple Algorithms
Venue: arXiv cs.DS 2007
Year: 2007

In this paper we give a definition of "algorithm," "finite algorithm," "equivalent algorithms," and what it means for a single algorithm to dominate a set of algorithms. We define a derived algorithm which may have a smaller mean execution time than any of its component algorithms. We give an explicit expression for the mean execution time (when it exists) of the derived algorithm. We give several illustrative examples of derived algorithms with two component algorithms. We include mean execution time solutions for two-algorithm processors whose joint density of execution times are of several general forms. For the case in which the joint density for a two-algorithm processor is a step function, we give a maximum-likelihood estimation scheme with which to analyze empirical processing time data.
Opportunistic Relay Selection with Limited Feedback
Venue: arXiv cs.IT 2007
Year: 2007

It has been shown that a decentralized relay selection protocol based on opportunistic feedback from the relays yields good throughput performance in dense wireless networks. This selection strategy supports a hybrid-ARQ transmission approach where relays forward parity information to the destination in the event of a decoding error. Such an approach, however, suffers a loss compared to centralized strategies that select relays with the best channel gain to the destination. This paper closes the performance gap by adding another level of channel feedback to the decentralized relay selection problem. It is demonstrated that only one additional bit of feedback is necessary for good throughput performance. The performance impact of varying key parameters such as the number of relays and the channel feedback threshold is discussed. An accompanying bit error rate analysis demonstrates the importance of relay selection.
Trellis-Coded Quantization Based on Maximum-Hamming-Distance Binary Codes
Venue: arXiv cs.IT 2007
Year: 2007

Most design approaches for trellis-coded quantization take advantage of the duality of trellis-coded quantization with trellis-coded modulation, and use the same empirically-found convolutional codes to label the trellis branches. This letter presents an alternative approach that instead takes advantage of maximum-Hamming-distance convolutional codes. The proposed source codes are shown to be competitive with the best in the literature for the same computational complexity.
Scaling Laws of Cognitive Networks
Venue: arXiv cs.IT 2007
Year: 2007

We consider a cognitive network consisting of n random pairs of cognitive transmitters and receivers communicating simultaneously in the presence of multiple primary users. Of interest is how the maximum throughput achieved by the cognitive users scales with n. Furthermore, how far these users must be from a primary user to guarantee a given primary outage. Two scenarios are considered for the network scaling law: (i) when each cognitive transmitter uses constant power to communicate with a cognitive receiver at a bounded distance away, and (ii) when each cognitive transmitter scales its power according to the distance to a considered primary user, allowing the cognitive transmitter-receiver distances to grow. Using single-hop transmission, suitable for cognitive devices of opportunistic nature, we show that, in both scenarios, with path loss larger than 2, the cognitive network throughput scales linearly with the number of cognitive users. We then explore the radius of a primary exclusive region void of cognitive transmitters. We obtain bounds on this radius for a given primary outage constraint. These bounds can help in the design of a primary network with exclusive regions, outside of which cognitive users may transmit freely. Our results show that opportunistic secondary spectrum access using single-hop transmission is promising.
Power control and receiver design for energy efficiency in multipath CDMA channels with bandlimited waveforms
Venue: arXiv cs.IT 2007
Year: 2007

This paper is focused on the cross-layer design problem of joint multiuser detection and power control for energy-efficiency optimization in a wireless data network through a game-theoretic approach. Building on work of Meshkati, et al., wherein the tools of game-theory are used in order to achieve energy-efficiency in a simple synchronous code division multiple access system, system asynchronism, the use of bandlimited chip-pulses, and the multipath distortion induced by the wireless channel are explicitly incorporated into the analysis. Several non-cooperative games are proposed wherein users may vary their transmit power and their uplink receiver in order to maximize their utility, which is defined here as the ratio of data throughput to transmit power. In particular, the case in which a linear multiuser detector is adopted at the receiver is considered first, and then, the more challenging case in which non-linear decision feedback multiuser detectors are employed is considered. The proposed games are shown to admit a unique Nash equilibrium point, while simulation results show the effectiveness of the proposed solutions, as well as that the use of a decision-feedback multiuser receiver brings remarkable performance improvements.
Joint universal lossy coding and identification of stationary mixing sources
Venue: arXiv cs.IT 2007
Year: 2007

The problem of joint universal source coding and modeling, treated in the context of lossless codes by Rissanen, was recently generalized to fixed-rate lossy coding of finitely parametrized continuous-alphabet i.i.d. sources. We extend these results to variable-rate lossy block coding of stationary ergodic sources and show that, for bounded metric distortion measures, any finitely parametrized family of stationary sources satisfying suitable mixing, smoothness and Vapnik-Chervonenkis learnability conditions admits universal schemes for joint lossy source coding and identification. We also give several explicit examples of parametric sources satisfying the regularity conditions.
Optimal Routing for the Gaussian Multiple-Relay Channel with Decode-and-Forward
Venue: arXiv cs.IT 2007
Year: 2007

In this paper, we study a routing problem on the Gaussian multiple relay channel, in which nodes employ a decode-and-forward coding strategy. We are interested in routes for the information flow through the relays that achieve the highest DF rate. We first construct an algorithm that provably finds optimal DF routes. As the algorithm runs in factorial time in the worst case, we propose a polynomial time heuristic algorithm that finds an optimal route with high probability. We demonstrate that that the optimal (and near optimal) DF routes are good in practice by simulating a distributed DF coding scheme using low density parity check codes with puncturing and incremental redundancy.
Neighbor Discovery in Wireless Networks:A Multiuser-Detection Approach
Venue: arXiv cs.IT 2007
Year: 2007

We examine the problem of determining which nodes are neighbors of a given one in a wireless network. We consider an unsupervised network operating on a frequency-flat Gaussian channel, where $K+1$ nodes associate their identities to nonorthogonal signatures, transmitted at random times, synchronously, and independently. A number of neighbor-discovery algorithms, based on different optimization criteria, are introduced and analyzed. Numerical results show how reduced-complexity algorithms can achieve a satisfactory performance.
Sample size cognizant detection of signals in white noise
Venue: arXiv cs.IT 2007
Year: 2007

The detection and estimation of signals in noisy, limited data is a problem of interest to many scientific and engineering communities. We present a computationally simple, sample eigenvalue based procedure for estimating the number of high-dimensional signals in white noise when there are relatively few samples. We highlight a fundamental asymptotic limit of sample eigenvalue based detection of weak high-dimensional signals from a limited sample size and discuss its implication for the detection of two closely spaced signals. This motivates our heuristic definition of the 'effective number of identifiable signals.' Numerical simulations are used to demonstrate the consistency of the algorithm with respect to the effective number of signals and the superior performance of the algorithm with respect to Wax and Kailath's "asymptotically consistent" MDL based estimator.
Direct Optimization of Ranking Measures
Venue: arXiv cs.IR 2007
Year: 2007

Web page ranking and collaborative filtering require the optimization of sophisticated performance measures. Current Support Vector approaches are unable to optimize them directly and focus on pairwise comparisons instead. We present a new approach which allows direct optimization of the relevant loss functions. This is achieved via structured estimation in Hilbert spaces. It is most related to Max-Margin-Markov networks optimization of multivariate performance measures. Key to our approach is that during training the ranking problem can be viewed as a linear assignment problem, which can be solved by the Hungarian Marriage algorithm. At test time, a sort operation is sufficient, as our algorithm assigns a relevance score to every (document, query) pair. Experiments show that the our algorithm is fast and that it works very well.
Cooperative Transmission Protocols with High Spectral Efficiency and High Diversity Order Using Multiuser Detection and Network Coding
Venue: arXiv cs.IT 2007
Year: 2007

Cooperative transmission is an emerging communication technique that takes advantages of the broadcast nature of wireless channels. However, due to low spectral efficiency and the requirement of orthogonal channels, its potential for use in future wireless networks is limited. In this paper, by making use of multiuser detection (MUD) and network coding, cooperative transmission protocols with high spectral efficiency, diversity order, and coding gain are developed. Compared with the traditional cooperative transmission protocols with single-user detection, in which the diversity gain is only for one source user, the proposed MUD cooperative transmission protocols have the merits that the improvement of one user's link can also benefit the other users. In addition, using MUD at the relay provides an environment in which network coding can be employed. The coding gain and high diversity order can be obtained by fully utilizing the link between the relay and the destination. From the analysis and simulation results, it is seen that the proposed protocols achieve higher diversity gain, better asymptotic efficiency, and lower bit error rate, compared to traditional MUD and to existing cooperative transmission protocols.
Polynomial algorithms for protein similarity search for restricted mRNA structures
Venue: arXiv cs.DS 2007
Year: 2007

In this paper we consider the problem of computing an mRNA sequence of maximal similarity for a given mRNA of secondary structure constraints, introduced by Backofen et al. in [BNS02] denoted as the MRSO problem. The problem is known to be NP-complete for planar associated implied structure graphs of vertex degree at most 3. In [BFHV05] a first polynomial dynamic programming algorithms for MRSO on implied structure graphs with maximum vertex degree 3 of bounded cut-width is shown. We give a simple but more general polynomial dynamic programming solution for the MRSO problem for associated implied structure graphs of bounded clique-width. Our result implies that MRSO is polynomial for graphs of bounded tree-width, co-graphs, $P_4$-sparse graphs, and distance hereditary graphs. Further we conclude that the problem of comparing two solutions for MRSO is hard for the class of problems which can be solved in polynomial time with a number of parallel queries to an oracle in NP.
Une plate-forme dynamique pour l'évaluation des performances des bases de données à objets
Venue: arXiv cs.DB 2007
Year: 2007

In object-oriented or object-relational databases such as multimedia databases or most XML databases, access patterns are not static, i.e., applications do not always access the same objects in the same order repeatedly. However, this has been the way these databases and associated optimisation techniques such as clustering have been evaluated up to now. This paper opens up research regarding this issue by proposing a dynamic object evaluation framework (DOEF). DOEF accomplishes access pattern change by defining configurable styles of change. It is a preliminary prototype that has been designed to be open and fully extensible. Though originally designed for the object-oriented model, it can also be used within the object-relational model with few adaptations. Furthermore, new access pattern change models can be added too. To illustrate the capabilities of DOEF, we conducted two different sets of experiments. In the first set of experiments, we used DOEF to compare the performances of four state of the art dynamic clustering algorithms. The results show that DOEF is effective at determining the adaptability of each dynamic clustering algorithm to changes in access pattern. They also led us to conclude that dynamic clustering algorithms can cope with moderate levels of access pattern change, but that performance rapidly degrades to be worse than no clustering when vigorous styles of access pattern change are applied. In the second set of experiments, we used DOEF to compare the performance of two different object stores: Platypus and SHORE. The use of DOEF exposed the poor swapping performance of Platypus.
Sabbath Day Home Automation: "It's Like Mixing Technology and Religion"
Venue: arXiv cs.HC 2007
Year: 2007

We present a qualitative study of 20 American Orthodox Jewish families' use of home automation for religious purposes. These lead users offer insight into real-life, long-term experience with home automation technologies. We discuss how automation was seen by participants to contribute to spiritual experience and how participants oriented to the use of automation as a religious custom. We also discuss the relationship of home automation to family life. We draw design implications for the broader population, including surrender of control as a design resource, home technologies that support long-term goals and lifestyle choices, and respite from technology.
Joint Detection and Identification of an Unobservable Change in the Distribution of a Random Sequence
Venue: arXiv cs.IT 2007
Year: 2007

This paper examines the joint problem of detection and identification of a sudden and unobservable change in the probability distribution function (pdf) of a sequence of independent and identically distributed (i.i.d.) random variables to one of finitely many alternative pdf's. The objective is quick detection of the change and accurate inference of the ensuing pdf. Following a Bayesian approach, a new sequential decision strategy for this problem is revealed and is proven optimal. Geometrical properties of this strategy are demonstrated via numerical examples.
Constructions of q-Ary Constant-Weight Codes
Venue: arXiv cs.IT 2007
Year: 2007

This paper introduces a new combinatorial construction for q-ary constant-weight codes which yields several families of optimal codes and asymptotically optimal codes. The construction reveals intimate connection between q-ary constant-weight codes and sets of pairwise disjoint combinatorial designs of various types.
About the domino problem in the hyperbolic plane, a new solution: complement
Venue: arXiv cs.CG 2007
Year: 2007

In this paper, we complete the construction of paper arXiv:cs.CG/0701096v2. Together with the proof contained in arXiv:cs.CG/0701096v2, this paper definitely proves that the general problem of tiling the hyperbolic plane with {\it à la} Wang tiles is undecidable.
Performance Analysis for Multichannel Reception of OOFSK Signaling
Venue: arXiv cs.IT 2007
Year: 2007

In this paper, the error performance of on-off frequency shift keying (OOFSK) modulation over fading channels is analyzed when the receiver is equipped with multiple antennas. The analysis is conducted in two cases: the coherent scenario where the fading is perfectly known at the receiver, and the noncoherent scenario where neither the receiver nor the transmitter knows the fading coefficients. For both cases, the maximum a posteriori probability (MAP) detection rule is derived and analytical probability of error expressions are obtained. The effect of fading correlation among the receiver antennas is also studied. Simulation results indicate that for sufficiently low duty cycle values, lower probability of error values with respect to FSK signaling are achieved. Equivalently, when compared to FSK modulation, OOFSK with low duty cycle requires less energy to achieve the same probability of error, which renders this modulation a more energy efficient transmission technique.
Riemannian level-set methods for tensor-valued data
Venue: arXiv cs.CV 2007
Year: 2007

We present a novel approach for the derivation of PDE modeling curvature-driven flows for matrix-valued data. This approach is based on the Riemannian geometry of the manifold of Symmetric Positive Definite Matrices Pos(n).
Power Allocation for Discrete-Input Non-Ergodic Block-Fading Channels
Venue: arXiv cs.IT 2007
Year: 2007

We consider power allocation algorithms for fixed-rate transmission over Nakagami-m non-ergodic block-fading channels with perfect transmitter and receiver channel state information and discrete input signal constellations under both short- and long-term power constraints. Optimal power allocation schemes are shown to be direct applications of previous results in the literature. We show that the SNR exponent of the optimal short-term scheme is given by the Singleton bound. We also illustrate the significant gains available by employing long-term power constraints. Due to the nature of the expressions involved, the complexity of optimal schemes may be prohibitive for system implementation. We propose simple sub-optimal power allocation schemes whose outage probability performance is very close to the minimum outage probability obtained by optimal schemes.
Algorithms for laying points optimally on a plane and a circle
Venue: arXiv cs.CG 2007
Year: 2007

Two averaging algorithms are considered which are intended for choosing an optimal plane and an optimal circle approximating a group of points in three-dimensional Euclidean space.