تفاوت coreset و sketch

https://www.cs.utah.edu/~jeffp/papers/chap48-coreset+sketch.pdf

مجموعه‌ی هسته (coreset) یک مجموعه‌ی داده‌ی کاهش داده شده است که می‌توان همان الگوریتم را روی آن اجرا کرد. در اکثر موارد زیرمجموعه‌ای از ورودی است.

مجموعه‌ی هسته‌ی وزن‌دار (weighted coreset) یک مجموعه‌ی هسته است که به نقاط وزن داده شده است که می‌تواند با وزن اولیه آنها متفاوت باشد.

مجموعه‌ی هسته‌ی ضعیف (weak coreset) برای یک مجموعه از پرسه‌ها (query) تعریف می‌شود که یک شرط را تقریباً برای بعضی از پرسه‌ها بهینه می‌کند.

مجموعه‌ی هسته‌ی قوی (strong coreset) برای همه‌ی پرسه‌های یک مجموعه‌ی داده شرط را بهینه می‌کند.

----------

خلاصه (sketch) یک تصویر فشرده شده از همه‌ی داده‌های یک داده‌ساختار است که می‌تواند به سادگی به روز رسانی شود و داده‌های آن تغییر کند و به آن داده‌ی جدید اضافه شود. همچنین پرسه‌های خاصی برای آن تعریف می‌شود که ویژگی‌هایی از کل داده‌ها را تقریب می‌زند.

خلاصه خطی (linear sketch) خلاصه‌ای است که تصویر داده‌ها تابعی خطی از هر داده است، در نتیجه اضافه، حذف و تغییر را ساده‌تر می‌کند.

--------

شباهت هر دو در این است که اندازه‌ی آنها تابعی از ضریب تقریب است و نه اندازه‌ی ورودی. هرچند در برخی موارد وابستگی لگاریتمی به اندازه ورودی دارد.