Search

This work presents a new perspective on characterizing the similarity between elements of a database or, more generally, nodes of a weighted and undirected graph. It is based on a Markov-chain model of random walk through the database. More precisely, we compute quantities (the average commute time, the pseudoinverse of the Laplacian matrix of the graph, etc.) that provide similarities between any pair of nodes, having the nice property of increasing when the number of paths connecting those elements increases and *en the 'length" of paths decreases. It turns out that the square root of the average commute time is a Euclidean distance and that the pseudoinverse of the Laplacian matrix is a kernel matrix (its elements are inner products closely related to commute times). A principal component analysis (PCA) of the graph is introduced for computing the subspace projection of the node vegors in a manner that preserves as much variance as possible in terms of the Euclidean commute-time distance. This graph PCA provides a nice interpretation to the 'Fiedler vector." widely used for graph partitioning. The model is evaluated on a collaborative recommendation task where suggestions are made about which movies people should watch based upon what they watched in the pest. Experimental results on the MovieLens database show that the Laplacian-based similarities perform well in comparison with other methods. The model, which nicely fits into the so-called "statistical relational learning" framework, could also be used to compute document or word similarities, and, more generally, could be applied to machine-learning and pattern-recognition tasks involving a relational database. [ABSTRACT FROM AUTHOR]

Materialization is a powerful and ubiquitous abstraction pattern for conceptual modeling that relates a class of categories (e.g., models of cars) and a class of more concrete objects (e.g., individual cars). This paper presents materialization as a generic relationship between two classes of objects and describes an abstract implementation of it. The presentation is abstract in that it is not targeted at a specific object system. The target system is supposed to provide: 1) basic object-modeling facilities, supplemented with an explicit metaclass concept and 2) operations for dynamic schema evolution like creation or deletion of a subclass of a given class and modification of the type of an attribute of a class. The presentation is generic in that the semantics of materialization is implemented in a metaclass, which is a template to be instantiated in applications. Application classes are created as instances of the metaclass and they are thereby endowed with structure and behavior consistent with the generic semantics of materialization. [ABSTRACT FROM AUTHOR]