Search results for "Information Systems"
showing 10 items of 1926 documents
Cost-driven framework for progressive compression of textured meshes
2019
International audience; Recent advances in digitization of geometry and radiometry generate in routine massive amounts of surface meshes with texture or color attributes. This large amount of data can be compressed using a progressive approach which provides at decoding low complexity levels of details (LoDs) that are continuously refined until retrieving the original model. The goal of such a progressive mesh compression algorithm is to improve the overall quality of the transmission for the user, by optimizing the rate-distortion trade-off. In this paper, we introduce a novel meaningful measure for the cost of a progressive transmission of a textured mesh by observing that the rate-distor…
Graph Clustering with Local Density-Cut
2018
In this paper, we introduce a new graph clustering algorithm, called Dcut. The basic idea is to envision the graph clustering as a local density-cut problem. To identify meaningful communities in a graph, a density-connected tree is first constructed in a local fashion. Building upon the local intuitive density-connected tree, Dcut allows partitioning a graph into multiple densely tight-knit clusters effectively and efficiently. We have demonstrated that our method has several attractive benefits: (a) Dcut provides an intuitive criterion to evaluate the goodness of a graph clustering in a more precise way; (b) Building upon the density-connected tree, Dcut allows identifying high-quality cl…
On the impact of forgetting on learning machines
1995
People tend not to have perfect memories when it comes to learning, or to anything else for that matter. Most formal studies of learning, however, assume a perfect memory. Some approaches have restricted the number of items that could be retained. We introduce a complexity theoretic accounting of memory utilization by learning machines. In our new model, memory is measured in bits as a function of the size of the input. There is a hierarchy of learnability based on increasing memory allotment. The lower bound results are proved using an unusual combination of pumping and mutual recursion theorem arguments. For technical reasons, it was necessary to consider two types of memory : long and sh…
A solution to the stochastic point location problem in metalevel nonstationary environments.
2008
This paper reports the first known solution to the stochastic point location (SPL) problem when the environment is nonstationary. The SPL problem involves a general learning problem in which the learning mechanism (which could be a robot, a learning automaton, or, in general, an algorithm) attempts to learn a "parameter," for example, lambda*, within a closed interval. However, unlike the earlier reported results, we consider the scenario when the learning is to be done in a nonstationary setting. For each guess, the environment essentially informs the mechanism, possibly erroneously (i.e., with probability p), which way it should move to reach the unknown point. Unlike the results availabl…
Boosting Textual Compression in Optimal Linear Time
2005
We provide a general boosting technique for Textual Data Compression. Qualitatively, it takes a good compression algorithm and turns it into an algorithm with a better compression performance guarantee. It displays the following remarkable properties: (a) it can turn any memoryless compressor into a compression algorithm that uses the “best possible” contexts; (b) it is very simple and optimal in terms of time; and (c) it admits a decompression algorithm again optimal in time. To the best of our knowledge, this is the first boosting technique displaying these properties.Technically, our boosting technique builds upon three main ingredients: the Burrows--Wheeler Transform, the Suffix Tree d…
Learning to Rank Images for Complex Queries in Concept-based Search
2018
Concept-based image search is an emerging search paradigm that utilizes a set of concepts as intermediate semantic descriptors of images to bridge the semantic gap. Typically, a user query is rather complex and cannot be well described using a single concept. However, it is less effective to tackle such complex queries by simply aggregating the individual search results for the constituent concepts. In this paper, we propose to introduce the learning to rank techniques to concept-based image search for complex queries. With freely available social tagged images, we first build concept detectors by jointly leveraging the heterogeneous visual features. Then, to formulate the image relevance, …
Work Partitioning on Parallel and Distributed Agent-Based Simulation
2017
Work partitioning is a key challenge with ap- plications in many scientific and technological fields. The problem is very well studied with a rich literature on both distributed and parallel computing architectures. In this paper we deal with the work partitioning problem for parallel and distributed agent-based simulations which aims at (i) balancing the overall load distribution, (ii) minimizing, at the same time, the communication overhead due to agents' inter-dependencies. We introduce a classification taxonomy of work partitioning strategies and present a space-based work partitioning ap- proach, based on a Quad-tree data structure, which enables to: identify a good space partitioning …
Global RDF Vector Space Embeddings
2017
Vector space embeddings have been shown to perform well when using RDF data in data mining and machine learning tasks. Existing approaches, such as RDF2Vec, use local information, i.e., they rely on local sequences generated for nodes in the RDF graph. For word embeddings, global techniques, such as GloVe, have been proposed as an alternative. In this paper, we show how the idea of global embeddings can be transferred to RDF embeddings, and show that the results are competitive with traditional local techniques like RDF2Vec.
Efficient evaluation for a subset of recursive queries
1991
Abstract We consider the efficient evaluation of recursive queries in logic databases where the queries are expressed using a Datalog program (function-free Horn-clause program) that contains only regularly or linearly recursive predicates. Using well-known results on graph traversal, we develop an efficient algorithm for evaluating relations defined by a binary-chain program. We also present a transformation by which the evaluation of a subset of queries involving nonbinary relations can be reduced to the evaluation of binary-chain queries. This transformation is guided by the choice of bound arguments in the query, and the bindings are propagated through the program so that in the evaluat…
Dictionary-symbolwise flexible parsing
2012
AbstractLinear-time optimal parsing algorithms are rare in the dictionary-based branch of the data compression theory. A recent result is the Flexible Parsing algorithm of Matias and Sahinalp (1999) that works when the dictionary is prefix closed and the encoding of dictionary pointers has a constant cost. We present the Dictionary-Symbolwise Flexible Parsing algorithm that is optimal for prefix-closed dictionaries and any symbolwise compressor under some natural hypothesis. In the case of LZ78-like algorithms with variable costs and any, linear as usual, symbolwise compressor we show how to implement our parsing algorithm in linear time. In the case of LZ77-like dictionaries and any symbol…