• designed for pmr queries   (conjunction of equalities)
• does not try to achieve better than O(n) performance
• attempts to provide an "efficient" linear scan

Each tuple is associated with a signature

• a compact (lossy) descriptor for the tuple
• formed by combining information from multiple attributes
• stored in a signature file, parallel to data file