The Protein Data Bank (PDB), which is the single worldwide repository for 3-D macromolecular structure data, contains tens of thousands of protein structures. Computationally efficient methods are required for the analysis of data at this scale. In this dissertation, we present methods for protein structure analysis that can scale well with the amount of protein structure data available. The presented methods are organized in three parts: (1) visualization and surface modeling, (2) structure comparison and similarity search, and (3) automated protein structure classification. The first part deals with computation of different structural representations of protein molecules. The second part considers the problem of similarity searches in large protein databases. The third part presents an ensemble classifier framework for automated classification of protein structures. The reader is expected to have a computer science background and an interest in bioinformatics.