Search

We study the problem of sub-trajectory nearest-neighbor queries on polygonal curves under the continuous Fréchet distance. Given an n vertex trajectory P and an m vertex query trajectory Q , we seek to report a vertex-aligned sub-trajectory P ′ of P that is closest to Q , i.e., P′ must start and end on contiguous vertices of P . Since in real data P typically contains a very large number of vertices, we focus on answering queries, without restrictions on P or Q , using only precomputed structures of 𝒪(n) size. We use three baseline algorithms from straightforward extensions of known work; however, they have impractical performance on realistic inputs. Therefore, we propose a new Hierarchical Simplification Tree (HST) data structure and an adaptive clustering-based query algorithm that efficiently explores relevant parts of P . The core of our query methods is a novel greedy-backtracking algorithm that solves the Fréchet decision problem using 𝒪(n+m) space and 𝒪O(nm) time in the worst case. Experiments on real and synthetic data show that our heuristic effectively prunes the search space and greatly reduces computations compared to baseline approaches.

This work deals with the clustering of information sources for epipole estimation in a multi-camera system. For this problem, each pair of matched visual features in the images can be considered as an elementary information source. The epipole is then estimated by combining these elementary sources taking into account their inadequacy, in particular large imprecision and presence of outliers, as well as the very large number of sources. We address the challenges introduced by a large number of sources with a strategy based on clustering and intra-cluster fusion using the Belief Functions framework. When evaluated on real data, the proposed algorithm exhibits more robustness in terms of accuracy and precision than the standard approaches which provide singular solutions.

Very large numbers words such as “hundred,” “thousand,” “million,” “billion,” and “trillion” pose a learning problem for children because they are sparse in everyday speech and children's experience with extremely large quantities is scarce. In this study, we examine when children acquire the relative ordering of very large number words as a first step toward understanding their acquisition. In Study 1, a hundred and twenty-five 5–8-year-olds participated in a verbal number comparison task involving very large number words. We found that children can judge which of two very large numbers is more as early as age 6, prior to entering first grade. In Study 2, we provided a descriptive analysis on the usage of very large number words using the CHILDES database. We found that the relative frequency of large number words does not change across the years, with “hundred” uttered more frequently than others by an order of magnitude. We also found that adults were more likely to use large number words to reference units of quantification for money, weight, and time, than for discrete, physical entities. Together, these results show that children construct a numerical scale for large number words prior to learning their precise cardinal meanings, and highlight how frequency and context may support their acquisition. Our results have pedagogical implications and highlight a need to investigate how children acquire meanings for number words that reference quantities beyond our everyday experience.

International audience; Massive biological datasets are available in various sources. To answer a biological question (e.g., ''which are the genes involved in a given disease?''), life scientists query and mine such datasets using various techniques. Each technique provides a list of results usually ranked by importance (e.g., a list of ranked genes). Combining the results obtained by various techniques, that is, combining ranked lists of elements into one list of elements is of paramount importance to help life scientists make the most of various results and prioritize further investigations. Rank aggregation techniques are particularly well-fitted with this context as they take in a set of rankings and provide a consensus, that is, a single ranking which is the ''closest'' to the input rankings. However, (i) the problem of rank aggregation is NP-hard in most cases (using an exact algorithm is currently not possible for more than a few dozens of elements) and (ii) several (possibly very different) exact solutions can be obtained. As answer to (i), many heuristics and approximation algorithms have been proposed. However, heuristics cannot guarantee how far from an exact solution the consensus ranking will be, and the approximation ratio of approximation algorithms dedicated to the problem is fairly high (not less than 3/2). No solution has yet been proposed to help true-users dealing with the problem encountered in point (ii). In this paper we present a complete system able to perform rank aggregation of massive biological datasets. Our solution is efficient as it is based on an original partitioning method making it possible to compute a high-quality consensus using an exact algorithm in a large number of cases. Our solution is robust as it clearly identifies for the user groups of elements whose relative order is the same in any optimal solution. These features provide answers to points (i) and (ii) and lie in mathematical bases offering guarantees on the computed result. Also, our solution is effective as it has been implemented into a real tool, ConquR-BioV2 is used for the life science community, and evaluated at large-scale using a very large number of datasets.

The aim of this paper is to establish a theorem associated with the product of the Aleph-function, the multivariable Aleph-function, and the general class of polynomials. The results of this theorem are unified in nature and provide a very large number of analogous results (new or known) involving simpler special functions and polynomials (of one or several variables) as special cases. The derived results lead to significant applications in physics and engineering sciences.

The Automatic Quasi-clique Merger algorithm is a new algorithm adapted from early work published under the name QCM “introduced by Ou and Zhang (JIMO 2007)”. The AQCM algorithm performs hierarchical clustering in any data set for which there is an associated similarity measure quantifying the similarity of any data i and data j. Importantly, the method exhibits two valuable performance properties: (1) the ability to automatically return either a larger or smaller number of clusters depending on the inherent properties of the data rather than on a parameter. (2) the ability to return a very large number of relatively small clusters automatically when such clusters are reasonably well defined in a data set. In this work we present the general idea of a quasi-clique agglomerative approach, provide the full details of the mathematical steps of the AQCM algorithm, and explain some of the motivation behind the new methodology. The main achievement of the new methodology is that the agglomerative process now unfolds adaptively according to the inherent structure unique to a given data set, and this happens without the time-costly parameter adjustment that drove the previous QCM algorithm. For this reason we call the new algorithm automatic. We provide a demonstration of the algorithm’s performance at the task of community detection in a social media network of 22,900 nodes.