We consider the problem of duplicate document detection for search evaluation. Given a query and a small number of web results for that query, we show how to detect duplicate web documents with precision ~0.91 and recall ~77. In contrast, Charikar's algorithm, designed for duplicate detection in an indexing pipeline, achieves precision ~0.91 but with a recall of ~0.58. Our improvement in recall while maintaining high precision comes from combining three ideas. First, because we are only concerned with duplicate detection among results for the same query, the number of pairwise comparisons is small. Therefore we can afford to compute multiple pairwise signals for each pair of documents. A model learned with standard machine-learning techniques improves recall to ~0.68 with precision ~0.90. Second, most duplicate detection has focused on text analysis of the HTML contents of a document. In some web pages the HTML is not a good indicator of the final contents of the page. We use extended fetching techniques to fill in frames and execute Java script. Including signals based on our richer fetches further improves the recall to ~0.75 and the precision to ~0.91. Finally, we also explore using signals based on the query. Comparing contextual snippets based on the richer fetches improves the recall to ~0.77. We show that the overall accuracy of this final model approaches that of human judges.

Stratified Datalog with integer (gap)-order (or Datalog ¬,< z ) is considered. A Datalog ¬,< z -program is said to be safe if its bottom-up processing terminates on all valid inputs. We prove that safe Datalog ¬,< z programs do not have effective syntax in the sense that there is no recursively enumerable set S of safe Datalog ¬,< z programs such that every safe Datalog ¬,< z program is equivalent to a program in S .

We generalize the pebble game to infinite directed acyclic graphs and use this generalization to give new and shorter proofs of the following well-known results: (1) that unbounded memory increases the power of logics of programs, and (2) that there exists a context-free grammar with infinite index.

Abstract We show that no formula of first order logic using linear ordering and the logical relationy= 2xcan define the property that the size of a finite model is divisible by 3. This answers a long-standing question which may be of relevance to certain open problems in circuit complexity.

We consider relational databases organized over an ordered domain with some additional relations---a typical example is the ordered domain of rational numbers together with the ternary relation + of addition. In the focus of our study are the first order queries that are invariant under order-preserving "permutations"---such queries are called (order-)generic. We show that for an arbitrary ordered divisible Abelian group order-generic queries fail to express more than pure order queries, and that, moreover, the generic queries can be effectively translated into pure order queries. For example, every order-generic query over rational numbers with + can be effectively rewritten without +. An important difference of this paper from a recent series of related pape...

A characterization of definability by positive first order formulas in terms of Fraisse-Ehrenfeucht-like games is developed. Using this characterization, an elementary, purely combinatorial, proof of the failure of Lyndon's Lemma (1959) (that every monotone first order property is expressible positively) for finite models is given. The proof implies that first order logic is a bad candidate for the role of a uniform version of positive Boolean circuits of constant depth and polynomial size. Although Lyndon's Lemma fails for finite models, same similar characterization may be established for finitely monotone properties, and we formulate a particular open problem in this direction.

A relational query is called finite, or sometimes safe, iff it yields a finite answer in every database state.The set of finite queries of relational calculus is known to be unsolvable.However, in many cases it is possible to impose syntactical restrictions on the class of queries that guarantee finiteness and do not reduce the expressive power of the calculus.We show that unfortunately this is not always the case, as we construct a recursive domain with decidable theory where any solvable (or enumerable, for that matter) subclsss of queries either contains an infinite query, or misses a finite one.Using the same example, we further show undecidability of the problem of state-jinitene.w,which is, given a query and a database state, to decide upon finiteness of the query in this state.ThB settles two long-standing open problems in the theory of relational databases.

It is shown that no formula of first-order logic using linear ordering and the logical relation y=2x can define the property that the size of a finite model is divisible by 3. This answers a long-standing question that may be of relevance to certain open problems in circuit complexity.>

It may happen that a first order formula with two free variables over a signature defines a linear order of some finite structure of the signature. Then, naturally, this finite structure is rigid, i.e. admits the single (trivial) automorphism. Also, the class of all the finite structures such that the formula defines a linear order on any of them, is finitely axiomatizable in the class of all finite structures (of the signature). It is shown that the inverse is not true, i.e. that there exists a finitely axiomatizable class of rigid finite structures, such that no first-order formula defines a linear order on all the structures of the class. To illustrate possible applications of the result in finite model theory, it is shown that Y. Gurevich's (1984) result that E.W. Beth's (1953) definability theorem fails for finite models is an immediate corollary.>

The class of so called Adian's structures with pairwise different exponents is considered. It is known that both deterministic dynamic logic (DDL) and context-free DDL (CF-DDL) have an unwind property in every structure Gamma in the class; thus they are equivalent in Gamma to first-order logic. None the less, it turns out that these three logics have different complexity bounds in the class. The main result is to prove polynomial upper bounds for DDL formulas. As a corollary, the authors find the DDL and CF-DDL are unequivalent to one another in the class. The proof remains valid even in the presence of elementary tests and rich tests.>