Methods and apparatus are described for matching a set input fingerprint blocks, each fingerprint block representing at least a part of an information signal, with fingerprints stored in a database that identify respective information signals. The method includes selecting a first fingerprint block of the set of input fingerprint blocks (10), and finding at least one fingerprint block in the database that matches the selected fingerprint block (20, 40). A further fingerprint block is then selected from the set of input blocks (60), at a predetermined position from the first selected fingerprint block. A corresponding fingerprint block is then located in the database at the same predetermined position relative to the found fingerprint block (70), and it is determined if the located fingerprint block matches the selected further fingerprint block (80).