Abstract
Collaborative outlier detection allows multiple parties to improve detection performance by learning from collective data without compromising privacy. We present LSH iTables, a hashing-based ensemble method that leverages the mergeability of Locality-Sensitive Hashing (LSH). By sharing privacy-preserving histograms (iTables) instead of raw data, participants can construct a global model efficiently. Our evaluation across 11 real-world datasets demonstrates that LSH iTables achieves state-of-the-art accuracy, provides massive speedups over proximity-based methods, and maintains robustness under Differential Privacy constraints.
Introduction
Outlier detection is a critical task in domains such as healthcare and finance. However, the most informative data is often distributed across different organizations. Collaborative detection aims to pool this knowledge while addressing three primary challenges: privacy (raw records cannot be shared), communication efficiency (minimizing model size), and mergeability (the ability to combine local models into a global one without the original data).
Existing methods like Isolation Forests (iForest) are popular but lack a mathematically sound way to merge separate models. LSH iTables addresses these gaps by using a hashing-based approach that is inherently mergeable and computationally lightweight.
Methodology
The core of LSH iTables is Random Feature LSH (RF-LSH). Each participant uses an identical set of random hash functions to map their local data points into discrete "buckets."
The iTable Mechanism
Participants generate a histogram, or "iTable," by counting the number of points falling into each bucket. Because all parties use the same hash functions, these iTables are additive. A global model is created by simply summing the counts of corresponding buckets from all participants.
Outlier Scoring and Privacy
A point's outlier score is inversely proportional to the total count in its corresponding bucket across the global histogram. To ensure privacy, the Laplacian mechanism is used to add noise to bucket counts before sharing, satisfying Differential Privacy (DP) requirements. A log2 scoring system is employed to minimize the impact of this noise, ensuring stable rankings even with small privacy budgets.
Experimental Setup
The performance of LSH iTables was evaluated against seven ensemble methods using 11 diverse datasets from the ODDS and UCI repositories. These datasets span medical, image recognition, and network security domains.
Results and Discussion
Accuracy and Efficiency
LSH iTables achieved the highest average AUC score (93.5) among the tested methods, including iForest and LODA. The efficiency gains were particularly notable on large datasets. For instance, on the "Cover" dataset (~300k instances), LSH iTables completed in 29 seconds, whereas the proximity-based EnsKNNW required 9 hours. This speed is attributed to the $O(1)$ hash evaluation time of RF-LSH.
Theoretical Insights
A key finding is the theoretical link between LSH and iForest. The authors demonstrate that iForest's splitting mechanism can be viewed as a specific type of weighted LSH. This explains the high accuracy of LSH iTables while highlighting its superior suitability for decentralized environments.
Privacy Performance
In decentralized settings, LSH iTables outperformed other hashing methods like RS-H under strict DP constraints. The log-scaling approach proved effective in maintaining high AUC even when significant noise was added to the bucket counts.
Conclusion
LSH iTables provides a scalable, private, and accurate framework for collaborative outlier detection. While it requires coordination for shared hash functions, its mergeability and efficiency make it a compelling choice for large-scale, privacy-sensitive applications. Future work may explore different LSH families to handle diverse data types and similarity measures.
Summary updated