The time required to retrieve a query’s nearest neighbor may quickly become a CBR system’s bottleneck when its case base contains a large volume of cases. Approximate retrieval techniques that build and employ complex index data structures can mitigate this issue by providing an acceptable tradeoff between time complexity and retrieval accuracy. In this paper, we propose a specialized multigraph-based index structure composed of multiple nested sub-case bases with individually labeled edge sets. We develop tailored algorithms for both constructing the index and utilizing it in a more efficient retrieval process, and we also evaluate our approach empirically using established benchmark datasets.