Abstract

We present output sensitive techniques for the generalized reporting versions of the planar range maxima problem and the planar range convex hull problem. Our solutions are in the pointer machine model, for orthogonal range queries on a static point set. We solve the planar range maxima problem for two-sided, three-sided and four-sided queries. We achieve a query time of O(logn + c) using O(n) space for the two-sided case, where n denotes the number of stored points and c the number of colors reported. For the three-sided case, we achieve query time O(log2 n + clogn) using O(n) space while for four-sided queries we answer queries in O(log3 n + clog2 n) using O(nlogn) space. For the planar range convex hull problem, we provide a solution that answers queries in O(log2 n + clogn) time, using O(nlog2 n) space.

Abstract

We propose a supervised learning technique defining significant frequent patterns for associative regression. Assuming frequent patterns quantify correlations in dataset, we constrain the Generalized Iterative Scaling (GIS) convergence algorithm for Maximum Entropy (ME) models. We have used the combinations of ME parameters and GIS probabilities as discriminative weights to frequent patterns. The weighted frequent patterns then order the predictive analytics output. Experiments are conducted on sparse numeric datasets. Results suggest that condensed representations of frequent patterns allow parametric models suitable for class association rule mining.

Abstract

We present here, TagMiner, a data mining approach for part-of-speech (POS) tagging, an important Natural language process-ing (NLP) classification task. It is a semi-supervised associative clas-sification method for POS tagging. Existing methods for building POS taggers require extensive domain and linguistic knowledge and resources.Our method uses combination of a small POS tagged corpus and a raw untagged text data as training data to build the classifier model using association rules. Our tagger works well with very little training dataalso. The use of semi-supervised learning provides the advantage of notrequiring a large high quality tagged corpus. These properties make it es-pecially suitable for resource poor languages. Our experiments on various resource-rich, resource-moderate and resource-poor languages show good performance without using any language specific linguistic information.We note that inclusion of such features in our method may further im-prove the performance. Results also show that for smaller training data sizes our tagger performs better than state-of-the-art CRF tagger using same features as our tagger.

Abstract

We propose a supervised learning technique for associative regression. Assuming frequent patterns quantify correlations in dataset, we constrain the Sequential Conditional Generalized Iterative Scaling (SCGIS) convergence algorithm for Maximum Entropy (ME) models. We also assume prior probabilities on the ME model as a control on the step size in SCGIS. We have used the combinations of ME parameters and SCGIS probabilities as discriminative weights to frequent patterns. The weighted frequent patterns then predict the associative regression values. Experiments have been conducted on sparse numeric datasets, to find the regression error of our proposal. Our technique is comparable to the standard regression algorithms. As a concept, the proposed associative regression is useful as a parametric model in class association rule mining.

Abstract

Studies on the emotion recognition task indicate that there is confusion in discrimination among higher activation states like ‘anger’ and ‘happy’. In this study, features related to excitation source of speech are examined for discriminating ‘anger’ and ‘happy’ emotions. The objective is to explore the features which are independent of lexical content, language, channel and speaker. The features like strength of excitation from zero frequency filtering method and spectral band magnitude energies from short-time spectral analysis are used. Experimental results show that these features can discriminate ‘anger’ and ‘happy’ emotion states to a good extent.

Abstract

Speech-laugh is a speech-synchronous form of laughter that often occurs in natural conversation. However, there are deviations in features of speech-laugh when compared with laughter and neutral speech individually. The objective of this study is to analyse the excitation source features to capture the deviations between laughter and speech-laughs in voiced regions. The features used in this analysis are based on instantaneous fundamental frequency and strength of excitation (β) at epochs. Modified zero frequency filtering (ZFF) method is used to extract the features. Kullback-Leibler (KL) distances obtained show that there are deviations in excitation source features which can be exploited to develop a method to discriminate speech-laughs from laughter. Experimental results show that features used are robust and speaker independent in discriminating speech-laughs from laughter. Results showing deviations of laughter and speech-laughs from neutral speech were also presented.

Abstract

The scan-line corrector (SLC) of the Landsat 7 Enhanced Thematic Mapper Plus (ETM+) sensor failed in May 2003, and this abnormal functioning of SLC resulted in about 22% of the pixels per scene without being scanned. By filling the un-scanned gap by a good technique will help in more use of ETM+ data for many scientific applications. While there have been a number of approaches developed to fill in the data gaps in ETM+ imagery, each method has shortcomings, especially they require SLC-on (images acquired before SLC-off anomaly) imagery for the same location to fill the gaps in SLC-off (images acquired after SLC anomaly) image. To overcome such shortcomings this study proposes an alternative interpolation method based on the partial derivative. This case study shows that this technique is very much useful to interpolate the missing pixel values in the SLC-off ETM+ data.

Abstract

The deterioration and loss of water bodies like lakes due to anthropogenic activities, are at the same pace at which forests are degraded. Lakes and ponds play a major role in the global cycle (carbon, water, etc.). They act as the basic units of hydrological systems to better understand the biogeochemical processes that take place within these aquatic systems and further for their management plans. As an initiative of managing resources at the unit level (lake) in the current study, we tried to understand the history and ecological dynamics of" Brahmayyalingam Cheruvu", a lake located in the peri-urban areas of the rapidly expanding Vijayawada city, Andhra Pradesh State, India. The study is based on field inventories, local surveys and satellite data, both current and past. Use of satellite images aided in capturing the changing spatiao-temporal lake dynamics due to climatic variations and government policy. The …

Abstract

In this work, we consider the problem of finding the closest pair (in L 1 metric) of points in an orthogonal query rectangle. Given a set of n static points on a U× U grid, we preprocess these points into a data structure of size O (m f (m) log 2 m) that can be queried in time O ((g (m)+ log log m) log 3 m), for m= O (n log U) and (i) f (m)= O (1) and g (m)= O (log ε m);(ii) f (m)= O (log log m) and g (m)= O (log log m);(iii) f (m)= O (log ε m) and g (m)= O (1). Here ε: 0< ε< 1 is a small but arbitrary constant.

Abstract

A t-ruling set of a graph G=(V, E) is a vertex-subset S⊆ V that is independent and satisfies the property that every vertex v∈ V is at a distance of at most t hops from some vertex in S. A maximal independent set (MIS) is a 1-ruling set. Extending results from Kothapalli et al.(FSTTCS 2012) this note presents a randomized algorithm for computing, with high probability, a t-ruling set in O (t⋅ log 1/(t-1) n) rounds for 2< t≤√(log log n) and in (O (√(log log n))) rounds for t>√(log log n).