Search

We present a succinct data structure for permutation graphs, and their superclass of circular permutation graphs, i.e., data structures using optimal space up to lower order terms. Unlike concurrent work on circle graphs (Acan et al. in Theor Comput Sci, https://doi.org/10.1016/j.tcs.2022.06.022, 2022), our data structure also supports distance and shortest-path queries, as well as adjacency and neighborhood queries, all in optimal time. We present in particular the first succinct exact distance oracle for (circular) permutation graphs. A second succinct data structure also supports degree queries in time independent of the neighborhood's size at the expense of an O (log n / log log n) -factor overhead in all running times. Furthermore, we develop a succinct data structure for the class of bipartite permutation graphs. We demonstrate how to run algorithms directly over our succinct representations for several problems on permutation graphs: Clique, Coloring, Independent Set, Hamiltonian Cycle, All-Pair Shortest Paths, and others. Finally, we initiate the study of semi-distributed graph representations; a concept that smoothly interpolates between distributed (labeling schemes) and centralized (standard data structures). We show how to turn some of our data structures into semi-distributed representations by storing only O (n) bits of additional global information, circumventing the lower bound on distance labeling schemes for permutation graphs. [ABSTRACT FROM AUTHOR]

Sentiment lexicons and word embeddings constitute well-established sources of information for sentiment analysis in online social media. Although their effectiveness has been demonstrated in state-of-the-art sentiment analysis and related tasks in the English language, such publicly available resources are much less developed and evaluated for the Greek language. In this paper, we tackle the problems arising when analyzing text in such an under-resourced language. We present and make publicly available a rich set of such resources, ranging from a manually annotated lexicon, to semi-supervised word embedding vectors and annotated datasets for different tasks. Our experiments using different algorithms and parameters on our resources show promising results over standard baselines; on average, we achieve a 24.9% relative improvement in F-score on the cross-domain sentiment analysis task when training the same algorithms with our resources, compared to training them on more traditional feature sources, such as n-grams. Importantly, while our resources were built with the primary focus on the cross-domain sentiment analysis task, they also show promising results in related tasks, such as emotion analysis and sarcasm detection. [ABSTRACT FROM AUTHOR]

Shallow cuttings are one of the most fundamental tools in range searching as many problems in the field admit efficient static data structures due to their application. We present the first efficient deterministic algorithms that, given n three-dimensional points, construct optimal-size (single and multiple) shallow cuttings for orthogonal dominance ranges. Specifically, we show how to construct a single shallow cutting in Onlogn worst-case time, using On space. We also show that the same complexity suffices to construct simultaneously a logarithmic number of shallow cuttings on the input pointset. Our algorithms are optimal in the comparison and algebraic-comparison models, and constitute an important step forwards as the first improvement over previous deterministic polynomial-time guarantees by Matoušek (Comput Geom 2(3):169-186, 1992) and Agarwal et al. (SIAM J Comput 29(3):912-953, 2000) matching the complexity of the optimal deteministic algorithm for the more general 3-d halfspace ranges by Chan and Tsakalidis (Discrete Comput Geom 56(4):866-881, 2016). Our methods yield worst-case efficient preprocessing algorithms for a series of important orthogonal range searching problems in the pointer machine and the word-RAM models, where such shallow cuttings are utilized to support queries efficiently. [ABSTRACT FROM AUTHOR]

We present optimal deterministic algorithms for constructing shallow cuttings in an arrangement of lines in two dimensions or planes in three dimensions. Our results improve the deterministic polynomial-time algorithm of Matoušek (Comput Geom 2(3):169-186, 1992) and the optimal but randomized algorithm of Ramos (Proceedings of the Fifteenth Annual Symposium on Computational Geometry, SoCG'99, 1999). This leads to efficient derandomization of previous algorithms for numerous well-studied problems in computational geometry, including halfspace range reporting in 2-d and 3-d, k nearest neighbors search in 2-d, $$({\le }k)$$ -levels in 3-d, order- k Voronoi diagrams in 2-d, linear programming with k violations in 2-d, dynamic convex hulls in 3-d, dynamic nearest neighbor search in 2-d, convex layers (onion peeling) in 3-d, $$\varepsilon $$ -nets for halfspace ranges in 3-d, and more. As a side product we also describe an optimal deterministic algorithm for constructing standard (non-shallow) cuttings in two dimensions, which is arguably simpler than the known optimal algorithms by Matoušek (Discrete Comput Geom 6(1):385-406, 1991) and Chazelle (Discrete Comput Geom 9(1):145-158, 1993). [ABSTRACT FROM AUTHOR]

Dementia affects cognitive functions of adults, including memory, language, and behaviour. Standard diagnostic biomarkers such as MRI are costly, whilst neuropsychological tests suffer from sensitivity issues in detecting dementia onset. The analysis of speech and language has emerged as a promising and non-intrusive technology to diagnose and monitor dementia. Currently, most work in this direction ignores the multi-modal nature of human communication and interactive aspects of everyday conversational interaction. Moreover, most studies ignore changes in cognitive status over time due to the lack of consistent longitudinal data. Here we introduce a novel fine-grained longitudinal multi-modal corpus collected in a natural setting from healthy controls and people with dementia over two phases, each spanning 28 sessions. The corpus consists of spoken conversations, a subset of which are transcribed, as well as typed and written thoughts and associated extra-linguistic information such as pen strokes and keystrokes. We present the data collection process and describe the corpus in detail. Furthermore, we establish baselines for capturing longitudinal changes in language across different modalities for two cohorts, healthy controls and people with dementia, outlining future research directions enabled by the corpus. [ABSTRACT FROM AUTHOR]

This study is an attempt to describe a conventional breeding program on Greek oregano (Origanum vulgare ssp. hirtum). First of all, a descriptor list including the most significant morphological traits was developed for the starting genetic material. The program aimed to select the elite selfplants obtained from the initial population originated from Samothraki Island, in purpose to generate the ideotype of a new cultivar, characterized by desirable agronomical traits and qualitative properties. Therefore, a pedigree intraselection method, based on widely spaced single-plant performance through honeycomb arrangement, was applied. The existing genetic/phenotypic variability of plants and families produced after selection was evaluated for plant’s growth and biomass density, type of stems and inflorescences and their components of yield potential. In addition, the effect of the mode of pollination on plants’ performance from two types of families obtained from self (SP) and open pollination (OP) was assessed. The evaluation for the components of yield potential, the composition of essential oil and carvacrol content, was detected in selected self plants, revealing genotypes with high yield potential. The target of this breeding program was the selection for high essential oil and carvacrol content and stabilization of valuable herbage components. The main selection criteria; high carvacrol and essential oil content, dry weight of leaves and flowers, ratio of leaves and flowers per stem, were subjected to statistical analysis using analytic hierarchy process, and plants were ranking according to their performance. The end-scope of this research was to recombine or even improve the starting population of local population of Greek oregano, according to mean essential oil content and carvacrol, biomass production and uniformity in desirable yield components using efficient breeding and statistical tools of selection. [ABSTRACT FROM AUTHOR]

We present a new finger search tree with O(loglog d) expected search time in the Random Access Machine (RAM) model of computation for a large class of input distributions. The parameter d represents the number of elements (distance) between the search element and an element pointed to by a finger, in a finger search tree that stores n elements. Our data structure improves upon a previous result by Andersson and Mattsson that exhibits expected O(loglog n) search time by incorporating the distance d into the search time complexity, and thus removing the dependence on n. We are also able to show that the search time is O(loglog d+ ϕ( n)) with high probability, where ϕ( n) is any slowly growing function of n. For the need of the analysis we model the updates by a 'balls and bins' combinatorial game that is interesting in its own right as it involves insertions and deletions of balls according to an unknown distribution. [ABSTRACT FROM AUTHOR]