PAM की तरह एक क्लासिक k-medoids विभाजन एल्गोरिथ्म छोटे डेटा सेट के लिए कुशलता से काम करता है लेकिन विशाल डेटा सेट के लिए अच्छी तरह से स्केल नहीं करता है। यह उच्च डेटा सेट से निपट सकता है, एक नमूना-आधारित विधि, जिसे क्लारा (क्लस्टरिंग लार्ज एप्लिकेशन) के रूप में जाना जाता है, का उपयोग किया जा सकता है।
क्लारा के पीछे का दृष्टिकोण इस प्रकार है:यदि नमूना काफी यादृच्छिक तरीके से चुना जाता है, तो उसे मूल डेटा सेट को बारीकी से परिभाषित करना चाहिए। चुने गए प्रतिनिधि ऑब्जेक्ट (मेडोइड्स) उन लोगों के समान होंगे जिन्हें पूरे डेटा सेट से चुना गया होगा। CLARA डेटा सेट के कई नमूने खींचता है, प्रत्येक नमूने पर PAM लागू करता है, और आउटपुट के रूप में अपनी सर्वश्रेष्ठ क्लस्टरिंग देता है।
क्लारा का प्रदर्शन नमूना आकार पर आधारित है। यह देखा गया है कि PAM किसी दिए गए डेटा सेट के बीच सर्वश्रेष्ठ k मेडोइड्स की खोज करता है, जबकि CLARA डेटा सेट के चयनित नमूनों के बीच सर्वश्रेष्ठ k मेडोइड्स की खोज करता है। एक k-medoids प्रकार एल्गोरिथ्म जिसे CLARANS के रूप में जाना जाता है (क्लस्टरिंग लार्ज एप्लिकेशन रैंडमाइज्ड सर्च पर निर्भर करता है) प्रस्तावित किया गया था। यह नमूनाकरण विधियों को PAM से जोड़ सकता है। जहां खोज के हर चरण में क्लारा का एक निश्चित नमूना होता है, वहीं CLARANS खोज के हर चरण में कुछ यादृच्छिकता के साथ एक नमूना तैयार करता है।
क्लस्टरिंग प्रक्रिया को एक ग्राफ के माध्यम से एक खोज के रूप में देखा जा सकता है, जहां प्रत्येक नोड एक संभावित समाधान (के मेडोइड्स का एक सेट) है। दो नोड पड़ोसी हैं (विशेषकर, ग्राफ में एक चाप से जुड़े हुए) यदि उनके सेट केवल एक वस्तु से भिन्न होते हैं। प्रत्येक नोड को एक लागत सौंपी जा सकती है जो प्रत्येक वस्तु और उसके क्लस्टर के मेडोइड के बीच कुल असमानता द्वारा दर्शायी जाती है।
प्रत्येक चरण में, PAM न्यूनतम लागत समाधान की खोज में नवीनतम नोड के सभी पड़ोसियों को निर्धारित करता है। नवीनतम नोड को फिर पड़ोसी द्वारा लागत में सबसे बड़े वंश के साथ बदल दिया जाता है। क्योंकि CLARA पूरे डेटा सेट के एक नमूने पर काम करता है, यह कम पड़ोसियों को निर्धारित करता है और खोज को उन सबग्राफ तक सीमित रखता है जो प्रारंभिक ग्राफ़ से छोटे होते हैं।
CLARANS को प्रयोगात्मक रूप से PAM और CLARA दोनों की तुलना में अधिक कुशल दिखाया गया है। इसका उपयोग किसी ऑब्जेक्ट की एक संपत्ति के सिल्हूट गुणांक का उपयोग करके क्लस्टर की सबसे "प्राकृतिक" संख्या को खोजने के लिए किया जा सकता है जो परिभाषित करता है कि ऑब्जेक्ट वास्तव में क्लस्टर पर कितना लागू होता है। CLARANS आउटलेर्स की खोज की भी अनुमति देते हैं।
CLARANS की कम्प्यूटेशनल जटिलता O(n 2 .) है ) जहां n वस्तुओं की संख्या है। इसके अलावा, इसकी क्लस्टरिंग गुणवत्ता इस्तेमाल की गई नमूना पद्धति पर आधारित है। डिस्क पर रहने वाले डेटा ऑब्जेक्ट्स के साथ प्रबंधन करने की CLARANS की क्षमता को R*-ट्री सहित स्थानिक डेटा संरचनाओं का पता लगाने वाली विधियों पर ध्यान केंद्रित करके और भी बेहतर बनाया जा सकता है।