Methods, systems, and computer-readable media for anonymizing electronic documents. In accordance with one or more embodiments, structurally-similar electronic documents can be identified among a group of electronic documents (e.g., e-mail messages, documents containing HTML formatting, etc.). A hash function can be specifically tailored to identify the similarly structured documents. The structurally-similar electronic documents can be grouped into a same equivalence class. Masked anonymized document samples can be generated from the structurally-similar electronic documents utilizing the same equivalence class, thereby ensuring that the anonymized document samples when viewed as a part of an audit remain anonymous. An online process is provided to guarantee k-anonymity of the users over the entire lifetime of the auditing process. An auditor's productivity can be measured based on the amount of content revealed to the auditor within the samples he is assigned. The auditor's productivity is maximized while ensuring anonymization over the lifetime of the audit.