Parallel query processing on distributed clustering indexes

Similarity search has been proved suitable for searching in large collections of unstructured data objects. A number of practical index data structures for this purpose have been proposed. All of them have been devised to process single queries sequentially. However, in large-scale systems such as Web Search Engines indexing multi-media content, it is critical to deal efficiently with streams of queries rather than with single queries. In this paper we show how to achieve efficient and scalable performance in this context. To this end we transform a sequential index based on clustering into a distributed one and devise algorithms and optimizations specially tailored to support high-performance parallel query processing.     

Investigating a claim for Russian priority in the abstract definition of a ring

In this article, I scutinize an assertion that the Russian-Ukrainian mathematician S O Shatunovskii (1859–1929) should be credited with the first modern definition of a ring. Shatunovskii’s claim is compared with that of Abraham Fraenkel, who defined a notion very close to the current concept of a ring in a paper of 1914.     

Zipf’s law and L. Levin probability distributions

Zipf’s law in its basic incarnation is an empirical probability distribution governing the frequency of usage of words in a language. As Terence Tao recently remarked, it still lacks a convincing and satisfactory mathematical explanation. In this paper I suggest that, at least in certain situations, Zipf’s law can be explained as a special case of the a priori distribution introduced and studied by L. Levin. The Zipf ranking corresponding to diminishing probability appears then as the ordering by growing Kolmogorov complexity. One argument justifying this assertion is the appeal to a recent interpretation by Yu. Manin and M. Marcolli of asymptotic bounds for error-correcting codes in terms of phase transition. In the respective partition function, the Kolmogorov complexity of a code plays the role of its energy.     

Finitely additive,modular, and probability functions on pre-Semirings

In this paper, we define finitely additive, probability and modular functions over semiring-like structures. We investigate finitely additive functions with the help of complemented elements of a semiring. We also generalize some classical results in probability theory such as the law of total probability, Bayes’ theorem, the equality of parallel systems, and Poincaré’s inclusion-exclusion theorem. While we prove that modular functions over a couple of known semirings are almost constant, we show it is possible to define many different modular functions over some semirings such as bottleneck algebras and the semiring (Id(D),+,?), where D is a Dedekind domain.     

A parallel implementation of Wang’s method for solving tridiagonal systems

In this paper, a parallel implementation of Wang’s method for solving tridiagonal system of equations on the multiprocessor machine using occam language is presented. The parallel algorithm has been designed for shared and distributed memory machine that support data parallel and message passing. The over all performance of this implementation on 9 each of processors is given. The communication times are very important and any improvement on this communication would have a significant performance of the implementation. The significance of these results are discussed.     

On residually finite groups of finite general rank

Following A. I.Mal’tsev, we say that a group G has finite general rank if there is a positive integer r such that every finite set of elements of G is contained in some r-generated subgroup. Several known theorems concerning finitely generated residually finite groups are generalized here to the case of residually finite groups of finite general rank. For example, it is proved that the families of all finite homomorphic images of a residually finite group of finite general rank and of the quotient of the group by a nonidentity normal subgroup are different. Special cases of this result are a similar result of Moldavanskii on finitely generated residually finite groups and the following assertion: every residually finite group of finite general rank is Hopfian. This assertion generalizes a similarMal’tsev result on the Hopf property of every finitely generated residually finite group.     

Costing communication standards in information systems using a minimum cut approach

On a very abstract level, an information system consists of a set of system elements which communicate with each other. Communication is an unproductive operation, so the time needed to communicate data should be kept as short as possible and, to put it in monetary terms, the opportunity costs for communication should be kept small. Now, communicating data is more than just transmitting it; it consists in large parts of converting data structures that are used by one system element into data structures that are used by another system element. Such conversion can be avoided, if the system elements, use a common standard of data structures. Since establishing a standard at a system element incurs standardization costs, a decision-maker has to check, if the cost savings gained by standardized communication outweigh the costs for installing the standard. In a recent paper by Buxmann et al¹, it is claimed that this so-called standardization problem is an NP-hard optimization problem without giving a formal proof for it. We will demonstrate that this claim is not true, but in fact the standardization problem can be solved in polynomial time by solving a minimum cut problem.     

Jumping coefficients and spectrum of a hyperplane arrangement

In an earlier version of this paper written by the second named author, we showed that the jumping coefficients of a hyperplane arrangement depend only on the combinatorial data of the arrangement as conjectured by Mustaţǎ. For this we proved a similar assertion on the spectrum. After this first proof was written, the first named author found a more conceptual proof using the Hirzebruch–Riemann–Roch theorem where the assertion on the jumping numbers was proved without reducing to that for the spectrum. In this paper we improve these methods and show that the jumping numbers and the spectrum are calculable in low dimensions without using a computer. In the reduced case we show that these depend only on fewer combinatorial data, and give completely explicit combinatorial formulas for the jumping coefficients and (part of) the spectrum in the case the ambient dimension is 3 or 4. We also give an analogue of Mustaţǎ’s formula for the spectrum.     

Collateral in banking policy: On the possibility of signaling

In this paper we study the validity of the assertion that collateral is in a position to signal the degree of borrowers’ riskiness. We use a framework in which the cash flow from the risky project is described by means of a continuous density and projects are classified by second-order stochastic dominance. We show that if collateral is assumed bounded by the initial project outlay the positive role of collateral, namely truthfully conveying the private information about the project risk by the collateral amount, can no longer be ensured.     

Parallel Algorithms and Probability of Large Deviation for Stochastic Convex Optimization Problems

We consider convex stochastic optimization problems under different assumptions on the properties of available stochastic subgradient. It is known that, if the value of the objective function is available, one can obtain, in parallel, several independent approximate solutions in terms of the objective residual expectation. Then, choosing the solution with the minimum function value, one can control the probability of large deviation of the objective residual. On the contrary, in this short paper, we address the situation, when the value of the objective function is unavailable or is too expensive to calculate. Under "‘light-tail"’ assumption for stochastic subgradient and in general case with moderate large deviation probability, we show that parallelization combined with averaging gives bounds for probability of large deviation similar to a serial method. Thus, in these cases, one can benefit from parallel computations and reduce the computational time without loss in the solution quality.     

关于《一类奇异边值问题的正解》的注记

文[4]通过构造反例断言文[1]中定理的必要性证明有误,本文首先指出文[4] 的这个断言不正确,然后对文[4]中定理2.1作了本质性的改进.     

On Connection Between the Nonholonomic Metric on the Heisenberg Group and the Grushin Metric

The purpose of this paper is to compute geodesics on the Grushin plane and examine an assertion on connection between spheres of the Grushin plane and spheres of the Heisenberg group. The assertion turns out to require correction that the spheres of the Heisenberg group are directly obtained by rotation of the Grushin spheres. We find a modified Grushin metric for which the last assertion holds. Also, we prove several theorems about connections between the Grushin plane and Heisenberg group.     

A combinatorial proof of a theorem of Freund

In 1989, Robert W. Freund published an article about generalizations of the Sperner lemma for triangulations of n-dimensional polytopes, when the vertices of the triangulations are labeled with points of Rn. For y∈Rn, the generalizations ensure, under various conditions, that there is at least one simplex containing y in the convex hull of its labels. Moreover, if y is generic, there is generally a parity assertion, which states that there is actually an odd number of such simplices.For one of these generalizations, contrary to the others, neither a combinatorial proof, nor the parity assertion were established. Freund asked whether a corresponding parity assertion could be true and proved combinatorially.The aim of this paper is to give a positive answer, using a technique which can be applied successfully to prove several results of this type in a very simple way. We prove actually a more general version of this theorem. This more general version was published by van der Laan, Talman and Yang in 2001, who proved it in a non-combinatorial way, without the parity assertion.     

Aspects of the planetary Birkhoff normal form

The discovery of the Birkhoff normal form around circular, co-planar motions for the planetary system opened new insights and hopes for the comprehension of the dynamics of this problem. Remarkably, it allowed to give a direct proof (after the proof in [18]) of the celebrated Arnold’s Theorem [5] on the stability of planetary motions. In this paper, after reviewing the story of the proof of this theorem, we focus on technical aspects of this normal form. We develop an asymptotic formula for it that may turn to be useful in applications. Then we provide two simple applications to the three-body problem: we prove that the “density” of the Kolmogorov set of the spatial three-body problem does not depend on eccentricities and the mutual inclination but depends only on the planets’ masses and the separation among semi-axes (going in the direction of an assertion by V. I.Arnold [5]) and, using Nehoro?ev Theory [33], we prove, in the planar case, stability of all planetary actions over exponentiallylong times, provided mean-motion resonances are excluded. We also briefly discuss difficulties for full generalization of the results in the paper.     

What Norm of Assertion?

I argue that the debates over which norm constitutes assertion can be abandoned by challenging the three main motivations for a constitutive norm. The first motivation is the alleged analogy between language and games. The second motivation is the intuition that some assertions are worthy of criticism. The third is the discursive responsibilities incurred by asserting. I demonstrate that none of these offer good reasons to believe in a constitutive norm of assertion, as such a norm is understood in the literature. Others who have made similar arguments conclude that assertion does not exist at all—that there is no such thing as assertion. I disagree: we do not have to relinquish the category of assertion just because it is not normatively constituted. There are alternative ways to understand and individuate assertion that do not rely on a constitutive norm.     

Representation systems and undergraduate proof production: A comment on Weber

Weber (2009) suggested that counterexamples can be generated by a syntactic proof production, apparently contradicting our earlier assertion (Alcock & Inglis, 2008). Here we point out that this ostensible difference is the result of Weber working with theoretical definitions that differ slightly from ours. We defend our approach by arguing that Weber’s relies upon an as yet unspecific metric for gauging the amount of work conducted in each representation system, and that it does not recognize an important asymmetry between the status of representation systems in the context of undergraduate mathematics.     

A toy Neumann analogue of the nodal line conjecture

We introduce an analogue of Payne’s nodal line conjecture, which asserts that the nodal (zero) set of any eigenfunction associated with the second eigenvalue of the Dirichlet Laplacian on a bounded planar domain should reach the boundary of the domain. The assertion here is that any eigenfunction associated with the first nontrivial eigenvalue of the Neumann Laplacian on a domain \(\Omega \) with rotational symmetry of order two (i.e. \(x\in \Omega \) iff \(-x\in \Omega \)) “should normally” be rotationally antisymmetric. We give both positive and negative results which highlight the heuristic similarity of this assertion to the nodal line conjecture, while demonstrating that the extra structure of the problem makes it easier to obtain stronger statements: it is true for all simply connected planar domains, while there is a counterexample domain homeomorphic to a disk with two holes.     

Design and implementation of a massively parallel version of DIRECT

This paper describes several massively parallel implementations for a global search algorithm DIRECT. Two parallel schemes take different approaches to address DIRECT’s design challenges imposed by memory requirements and data dependency. Three design aspects in topology, data structures, and task allocation are compared in detail. The goal is to analytically investigate the strengths and weaknesses of these parallel schemes, identify several key sources of inefficiency, and experimentally evaluate a number of improvements in the latest parallel DIRECT implementation. The performance studies demonstrate improved data structure efficiency and load balancing on a 2200 processor cluster.     

Optimal resource allocation for security in reliability systems

Recent results have used game theory to explore the nature of optimal investments in the security of simple series and parallel systems. However, it is clearly important in practice to extend these simple security models to more complicated system structures with both parallel and series subsystems (and, eventually, to more general networked systems). The purpose of this paper is to begin to address this challenge. While achieving fully general results is likely to be difficult, and may require heuristic approaches, we are able to find closed-form results for systems with moderately general structures, under the assumption that the cost of an attack against any given component increases linearly in the amount of defensive investment in that component. These results have interesting and sometimes counterintuitive implications for the nature of optimal investments in security.