1,721,128 research outputs found
Maximal chains and antichains in strongly noetherian semiorders
No full textIn the field of abstract measurement theory, semiorders have assumed an especially important role as a natural setting for expressing the comparative relations among the magnitudes of measurands. If we assume in addition that our measuring scale is bounded below, which happens in many important cases, we get an interesting class of semiorders, the strongly noetherian ones. In this work, we study some combinatorial and order-theoretic properties of strongly noetherian semiorders, with a particular regard to the structure of maximal chains and antichains (called lines and cuts in the present paper). We see that the cuts determine a sort of dynamics in the semiorder, which may be described as a linear order on the cuts themselves; from this linear order one can extract the main properties of the original semiorder, whose elements are represented as closed intervals of cuts. Moreover, "continuity" properties such as K-density and coherence have a natural description in term of simple cut properties; as a corollary, we obtain that K-density is equivalent to N-freeness in strongly noetherian semiorders
WebGraph: things you thought you could not do with Java
No full textStudying web graphs is often difficult due to their large size. The WebGraph framework is a suite of codes, algorithms and tools that make it easy to manipulate large web graphs, and to store them in a limited space, by exploiting the inner redundancies of the web. WebGraph is based on sophisticated bitwise compression techniques, and functional-style lazy constructions. Common wisdom would say that the most unlikely language to implement such a framework is Java. We are going to tell you the real story
Sux4J 1.0
No full textSux4J is a set of Java classes providing state-of-the-art implementations of succinct data structures
WebGraph 1.1
No full textWebGraph is a framework to study the web graph. It provides simple ways to manage very large graphs, exploiting modern compression techniques
Efficient optimally lazy algorithms for minimal-interval semantics
No full textMinimal-interval semantics associates with each query over a document a set of intervals, called witnesses, that are incomparable with respect to inclusion (i.e., they form an antichain): witnesses define the minimal regions of the document satisfying the query. Minimal-interval semantics makes it easy to define and compute several sophisticated proximity operators, provides snippets for user presentation, and can be used to rank documents. In this paper we provide algorithms for computing conjunction and disjunction that are linear in the number of intervals and logarithmic in the number of operands; for additional operators, such as ordered conjunction and Brouwerian difference, we provide linear algorithms. In all cases, space is linear in the number of operands. More importantly, we define a formal notion of optimal laziness, and either prove it, or prove its impossibility, for each algorithm. We cast our results in a general framework of antichains of intervals on total orders, making our algorithms directly applicable to other domains
The WebGraph framework I : compression techniques
No full textStudying web graphs is often difficult due to their large size. Recently, several proposals have been published about various techniques that allow to store a web graph in memory in a limited space, exploiting the inner redundancies of the web. The WebGraph framework is a suite of codes, algorithms and tools that aims at making it easy to manipulate large web graphs. This papers presents the compression techniques used in WebGraph, which are centred around referentiation and intervalisation (which in turn are dual to each other). WebGraph can compress the WebBase graph (118 Mnodes, 1 Glinks) in as little as 3.08 bits per link, and its transposed version in as little as 2.89 bits per link
Complexity of deciding sense of direction
No full textIn this paper we prove that deciding whether a distributed system (represented as a coloured digraph with n nodes) has weak sense of direction is in AC^1 (using n^6 processors). Moreover, we show that deciding sense of direction is in P. Our algorithms can also be used to decide in AC^1 whether a coloured graph is a Cayley colour graph
MG4J 2.2
No full textMG4J is a large-scale, high-performance search engine. Version 2.x provides a whole set of new features, including more operators, more efficient algorithms, and more flexible scoring
On the Lattice of Antichains of Finite Intervals
No full textMotivated by applications to information retrieval, we study the lattice of antichains of finite intervals of a locally finite, totally ordered set. Intervals are ordered by reverse inclusion; the order between antichains is induced by the lower set they generate. We discuss in general properties of such antichain completions; in particular, their connection with Alexandrov completions. We prove the existence of a unique, irredundant ∧-representation by ∧-irreducible elements, which makes it possible to write the relative pseudo-complement in closed form. We also discuss in detail properties of additional interesting operators used in information retrieval. Finally, we give a formula for the rank of an element and for the height of the lattice
MG4J (Managing Gigabyte for Java) 1.1
No full textMG4J (Managing Gigabytes for Java) is a free full-text search engine for large document collections written in Java. As a by-product, it offers several general-purpose optimised classes, including fast & compact mutable strings, bit-level I/O, (possibly signed) minimal perfect hashing for very large strings collections, etc
- …
