Dimensionality reduction techniques map values from a high dimensional space to one with a lower dimension. The result is a space which requires less physical memory and has a faster distance calculation. These techniques are widely used where required properties of the reduced-dimension space give an acceptable accuracy with respect to the original space. Many such transforms have been described. They have been classified in two main groups: linear and topological . Linear methods such as Principal Component Analysis (PCA) and Random Projection (RP) define matrix-based transforms into a lower dimension of Euclidean space. Topological methods such as Multidimensional Scaling (MDS) attempt to preserve higher-level aspects such as the nearest-neighbour relation, and some may be applied to non-Euclidean spaces. Here, we introduce nSimplex Zen , a novel topological method of reducing dimensionality. Like MDS, it relies only upon pairwise distances measured in the original space. The use of distances, rather than coordinates, allows the technique to be applied to both Euclidean and other Hilbert spaces, including those governed by Cosine, Jensen–Shannon and Quadratic Form distances. We show that in almost all cases, due to geometric properties of high-dimensional spaces, our new technique gives better properties than others, especially with reduction to very low dimensions.

Approximate Nearest Neighbor (ANN) search is a prevalent paradigm for searching intrinsically high dimensional objects in large-scale data sets. Recently, the permutation-based approach for ANN has attracted a lot of interest due to its versatility in being used in the more general class of metric spaces. In this approach, the entire database is ranked by a permutation distance to the query. Typically, permutations allow the efficient selection of a candidate set of results, but typically to achieve high recall or precision this set has to be reviewed using the original metric and data. This can lead to a sizeable percentage of the database being recalled, along with many expensive distance calculations. To reduce the number of metric computations and the number of database elements accessed, we propose here a re-ranking based on a local embedding using the nSimplex projection. The nSimplex projection produces Euclidean vectors from objects in metric spaces which possess the n-point property. The mapping is obtained from the distances to a set of reference objects, and the original metric can be lower bounded and upper bounded by the Euclidean distance of objects sharing the same set of references. Our approach is particularly advantageous for extensive databases or expensive metric function. We reuse the distances computed in the permutations in the first stage, and hence the memory footprint of the index is not increased. An extensive experimental evaluation of our approach is presented, demonstrating excellent results even on a set of hundreds of millions of objects.

Most research into similarity search in metric spaces relies on the triangle inequality property. This property allows the space to be arranged according to relative distances to avoid searching some subspaces. We show that many common metric spaces, notably including those using Euclidean and Jensen-Shannon distances, also have a stronger property, sometimes called the four-point property: In essence, these spaces allow an isometric embedding of any four points in three-dimensional Euclidean space, as well as any three points in two-dimensional Euclidean space. In fact, we show that any space that is isometrically embeddable in Hilbert space has the stronger property. This property gives stronger geometric guarantees, and one in particular, which we name the Hilbert Exclusion property, allows any indexing mechanism which uses hyperplane partitioning to perform better. One outcome of this observation is that a number of state-of-the-art indexing mechanisms over high-dimensional spaces can be easily refined to give a significant increase in performance; furthermore, the improvement given is greater in higher dimensions. This therefore leads to a significant improvement in the cost of metric search in these spaces.

The similarity of objects is one of the most fundamental concepts in any collection of complex information; similarity, along with techniques for storing and indexing sets of values based on it, is a concept of ever increasing importance as inherently unordered data sets become ever more common. Examples of such datasets include collections of images, multimedia, and semi-structured data.There are however two, largely separate, classes of related research. On the one hand, techniques such as clustering and similarity search give general treatments over sets of data. Results are domain-independent, typically relying only on the existence of an anonymous distance metric over the set in question. On the other hand, results in the domain of similarity measurement are often limited to the context of pairwise comparison over individual objects, and are not typically set in a wider context. Published algorithms are scattered over various demand-led subject areas, including for example bioinformatics, library sciences, and crime detection. Few, if any, of the published algorithms have the distance metric properties.We have identified a distance metric, Ensemble Distance, which we believe can help to bridge this gap. Ensemble Distance is a non-Euclidean distance metric which we believe can be used in the treatment of many classes of structured data. For any complex type where a useful characterisation exists in the form of an ensemble, we can produce a distance metric for that type. This will in turn allow use of the complex type within off-the-shelf clustering and similarity search algorithms; this would be a major result in the management of complex data sets.

We demonstrate the use of a hyper-programming system in building persistent applications. This allows program representations to contain type-safe links to persistent objects embedded directly within the source code. The benefits include improved efficiency and potential for static program checking, reduced programming effort and the ability to display meaningful source level representations for first class procedure values. Hyper-programming represents a completely new style of programming which is only possible in a persistent programming system.

Persistent programming systems are designed to provide technology for the construction and maintenance of large, long-lived object-based application systems. Many successful prototypes have been constructed and a large body of application building experience is emerging. Three common attributes of persistent systems are persistent linkage, strong typing, and the referential integrity of data. Persistent linkage allows persistent objects to be included in the binding process. Strong typing guarantees that objects are only manipulated in a manner consistent with their type system descriptions. Referential integrity ensures that once a link (reference) to an object is established, its identity is unique and it persists over time. As a consequence no object can be deleted while another refers to it. Here we examine some of the advantages of providing software engineering environments within a persistent object system with strong typing and referential integrity. It is shown how the integration of system specifications, programs, configuration management tools and documentation all within a single persistent environment leads to powerful new techniques. This new power is achieved by sharing structured persistent data across the hitherto enclosing boundaries of system components.

Polymorphicabstraction provides the ability to write programs that are independent of the form of the data over which they operate.There are a number of different categories of polymorphic expression-ad hoc and umversal, which includes parametric and inclusion-all of which have many advantages in terms of code reuse and software economics.It has proved difficult to provide efficient implementations of polymorphism.Here, we address this problem and describe a new technique that can implement all forms of polymorphism, use a conventional machine architecture, and support nonuniform data representations.Furthermore, the method ensures that any extra cost of implementation applies to polymorphic forms only, and allows such polymorphic forms to persist over program invocations.

In this paper we are concerned with addressing techniques for statically typed languages with multiple inheritance. The addressing techniques are responsible for the efficient implementation of record field selection. In object-oriented languages, this record selection is equivalent to the access of methods. Thus, the efficiency of these techniques greatly affects the overall performance of an object-oriented language. We will demonstrate that addresses, in such systems, cannot always be calculated statically and show how symbol tables have been used as address maps at run time. The essence of the paper is a new addressing technique that can statically calculate either the address of a field or the address of the address of the field. This technique is powerful enough to support an efficient implementation of multiple inheritance with implicit subtyping as described by Cardelli.