OpenRaiser/Intern-Atlas huggingface dataset:
Efficient Multi-way Theta-Join Processing Using MapReduce
Venue: arXiv cs.DB 2012
Year: 2012

Multi-way Theta-join queries are powerful in describing complex relations and therefore widely employed in real practices. However, existing solutions from traditional distributed and parallel databases for multi-way Theta-join queries cannot be easily extended to fit a shared-nothing distributed computing paradigm, which is proven to be able to support OLAP applications over immense data volumes. In this work, we study the problem of efficient processing of multi-way Theta-join queries using MapReduce from a cost-effective perspective. Although there have been some works using the (key,value) pair-based programming model to support join operations, efficient processing of multi-way Theta-join queries has never been fully explored. The substantial challenge lies in, given a number of processing units (that can run Map or Reduce tasks), mapping a multi-way Theta-join query to a number of MapReduce jobs and having them executed in a well scheduled sequence, such that the total processing time span is minimized. Our solution mainly includes two parts: 1) cost metrics for both single MapReduce job and a number of MapReduce jobs executed in a certain order; 2) the efficient execution of a chain-typed Theta-join with only one MapReduce job. Comparing with the query evaluation strategy proposed in [23] and the widely adopted Pig Latin and Hive SQL solutions, our method achieves significant improvement of the join processing efficiency.
Matched Decoding for Punctured Convolutional Encoded Transmission Over ISI-Channels
Venue: arXiv cs.IT 2012
Year: 2012

Matched decoding is a technique that enables the efficient maximum-likelihood sequence estimation of convolutionally encoded PAM-transmission over ISI-channels. Recently, we have shown that the super-trellis of encoder and channel can be described with significantly fewer states without loss in Euclidean distance, by introducing a non-linear representation of the trellis. This paper extends the matched decoding concept to punctured convolutional codes and introduces a time-variant, non-linear trellis description.
Functional Mechanism: Regression Analysis under Differential Privacy
Venue: arXiv cs.DB 2012
Year: 2012

ε-differential privacy is the state-of-the-art model for releasing sensitive information while protecting privacy. Numerous methods have been proposed to enforce epsilon-differential privacy in various analytical tasks, e.g., regression analysis. Existing solutions for regression analysis, however, are either limited to non-standard types of regression or unable to produce accurate regression results. Motivated by this, we propose the Functional Mechanism, a differentially private method designed for a large class of optimization-based analyses. The main idea is to enforce epsilon-differential privacy by perturbing the objective function of the optimization problem, rather than its results. As case studies, we apply the functional mechanism to address two most widely used regression models, namely, linear regression and logistic regression. Both theoretical analysis and thorough experimental evaluations show that the functional mechanism is highly effective and efficient, and it significantly outperforms existing solutions.
OLTP on Hardware Islands
Venue: arXiv cs.DB 2012
Year: 2012

Modern hardware is abundantly parallel and increasingly heterogeneous. The numerous processing cores have non-uniform access latencies to the main memory and to the processor caches, which causes variability in the communication costs. Unfortunately, database systems mostly assume that all processing cores are the same and that microarchitecture differences are not significant enough to appear in critical database execution paths. As we demonstrate in this paper, however, hardware heterogeneity does appear in the critical path and conventional database architectures achieve suboptimal and even worse, unpredictable performance. We perform a detailed performance analysis of OLTP deployments in servers with multiple cores per CPU (multicore) and multiple CPUs per server (multisocket). We compare different database deployment strategies where we vary the number and size of independent database instances running on a single server, from a single shared-everything instance to fine-grained shared-nothing configurations. We quantify the impact of non-uniform hardware on various deployments by (a) examining how efficiently each deployment uses the available hardware resources and (b) measuring the impact of distributed transactions and skewed requests on different workloads. Finally, we argue in favor of shared-nothing deployments that are topology- and workload-aware and take advantage of fast on-chip communication between islands of cores on the same socket.
Accelerating Pathology Image Data Cross-Comparison on CPU-GPU Hybrid Systems
Venue: arXiv cs.DB 2012
Year: 2012

As an important application of spatial databases in pathology imaging analysis, cross-comparing the spatial boundaries of a huge amount of segmented micro-anatomic objects demands extremely data- and compute-intensive operations, requiring high throughput at an affordable cost. However, the performance of spatial database systems has not been satisfactory since their implementations of spatial operations cannot fully utilize the power of modern parallel hardware. In this paper, we provide a customized software solution that exploits GPUs and multi-core CPUs to accelerate spatial cross-comparison in a cost-effective way. Our solution consists of an efficient GPU algorithm and a pipelined system framework with task migration support. Extensive experiments with real-world data sets demonstrate the effectiveness of our solution, which improves the performance of spatial cross-comparison by over 18 times compared with a parallelized spatial database approach.
Only Aggressive Elephants are Fast Elephants
Venue: arXiv cs.DB 2012
Year: 2012

Yellow elephants are slow. A major reason is that they consume their inputs entirely before responding to an elephant rider's orders. Some clever riders have trained their yellow elephants to only consume parts of the inputs before responding. However, the teaching time to make an elephant do that is high. So high that the teaching lessons often do not pay off. We take a different approach. We make elephants aggressive; only this will make them very fast. We propose HAIL (Hadoop Aggressive Indexing Library), an enhancement of HDFS and Hadoop MapReduce that dramatically improves runtimes of several classes of MapReduce jobs. HAIL changes the upload pipeline of HDFS in order to create different clustered indexes on each data block replica. An interesting feature of HAIL is that we typically create a win-win situation: we improve both data upload to HDFS and the runtime of the actual Hadoop MapReduce job. In terms of data upload, HAIL improves over HDFS by up to 60% with the default replication factor of three. In terms of query execution, we demonstrate that HAIL runs up to 68x faster than Hadoop. In our experiments, we use six clusters including physical and EC2 clusters of up to 100 nodes. A series of scalability experiments also demonstrates the superiority of HAIL.
Mining Frequent Itemsets over Uncertain Databases
Venue: arXiv cs.DB 2012
Year: 2012

In recent years, due to the wide applications of uncertain data, mining frequent itemsets over uncertain databases has attracted much attention. In uncertain databases, the support of an itemset is a random variable instead of a fixed occurrence counting of this itemset. Thus, unlike the corresponding problem in deterministic databases where the frequent itemset has a unique definition, the frequent itemset under uncertain environments has two different definitions so far. The first definition, referred as the expected support-based frequent itemset, employs the expectation of the support of an itemset to measure whether this itemset is frequent. The second definition, referred as the probabilistic frequent itemset, uses the probability of the support of an itemset to measure its frequency. Thus, existing work on mining frequent itemsets over uncertain databases is divided into two different groups and no study is conducted to comprehensively compare the two different definitions. In addition, since no uniform experimental platform exists, current solutions for the same definition even generate inconsistent results. In this paper, we firstly aim to clarify the relationship between the two different definitions. Through extensive experiments, we verify that the two definitions have a tight connection and can be unified together when the size of data is large enough. Secondly, we provide baseline implementations of eight existing representative algorithms and test their performances with uniform measures fairly. Finally, according to the fair tests over many different benchmark data sets, we clarify several existing inconsistent conclusions and discuss some new findings.
Logarithmic Lipschitz norms and diffusion-induced instability
Venue: arXiv cs.SY 2012
Year: 2012

This paper proves that contractive ordinary differential equation systems remain contractive when diffusion is added. Thus, diffusive instabilities, in the sense of the Turing phenomenon, cannot arise for such systems. An important biochemical system is shown to satisfy the required conditions.
Botnet-based Distributed Denial of Service (DDoS) Attacks on Web Servers: Classification and Art
Venue: arXiv cs.CR 2012
Year: 2012

Botnets are prevailing mechanisms for the facilitation of the distributed denial of service (DDoS) attacks on computer networks or applications. Currently, Botnet-based DDoS attacks on the application layer are latest and most problematic trends in network security threats. Botnet-based DDoS attacks on the application layer limits resources, curtails revenue, and yields customer dissatisfaction, among others. DDoS attacks are among the most difficult problems to resolve online, especially, when the target is the Web server. In this paper, we present a comprehensive study to show the danger of Botnet-based DDoS attacks on application layer, especially on the Web server and the increased incidents of such attacks that has evidently increased recently. Botnet-based DDoS attacks incidents and revenue losses of famous companies and government websites are also described. This provides better understanding of the problem, current solution space, and future research scope to defend against such attacks efficiently.
Fixed Interfaces, Adaptive Interfaces... What is next? Total movability - a new paradigm for the user interface
Venue: arXiv cs.HC 2012
Year: 2012

Users can't talk with computers in their natural language (machine codes), so there are interfaces that allow such communication. 40 years ago the outcome of computer programs was in the form of long listings covered by numbers and even the format of those numbers was determined by developers. Throughout the latest 25 years: program views and results are shown in a wide variety of shapes and variants, but all these possibilities are predefined and fixed in code by developers; nothing outside of their approved solutions is allowed. My vision from now on into the future: developers are responsible only for correct work of a program (calculations, link with the database, etc.) and suggest a good default interface, but not determine all possible scenarios; only users decide WHAT, WHEN, and HOW to show. This will be a revolution in our dealing with computers, but there are obvious questions. How this step can be made? Do all users need such change? Is it going to be a burden for users or a welcome revolution?
On Constructor Rewrite Systems and the Lambda Calculus
Venue: arXiv cs.PL 2012
Year: 2012

We prove that orthogonal constructor term rewrite systems and lambda-calculus with weak (i.e., no reduction is allowed under the scope of a lambda-abstraction) call-by-value reduction can simulate each other with a linear overhead. In particular, weak call-by- value beta-reduction can be simulated by an orthogonal constructor term rewrite system in the same number of reduction steps. Conversely, each reduction in a term rewrite system can be simulated by a constant number of beta-reduction steps. This is relevant to implicit computational complexity, because the number of beta steps to normal form is polynomially related to the actual cost (that is, as performed on a Turing machine) of normalization, under weak call-by-value reduction. Orthogonal constructor term rewrite systems and lambda-calculus are thus both polynomially related to Turing machines, taking as notion of cost their natural parameters.
A Constructive Algorithm to Prove P=NP
Venue: arXiv cs.DS 2012
Year: 2012

After reducing the undirected Hamiltonian cycle problem into the TSP problem with cost 0 or 1, we developed an effective algorithm to compute the optimal tour of the transformed TSP. Our algorithm is described as a growth process: initially, constructing 4-vertexes optimal tour; next, one new vertex being added into the optimal tour in such a way to obtain the new optimal tour; then, repeating the previous step until all vertexes are included into the optimal tour. This paper has shown that our constructive algorithm can solve the undirected Hamiltonian cycle problem in polynomial time. According to Cook-Levin theorem, we argue that we have provided a constructive proof of P=NP.
Efficient and Secure Key Extraction using CSI without Chasing down Errors
Venue: arXiv cs.CR 2012
Year: 2012

Generating keys and keeping them secret is critical in secure communications. Due to the "open-air" nature, key distribution is more susceptible to attacks in wireless communications. An ingenious solution is to generate common secret keys by two communicating parties separately without the need of key exchange or distribution, and regenerate them on needs. Recently, it is promising to extract keys by measuring the random variation in wireless channels, e.g., RSS. In this paper, we propose an efficient Secret Key Extraction protocol without Chasing down Errors, SKECE. It establishes common cryptographic keys for two communicating parties in wireless networks via the realtime measurement of Channel State Information (CSI). It outperforms RSS-based approaches for key generation in terms of multiple subcarriers measurement, perfect symmetry in channel, rapid decorrelation with distance, and high sensitivity towards environments. In the SKECE design, we also propose effective mechanisms such as the adaptive key stream generation, leakage resilient consistence validation, and weighted key recombination, to fully exploit the excellent properties of CSI. We implement SKECE on off-the-shelf 802.11n devices and evaluate its performance via extensive experiments. The results demonstrate that SKECE achieves a more than 3x throughput gain in the key generation from one subcarrier in static scenarios, and due to its high efficiency, a 50% reduction on the communication overhead compared to the state-of-the-art RSS based approaches.
Vertex Nim played on graphs
Venue: arXiv cs.DM 2012
Year: 2012

Given a graph G with positive integer weights on the vertices, and a token placed on some current vertex u, two players alternately remove a positive integer weight from u and then move the token to a new current vertex adjacent to u. When the weight of a vertex is set to 0, it is removed and its neighborhood becomes a clique. The player making the last move wins. This adaptation of Nim on graphs is called Vertexnim, and slightly differs from the game Vertex NimG introduced by Stockman in 2004. Vertexnim can be played on both directed or undirected graphs. In this paper, we study the complexity of deciding whether a given game position of Vertexnim is winning for the first or second player. In particular, we show that for undirected graphs, this problem can be solved in quadratic time. Our algorithm is also available for the game Vertex NimG, thus improving Stockman's exptime algorithm. In the directed case, we are able to compute the winning strategy in polynomial time for several instances, including circuits or digraphs with self loops.
Universal Numeric Segment Display for Indian Scheduled Languages: an Architectural View
Venue: arXiv cs.OH 2012
Year: 2012

India is country of several hundred different languages. Though twenty two languages have only been devised as scheduled to the Eighth Schedule of Indian Constitution in 2007. But as there is yet no proposed compact display architecture to display all the scheduled language numerals at a time, this paper proposes a uniform display architecture to display all twenty two different language digits with higher accuracy and simplicity by using a 17-segment display, which is an improvement over the 16-segment display.
A Novel Approach of Color Image Hiding using RGB Color planes and DWT
Venue: arXiv cs.CR 2012
Year: 2012

This work proposes a wavelet based Steganographic technique for the color image. The true color cover image and the true color secret image both are decomposed into three separate color planes namely R, G and B. Each plane of the images is decomposed into four sub bands using DWT. Each color plane of the secret image is hidden by alpha blending technique in the corresponding sub bands of the respective color planes of the original image. During embedding, secret image is dispersed within the original image depending upon the alpha value. Extraction of the secret image varies according to the alpha value. In this approach the stego image generated is of acceptable level of imperceptibility and distortion compared to the cover image and the overall security is high.
Implementations of ICT Innovations: A Comparative Analysis in terms of Challenges between Developed and Developing Countries
Venue: arXiv cs.CY 2012
Year: 2012

The main aim of this paper is to achieve a depth of understanding of the various similarities and differences in terms of challenges between developed and developing countries and in regards to the implementation of ICT innovations. Indeed, advances in Information and Communication Technologies (ICTs) have brought many innovations to the field of Information Systems (IS). Despite agreements on their importance to the success of organizations, the implementation processes of such innovations are multifaceted and require proper addressing of a wide-spread issues and challenges. In this study, we address this matter by first; synthesizing a comprehensive body of recent and classified literature concerningfive ICTinitiatives,second;analyzing and classifying ICTs challenges forboth developed and developing countries as well as justifying their similarities and differences following thematic analysis qualitative methods, and third; presenting the study conclusions and identifying future research areas drawn upon theconducted comparative analysis.
Human Activity Learning using Object Affordances from RGB-D Videos
Venue: arXiv cs.CV 2012
Year: 2012

Human activities comprise several sub-activities performed in a sequence and involve interactions with various objects. This makes reasoning about the object affordances a central task for activity recognition. In this work, we consider the problem of jointly labeling the object affordances and human activities from RGB-D videos. We frame the problem as a Markov Random Field where the nodes represent objects and sub-activities, and the edges represent the relationships between object affordances, their relations with sub-activities, and their evolution over time. We formulate the learning problem using a structural SVM approach, where labeling over various alternate temporal segmentations are considered as latent variables. We tested our method on a dataset comprising 120 activity videos collected from four subjects, and obtained an end-to-end precision of 81.8% and recall of 80.0% for labeling the activities.
Design and implementation of a digital clock showing digits in Bangla font using microcontroller AT89C4051
Venue: arXiv cs.AR 2012
Year: 2012

In this paper, a digital clock is designed where the microcontroller is used for timing controller and the font of the Bangla digits are designed, and programmed within the microcontroller. The design is cost effective, simple and easy for maintenance.
Image encryption schemes for JPEG and GIF formats based on 3D baker with compound chaotic sequence generator
Venue: arXiv cs.CR 2012
Year: 2012

This paper proposed several methods to transplant the compound chaotic image encryption scheme with permutation based on 3D baker into image formats as Joint Photographic Experts Group (JPEG) and Graphics Interchange Format (GIF). The new method averts the lossy Discrete Cosine Transform and quantization and can encrypt and decrypt JPEG images lossless. Our proposed method for GIF keeps the property of animation successfully. The security test results indicate the proposed methods have high security. Since JPEG and GIF image formats are popular contemporarily, this paper shows that the prospect of chaotic image encryption is promising.
Social Trust as a solution to address sparsity-inherent problems of Recommender systems
Venue: arXiv cs.SI 2012
Year: 2012

Trust has been explored by many researchers in the past as a successful solution for assisting recommender systems. Even though the approach of using a web-of-trust scheme for assisting the recommendation production is well adopted, issues like the sparsity problem have not been explored adequately so far with regard to this. In this work we are proposing and testing a scheme that uses the existing ratings of users to calculate the hypothetical trust that might exist between them. The purpose is to demonstrate how some basic social networking when applied to an existing system can help in alleviating problems of traditional recommender system schemes. Interestingly, such schemes are also alleviating the cold start problem from which mainly new users are suffering. In order to show how good the system is in that respect, we measure the performance at various times as the system evolves and we also contrast the solution with existing approaches. Finally, we present the results which justify that such schemes undoubtedly work better than a system that makes no use of trust at all.
The concavity of Rènyi entropy power
Venue: arXiv cs.IT 2012
Year: 2012

We associate to the p-th Rényi entropy a definition of entropy power, which is the natural extension of Shannon's entropy power and exhibits a nice behaviour along solutions to the p-nonlinear heat equation in $R^n$. We show that the Rényi entropy power of general probability densities solving such equations is always a concave function of time, whereas it has a linear behaviour in correspondence to the Barenblatt source-type solutions. We then shown that the p-th Rényi entropy power of a probability density which solves the nonlinear diffusion of order p, is a concave function of time. This result extends Costa's concavity inequality for Shannon's entropy power to Rényi entropies.