Security Aware Partitioning for Efficient File System Search

Appeared in 26th IEEE Symposium on Massive Storage Systems and Technologies: Research Track (MSST 2010).


Index partitioning techniques - where indexes are broken into multiple distinct sub-indexes - are a proven way to improve metadata search speeds and scalability for large file systems, permitting early triage of the file system. A partitioned metadata index can rule out irrelevant files and quickly focus on files that are more likely to match the search criteria. Also, in a large file system that contains many users, a user’s search should not include confidential files the user doesn’t have permission to view. To meet these two parallel goals, we propose a new partitioning algorithm, Security Aware Partitioning, that integrates security with the partitioning method to enable efficient and secure file system search. In order to evaluate our claim of improved efficiency, we compare the results of Security Aware Partitioning to six other partitioning methods, including implementations of the metadata partitioning algorithms of SmartStore and Spyglass, two recent systems doing partitioned search in similar environments. We propose a general set of criteria for comparing partitioning algorithms, and use them to evaluate the partitioning algorithms. Our results show that Security Aware Partitioning can provide excellent search performance at a low computational cost to build indexes, O(n). Based on metrics such as information gain, we also conclude that expensive clustering algorithms do not offer enough benefit to make them worth the additional cost in time and memory.

Publication date:
May 2010

Aleatha Parker-Wood
Christina Strong
Ethan L. Miller
Darrell D. E. Long

Scalable File System Indexing
HECURA: Scalable Data Management
Ultra-Large Scale Storage
Prediction and Grouping

Available for download:

Full text:
Download as PDF

Bibtex entry

  author       = {Aleatha Parker-Wood and Christina Strong and Ethan L. Miller and
Darrell D. E. Long},
  title        = {Security Aware Partitioning for Efficient File System Search},
  booktitle = {26th IEEE Symposium on Massive Storage Systems and Technologies:
Research Track (MSST 2010)},
  month        = may,
  year         = {2010},
Last modified 26 Oct 2011