المسافة إلى $k$th أقرب جار بكفاءة لـ $k$ التعسفي

Question

مشكلة. منح $X$ مساحة مترية محدودة من الكاردينالية $ن$, ، قم بإنشاء بنية بيانات في زمن دون التربيعي مثل الاستعلام distance to the kth nearest neighbor of x يمكن حلها في الوقت الخطي (مستقل عن $ك$) للتعسف $k \leq n$ و $x \في X$.

ما حاولت. أنا على علم بوجود أشجار kdtrees وأشجار الكرة وأشجار الغطاء.في ظل بعض الافتراضات (التي أنا على استعداد للقيام بها)، أعلم أن هذه الهياكل يمكنها حل الاستعلام distance to the nearest neighbor of x في الوقت الخطي (في كثير من الأحيان $O(\log(n))$)، ولكنني لم أتمكن من العثور على نتائج مماثلة لـ $ك$عشر أقرب جار التعسفي $ك$.

يبدو أن المرء مهتم في كثير من الأحيان $ك$ القيم التي هي صغيرة مقارنة ب $ن$, ، وأنه في تلك الحالات، يمكن تكييف الخوارزميات المذكورة في الفقرة السابقة على حساب ثابت مضاعف من ترتيب $ك$.مشكلتي هي أنني مهتم $ك$ القيم التي يحتمل أن تكون من ترتيب $ن$.

Answer 1

بالنسبة لمقياس عام، لا يمكنك ذلك.على سبيل المثال، يمكن للمرء أن يثبت أن الإجابة تستغرق وقتًا تربيعيًا على الأقل $\ثيتا(ن)$ الاستفسارات، في أسوأ الأحوال.

على سبيل المثال، لنفترض أن لدينا $ن/2$ نقاط الاستعلام التي تكون كلها بعيدة جدًا عن بعضها البعض، و $ن/2$ النقاط المستهدفة.سوف نطلب ال $ن/4$-الجار الأقرب لكل نقطة استعلام.ثم كل $د(ف،ر)$ يمكن ضبطها على أي مسافة في $[1/2,1]$ لكل من $ن^2/4$ أزواج من نقطة الاستعلام $س$ ونقطة الهدف $t$, ، ويمكن اختيار كل منها بشكل مستقل، وسيكون لديك مقياس صالح.وبالتالي يمكنك أن تتخيل المسافة التي تم تحديدها بواسطة أ $ن/2 \مرات ن/2$ مصفوفة المسافات $د(ف،ر)$.في $س(ن^2)$ الوقت، يمكنك أن تقرأ فقط $س(ن^2)$ من الإدخالات في تلك المصفوفة، والتي لا تكفي للإجابة على كافة الاستعلامات.يمكنك إثبات ذلك بحجة خصومية:النظر في أي $س$ حيث تمت قراءة الخوارزمية $د(ف،ر)$ لأقل من $ن/4$ قيم مختلفة من $t$;ثم مهما كانت مخرجات الخوارزمية كـ $ن/4$-ال أقرب جار ل $س$, يمكننا ترتيب المسافات الأخرى غير المقروءة بحيث يكون إخراج الخوارزمية غير صحيح.