Force-Based Clustering for Transitive Identity Mapping

In most information retrieval systems, software processes reason about passive data. Our approach instantiates each piece of information as an agent that actively seeks to organize itself with respect to other agents (including queries). Imitating the movement of bodies under physical forces, we describe a distributed algorithm ("force-based clustering," or FBC) for dynamically clustering and querying large, heterogeneous, dynamic collections of entities. The algorithm moves records in a virtual space in a way that estimates the transitive closure of the pairwise comparisons. We demonstrate FBC on a large, heterogeneous collection of records, each representing a person. We have some information about a person of interest, but no record in the collection directly matches this information. Application of FBC identifies a small subset of records that are good candidates for describing the person of interest, for further manual investigation and verification.