Similarity search in high-dimensional vector spaces has been the subject of substantial research, motivated in part by the need to provide query support for images and other complex data types. The paper VLDB 1998 paper "Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces" analyses why this search problem can be so tricky, and shows with intuitive yet formal proofs that nearest-neighbour search is fundamentally linear beyond a certain dimensionality. Consequently, the paper proposes a new, linear search structure (the VA-File) which focuses on accelerating the indispensable sequential scan with approximations and computational schemes to reduce both CPU and IO efforts. Experiments with both synthetic and image data showed -- surprisingly, at the time -- that such schemes outperform hierarchical methods in all cases where the dimensionality is greater than five. In this paper, we review that work and identify both what we got right in the paper and its impact, and also (with the benefit of hindsight) those elements of the work for which we were off the mark. The lessons learned are relevant not just to the narrow area of similarity search, but also more broadly across the fields of databases and computing.

Over the past decade, the World-Wide-Web has become the preferred vehicle for information dissemination on a global scale. However, no guarantees as to the consistency, or correctness, of the content being provided are made. In this paper, a novel vision of a Consistent Web is proposed. Unlike in the current system, time will have a direct influence on whether requests for specific content should be satisfied. Firstly, the motivation for the work and the limitations of current consistency management techniques are discussed. The concept of a Consistent Web is then presented, and by way of several examples, an illustration of the type of functionality it offers is provided. Finally, an outline of the research strategy to be employed is given.

In recent years, databases have started to be used as intelligent repositories for a variety of semantically-richer systems. A consequence of such architectures is that transaction scheduling takes place throughout composite systems consisting of layered subsystems. Such transaction architectures have been studied extensively. Existing theory, however, limits the degree of parallelism, and makes a number of simplifying assumptions which cannot be taken for granted in practice. This paper proposes a new model and correctness criterion, stack conflict consistency, for composite transactional systems. The main contribution of the new model is to establish the correctness conditions under which higher degrees of parallelism can be achieved between operations of the same transaction, as well as between conflicting operations of different transactions, in a uniform way. This possibility, although hinted at previously, has not yet been exploited in practical composite systems. Hence, we hope...

Database systems must become more open to retain their relevance as a technology of choice and necessity. Openness implies not only databases exporting their data, but also exporting their services. This is as true in classical application areas as in non-classical (GIS, multimedia, design, etc).This paper addresses the problem of exporting storage-management services of indexing, replication and basic query processing. We describe an abstract-object storage model which provides the basic mechanism, 'likeness', through which these services are applied uniformly to internally-stored, internally-defined data, and to externally-stored, externally-defined data. Managing external data requires the coupling of external operations to the database system. We discuss the interfaces and protocols required of these to achieve correct resource management and admit efficient realisation. Throughout, we demonstrate our solutions in the area of semi-structured file management; in our case, geospatial metadata files.

This paper presents type classes, a new approach to ad-hoc polymorphism. Type classes permit overloading of arithmetic operators such as multiplication, and generalise the “eqtype variables” of Standard ML. Type classes extend the Hindley/Milner polymorphic type system, and provide a new approach to issues that arise in object-oriented programming, bounded type quantification, and abstract data types. This paper provides an informal introduction to type classes, and defines them formally by means of type inference rules.