Azərbaycanca
Беларускі
Dansk
Deutsch
Española
Français
Indonesia
Italiana
日本語
Қазақ
Lietuvos
Nederlands
Português
Русский
සිංහල
แบบไทย
Türkçe
Українська
中國人
United State
Afrikaans
การค้นหาเพื่อนบ้านที่ใกล้ที่สุด (อังกฤษ: nearest neighbor search) เป็นที่รู้จักในนามอื่น ๆ อาทิ การค้นหาความใกล้ชิด การค้นหาความคล้ายคลึง หรือการค้นหาจุดที่ใกล้ที่สุด เอ็นเอ็นเอส คือ เทคนิคที่ใช้ในการแก้ปัญหาที่ใช้สำหรับหาจุดที่ใกล้ที่สุดใน ยกตัวอย่างจากโจทย์ต่อไปนี้ เมื่อให้เซต S คือเซตของจุดในปริภูมิเมทริกซ์ M และ จุดที่กำหนด q ∈ M ต้องการหาจุดที่ใกล้ที่สุดของ S กับ q ในหลายกรณี M นั้นจะถูกแทนค่าเป็นมิติในปริภูมิของยูคลิด และระยะทางนั้นสามารถวัดได้จากระยะทางยูคลิด หรือ ระยะทางแมนฮัตตัน ในหนังสือของ โดนัลด์ คนูธ เล่มที่สามที่มีชื่อว่า เรียกโจทย์ปัญหาแบบนี้ว่า ปัญหาไปรษณีย์ โดยอ้างอิงถึงระบบการแนะนำผู้อยู่อาศัยเกี่ยวกับไปรษณีย์ที่ใกล้ที่สุด
การประยุกต์
เอ็นเอ็นเอสได้ถูกนำไปใช้ในการแก้ปัญหาและตอบโจทย์ในหลายๆด้าน อาทิเช่น
- การจำแนกรูปแบบ โดยเน้นไปที่ Optical Character recognition
- การแบ่งให้เป็นหมวดหมู่ของตัวเลขสถิติ ยกตัวอย่างเช่น ขั้นตอนวิธีการหาค่า k ที่ใกล้เคียงที่สุด
- การมองเห็นของเครื่องคอมพิวเตอร์
- ฐานข้อมูล อาทิ การจัดข้อมูลโดยการอ้างอิงและค้นหาจากรูปปภาพ
- ทฏษฎีการเขียดโค้ด
- การย่อขนาดข้อมูล
- ระบบแนะนำ
- การตลาดทางอินเทอร์เน็ต
- การจัดเรียงกันของดีเอ็นเอ
- ระบบสะกดคำ
- การจับทุจริตในการเขียนเรียงความ
- สมการที่ใช้สำหรับการค้นหาพื้นที่สัมผัส ในเอฟอีเอ (Finite Element Analysis)
- การเทียบเคียงผลการแข่งขันเพื่อที่ใช้สำหรับคาดคะเนความสำเร็จในด้านกีฬาของนักกีฬา
- การวิเคาระห์ข้อมูลที่ถูกจัดเป็นกลุ่มไว้แล้ว
ขั้นตอนวิธี
มีหลายวิธีการที่สามารนำไปใช้ในการค้นหาคำตอบสำหรับโจทย์เอ็นเอ็นเอส ได้ถูกคิดต้นขึ้น ค่าประสิทธิภาพของแต่ละวิธีนั้นสามารถหาได้จากเวลาและความซับซ้อนของโครงสร้างข้อมูลที่ถูกบันทึกไว้ การสังเกตอย่างไม่เป็นทางการ หรืออีกชื่อหนึ่งว่าคำสาปของมิติ() กล่าวว่าไม่มีผลลัพธ์ของจุดประสงค์ได้อย่างชัดเจนสำหรับเอ็นเอ็นเอสในปริภูมิของยูคลิดที่มีมิติสูงๆ โดยการใช้การแก้สมการทีมีมากกว่าหนึ่งตัวแปรและ เวลาค้นหาแบบพหุนามล็อคการิทึม
การค้นหาแบบเส้นตรง
การหาวิธีแก้โจทย์เอ็นเอ็นเอสที่ง่ายที่สุดสามารถกระทำโดยเริ่มจากการหาค่าระยะทางจากจุดที่กำหนด ถึงจุดอื่นๆในฐานข้อมูล และเก็บข้อมูลเส้นทางที่ดีที่สุดอยู่เสมอ การหาค่าแบบนี้บางครั้งถูกตราหาเป็นวิธีที่พื้นฐานเกินไปและใช้เวลาทำงานเท่ากับ O( Nd ) โดย N คือ จำนวนสมาชิกของ S และ d คือมิติของ M วิธีการค้นหาแบบเส้นตรงนั้นไม่จำเป็นที่จะต้องรักษาโครงสร้างของข้อมูล เพราะฉะนั้นวิธีการค้นหาแบบเส้นตรงนั้นไม่ได้มีความสัมพันธ์กับความซับซ้อนของฐานข้อมูล เป็นที่น่าประหลาดใจว่า วิธีการค้นหาแบบเส้นตรงนั้นมีประสิทธิภาพมากกว่า อีกสองวิธีที่จะกล่าวถึงซึ่งก็คือ การแบ่งปริภูมิบนปริภูมิที่มีมิติสูงกว่า
การแบ่งส่วนปริภูมิ
ตั้งแต่ปี 1970 วิธีการขยายและจำกัดเขต () ได้ถูกมาใช้ในการแก้ปัญหา ในกรณีของปริภูมิของยูคลิด วิธีของการแบ่งปริภูมิ () นั้นรู้จักในนามว่าวิธีตำแหน่งเชิงพื้นที่ () หรือการเข้าถึงชิงพื้นที่ ในหลายวิธีของการแบ่งปริภูมิ ได้ถูกพัฒนาขึ้นเพื่อใช้ในการแก้โจทย์เอ็นเอ็นเอส บางทีวิธีที่ง่ายและมีความซับซ้อนน้อยที่สุดคือ วิธีนี้คือการแบ่งแยกข้อมูลออกเป็นสองฝั่ง โดยฝั่งที่ถูกแบ่งนั้นจะมีจุดครึ่งหนึ่งจากทั้งหมดของตอนแรกที่ยังไม่ถูกแบ่ง จะแก้ปัญหาผ่านทางการแวะผ่านต้นไม้เริ่มตั้งแต่รากถึงใบโดยการแก้จุดที่กำหนด ในทุกๆที่ที่ถูกแบ่ง วิธีการนี้ขึ้นอยู่กับระยะทางที่กล่าวถึงในคำถาม กิ่งเพื่อนบ้านที่มีตัวที่กำลังค้นหาอยู่นั้นอาจจะต้องถูกนำมาวิเคาระห์ด้วย โดยช้เวลาในการหาคำตอบเท่ากับ O(log N) ในกรณีที่เลวร้ายที่สุด คือมีจุดกระจายกันอย่างไม่เป็นระเบียบ อีกทางเลือกหนึ่งคือ การใช้โครงสร้างข้อมูลแบบ ที่ได้ถูกออกแบบมาเพื่อรองรับการค้นหาจุดที่ใกล้ที่สุด แบบพลวัตสืบเนื่องจากว่ามันมีวิธีที่มีประสิทธิภาพในการเพิ่มและลบของข้อมูล ในกรณีทั่วไปของปริภูมิเมทริกซ์ วิธีการขยายและจำกัดเขต() รู้จักกันภายใต้ชื่อว่า ต้นไม้เมทริกซ์ ยกตัวอย่างจาก และ โดยการใช้กลุ่มตัวเลขจากปริภูมิสามมิติและใส่เข้าไปในต้นไม้บีเอสพี และให้จุดที่กำหนดที่มาจากปริภูมิเดียวกัน การหาผลลัพธ์ที่เป็นไปได้สำหรับปัญหาการหาจุดที่ใกล้เคียงที่สุดระหว่างกลุ่มของจุดและ ดังคำอธิบายของการแก้สมการต่อไปนี้ ในทางปฏิบัติ เรานั้นสนใจแค่การหาค่าสับเซตอันใดก็ได้ของกลุ่มของจุดทั้งหมดที่ปรากฏให้เห็นในระยะทางที่สั้นที่สุดจากจุดที่กำหนดไว้ก่อนหน้า จุดประสงค์ของแต่ละกิ่งของต้นไม้นี้คือการเดาว่าจุดที่ใกล้ที่สุดจากในกลุ่มที่ตั้งอยู่ในครึ่งหนึ่งของปริภูมิที่ประกอบไปด้วยจุดที่ต้องการรู้ วิธีนี้อาจไม่ได้ผลเสมอไปแต่มันเป็นการเริ่มต้นในการแก้ไขปัญหาของตัวเองที่ดี หลังจากที่ใช้วิธีนี้วนซ้ำครบทุกกิ่งแล้ว เราจะสามารถเปรียบเทียบว่าระยะทางที่ได้จากผลลัพธ์กับระยะทางที่สั้นที่สุดจากจุดที่ต้องการถึงระนาบที่แบ่งไว้ ว่ากิ่งไหนนั้นใช้ระยะทางที่สั้นที่สุด โดยระยะทางที่สั้นที่สุดอาจจะเกิดขึ้นอีกจากฐานข้อมูลอีกอันที่ถูกแบ่งก็ได้เพราะฉะนั้นบางทีคุณอาจจะต้องพิจารณาทั้งสองฝั่งที่ถูกแบ่ง แต่ถึงอย่างไรก็ตามถ้าระยะทางไปกลับจากจุดที่ต้องการกับระนาบที่แบ่งไว้ นั้นยาวกว่าระยะทางที่ถูกค้นหาก่อนหน้านี้ เราก็ไม่จำเป็นที่จะต้องวิเคราะห์อีกฝั่งนึงแล้ว วิธีนี้ใช้เวลาสั้นกว่าวิธีการค้นหาแบบเส้นตรงเพราะว่าระยะทางระหว่าง จุดที่ต้องการทราบกับกลุ่มของจุดที่ใกล้ที่สุดนั้นเกือบจะเทียบเท่ากับศูนย์ วิธีนี้จะใช้ได้ผลก็ต่อเมื่อมีการค้นหาโดยใช้จุดที่ต้องการทราบ
Locality sensitive hashing
แอลเอสเอช () คือขั้นตอนที่ใช้สำหรับจับกลุ่มจุดต่างๆที่อยู่ในที่ว่างให้อยู่เป็นที่ โดยอ้างอิงจากระยะทางจากการกระทำการเมทริกซ์บนจุดเหล่านั้น จุดที่ใกล้กันในเมทริกซ์ ที่ถูกเลือกนั้นจะถูกจัดเข้าไปอยู่ในที่ๆเดียวกันโดยที่มีสถิติความน่าจะเป็นที่สูงกว่า
การค้นหาเพื่อนบ้านที่ใกล้ที่สุดในปริภูมิที่มีมิติน้อย
รูปแบบโดยกว้างของต้นไม้นั้นอ้างอิงมาจากการเพิ่มค่าขึ้นเป็นสองเท่าของฐานข้อมูลที่คงที่ เส้นรอบนอก ในเวลาของการค้นหานั้นเท่ากับ O(c12 log n) โดย c นั้นเท่ากับการขยายตัวที่คงที่ของข้อมูลนั้น
Vector Approximation Files
ในโลกหลายๆมิติ รายละเอียดภายในของต้นไม้นั้นไม่สามารถนำมาใช้ประโยชน์ได้เพราะว่าค่าเปอร์เซ็นต์ของจุดนั้นจะต้องถูกนำมาตรวจสอบด้วย ในการเพิ่มประสิทธิภาพให้กับวิธีค้นหาเป็นเส้นตรง รูปแบบการบีบอัดของการเก็บเวกเตอร์ในแรม นั้นได้ถูกใช้ในการคัดจำแนกข้อมูลในการประเมินในครั้งแรก ตัวเลือกสุดท้ายนั้นสามารถหาได้จากในขั้นตอนที่สองโดยการใช้การปลดปล่อยข้อมูลจากดิสก์เพื่อการคำนวณระยะทาง Compression/Clustering Based Search การจำลองการเข้าถึงไฟล์นั้นเป็นวิธีเฉพาะที่ใช้สำหรับการข้นหาข้อมูลแบบย่อ โดยที่องค์ประกอบของข้อมูลที่ถูกย่อนั้นได้ถูกย่อจากเวอร์ชันเต็มโดยไร้ข้อบังคับใช้เทคนิคการย่อและบีบอัดในโลกหลายๆมิตินั้นเรียกว่า Vector Quantization (VQ)ที่สร้างโดยการจัดกลุ่ม ฐานข้อมูลได้ถูกหั่นและย่อลงมาจนเหลือแค่ชิ้นข้อมูลที่น่าเชื่อถือที่สุด ประโยชน์ของเทคนิคนี้นั้นมากกว่าVA-File, tree-based indexes และ sequential scan
สิ่งที่แปรผัน
มีค่าแปรผันมากมายในโจทย์เอ็นเอ็นเอสแต่ค่าแปรผันสองตัวที่พบเจอบ่อยที่สุดคือ การค้นหาเพื่อนบ้านที่ใกล้ที่สุดเป็นระยะทาง k () และการประมาณหาเพื่อนบ้านที่ใกล้ที่สุด()
k เพื่อนบ้านที่ใกล้ที่สุด (k-nearest neighbor)
การค้นหาเพื่อนบ้านที่ใกล้ที่สุด k ตัว() แสดงค่าเพื่อนบ้านที่ใกล้กับจุดที่ต้องการทราบที่สุด k ตัว เทคนิคนี้ใช้อย่างเพร่หลายใจการวิเคราะห์คาดคะเนเพื่อที่จะประมาณหรือจำแนกจุดโดยอ้างอิงจากข้อสรุปของจุดอื่นในละแวกใกล้เคียง กราฟของเพื่อนบ้านที่ใกล้ที่สุด k เพื่อนบ้าน คือกราฟที่ทุกๆจุดได้ถูกเชื่อมต่อเข้ากับ k ที่ใกล้สุดในระแวกเดียวกัน
การคาดคะเนหรือประมาณจุดที่ใกล้ที่สุด (Approximate nearest neighbor)
ในการประยุกต์ใช้ในบางอย่าง มันอาจเป็นที่ยอบรับสำหรับการค้นเจอการคาดเดาที่ดีของจุดที่ใกล้ที่สุดในละแวกนั้น สำหรับกรณีเหล่านั้นเราสามารถใช้สมการที่ไม่รับรองการค้นหาจุดที่ใกล้ที่สุดที่แท้จริงโดยเสมอไป แต่ข้อดีของมันก็คือมันสามารถนำไปใช้ในการพัฒนาความเร็วในด้านการค้นหาและจัดเก็บข้อมูล แต่ถึงอย่างไรก็ตามสมการที่ว่าวามารถค้นหาจุดรอบๆที่ใกล้ที่สุดได้อยู่บ่อยๆแต่ทั้งนี้ทั้งนั้นมันก็ขึ้นอยู่กับข้อมูลที่ใช้ในการวิเคราะห์ ขั้นตอนวิธีที่รองรับการค้นหาเพื่อนบ้านที่ใกล้ที่สุดแบบคาดคะเน อาทิเช่น , best bin first และ based search การประมาณหาเพื่อนบ้านที่ใกล้ที่สุด () นั้นกำลังเป็นที่นิยมสำหรับต่อกรกับคำสาปของมิติ ()
อัตราส่วนระยะทางของเพื่อนบ้านที่ใกล้ที่สุด (Nearest neighbor distance ratio)
อัตราส่วนระยะทางของเพื่อนบ้านที่ใกล้ที่สุด () นั้นใช้ไม่ได้กับระยะทางโดยตรงระหว่างจุดเริ่มแรกกับจุดที่อยู่ในละแวกเดียวกันแต่สัดส่วนของแต่ละจุดนี้ขึ้นอยู่กับระยะทางของจุดก่อนหน้านี้ที่อยู่ในละแวกเดียวกัน เทคนิคได้ถูกนำไปใช้กับ CBIR ในการค้นหารูปภาพผ่านจากตัวอย่างคำถาม โดยอ้างอิงจากความใกล้เคียงของคุณสมบัติต่างๆของรูปภาพเหล่านั้น ในเชิงลึกเทคนิคนี้ได้นำไปใช้ในปัญหาสำหรับการจับคู่
ทุกเพื่อนบ้านที่ใกล้ที่สุด (All nearest neighbors)
สำหรับขั้นตอนอื่น ตัวอย่างเช่น เราอาจมี N จุดข้อมูลและเราต้องการที่ทราบว่าจุดในละแวกไหนที่อยู่ใกล้จุดข้อมูล N เหล่านั้น เราอาจสามารถแก้ปัญหานี้ได้โดยการใช้วิธีเอ็นเอ็นเอสกับทุกจุด แต่แผนการ์ณที่ดีกว่านั้นคือการใช้ข้อมูลที่ซับซ้อนระหว่าง Nจุดที่ต้องการทราบ เพื่อที่จะสร้างการค้นหาที่มีประสิทธิภาพที่มากยิ่งขึ้น ดังเช่นตัวอย่างที่ง่ายที่จะกล่าวถึงต่อไปนี้ เมื่อไรเราได้หาระยะทางระหว่าจุด X กับ จุด Y เราก็สามารถรู้ระยะทางระหว่าง Y กับ X ในเวลาเดียวกัน เพราะฉะนั้นขั้นตอนการคำนวณที่เหมือนกันสามารถนำไปใช้ได้อีกเมื่อเราต้องการหาระยะทางจากจุด X ไปยังจุดสองจุดที่ต่างกัน
อ้างอิง
- Andrews, L.. A template for the nearest neighbor problem. C/C++ Users Journal, vol. 19 , no 11 (November 2001), 40 - 49, 2001, ISSN:1075-2838, www.ddj.com/architect/184401449
- Arya, S., D. M. Mount, N. S. Netanyahu, R. Silverman, and A. Y. Wu. An Optimal Algorithm for Approximate Nearest Neighbor Searching in Fixed Dimensions. Journal of the ACM, vol. 45, no. 6, pp. 891–923
- Beyer, K., Goldstein, J., Ramakrishnan, R., and Shaft, U. 1999. When is nearest neighbor meaningful? In Proceedings of the 7th ICDT, Jerusalem, Israel.
- Chung-Min Chen and Yibei Ling - A Sampling-Based Estimator for Top-k Query. ICDE 2002: 617-627
- Samet, H. 2006. Foundations of Multidimensional and Metric Data Structures. Morgan Kaufmann.
- Zezula, P., Amato, G., Dohnal, V., and Batko, M. Similarity Search - The Metric Space Approach. Springer, 2006.
wikipedia, แบบไทย, วิกิพีเดีย, วิกิ หนังสือ, หนังสือ, ห้องสมุด, บทความ, อ่าน, ดาวน์โหลด, ฟรี, ดาวน์โหลดฟรี, mp3, วิดีโอ, mp4, 3gp, jpg, jpeg, gif, png, รูปภาพ, เพลง, เพลง, หนัง, หนังสือ, เกม, เกม, มือถือ, โทรศัพท์, Android, iOS, Apple, โทรศัพท์โมบิล, Samsung, iPhone, Xiomi, Xiaomi, Redmi, Honor, Oppo, Nokia, Sonya, MI, PC, พีซี, web, เว็บ, คอมพิวเตอร์
karkhnhaephuxnbanthiiklthisud xngkvs nearest neighbor search epnthiruckinnamxun xathi karkhnhakhwamiklchid karkhnhakhwamkhlaykhlung hruxkarkhnhacudthiiklthisud exnexnexs khux ethkhnikhthiichinkaraekpyhathiichsahrbhacudthiiklthisudin yktwxyangcakocthytxipni emuxihest S khuxestkhxngcudinpriphumiemthriks M aela cudthikahnd q M txngkarhacudthiiklthisudkhxng S kb q inhlaykrni M nncathukaethnkhaepnmitiinpriphumikhxngyukhlid aelarayathangnnsamarthwdidcakrayathangyukhlid hrux rayathangaemnhttn inhnngsuxkhxng odnld khnuth elmthisamthimichuxwa eriykocthypyhaaebbniwa pyhaiprsniy odyxangxingthungrabbkaraenanaphuxyuxasyekiywkbiprsniythiiklthisudkarprayuktexnexnexsidthuknaipichinkaraekpyhaaelatxbocthyinhlaydan xathiechn karcaaenkrupaebb odyennipthi Optical Character recognition karaebngihepnhmwdhmukhxngtwelkhsthiti yktwxyangechn khntxnwithikarhakha k thiiklekhiyngthisud karmxngehnkhxngekhruxngkhxmphiwetxr thankhxmul xathi karcdkhxmulodykarxangxingaelakhnhacakruppphaph thtsdikarekhiydokhd karyxkhnadkhxmul rabbaenana kartladthangxinethxrent karcderiyngknkhxngdiexnex rabbsakdkha karcbthucritinkarekhiyneriyngkhwam smkarthiichsahrbkarkhnhaphunthismphs inexfxiex Finite Element Analysis karethiybekhiyngphlkaraekhngkhnephuxthiichsahrbkhadkhaenkhwamsaercindankilakhxngnkkila karwiekharahkhxmulthithukcdepnklumiwaelwkhntxnwithimihlaywithikarthisamarnaipichinkarkhnhakhatxbsahrbocthyexnexnexs idthukkhidtnkhun khaprasiththiphaphkhxngaetlawithinnsamarthhaidcakewlaaelakhwamsbsxnkhxngokhrngsrangkhxmulthithukbnthukiw karsngektxyangimepnthangkar hruxxikchuxhnungwakhasapkhxngmiti klawwaimmiphllphthkhxngcudprasngkhidxyangchdecnsahrbexnexnexsinpriphumikhxngyukhlidthimimitisung odykarichkaraeksmkarthimimakkwahnungtwaepraela ewlakhnhaaebbphhunamlxkhkarithum karkhnhaaebbesntrng karhawithiaekocthyexnexnexsthingaythisudsamarthkrathaodyerimcakkarhakharayathangcakcudthikahnd thungcudxuninthankhxmul aelaekbkhxmulesnthangthidithisudxyuesmx karhakhaaebbnibangkhrngthuktrahaepnwithithiphunthanekinipaelaichewlathanganethakb O Nd ody N khux canwnsmachikkhxng S aela d khuxmitikhxng M withikarkhnhaaebbesntrngnnimcaepnthicatxngrksaokhrngsrangkhxngkhxmul ephraachannwithikarkhnhaaebbesntrngnnimidmikhwamsmphnthkbkhwamsbsxnkhxngthankhxmul epnthinaprahladicwa withikarkhnhaaebbesntrngnnmiprasiththiphaphmakkwa xiksxngwithithicaklawthungsungkkhux karaebngpriphumibnpriphumithimimitisungkwa karaebngswnpriphumi tngaetpi 1970 withikarkhyayaelacakdekht idthukmaichinkaraekpyha inkrnikhxngpriphumikhxngyukhlid withikhxngkaraebngpriphumi nnruckinnamwawithitaaehnngechingphunthi hruxkarekhathungchingphunthi inhlaywithikhxngkaraebngpriphumi idthukphthnakhunephuxichinkaraekocthyexnexnexs bangthiwithithingayaelamikhwamsbsxnnxythisudkhux withinikhuxkaraebngaeykkhxmulxxkepnsxngfng odyfngthithukaebngnncamicudkhrunghnungcakthnghmdkhxngtxnaerkthiyngimthukaebng caaekpyhaphanthangkaraewaphantnimerimtngaetrakthungibodykaraekcudthikahnd inthukthithithukaebng withikarnikhunxyukbrayathangthiklawthunginkhatham kingephuxnbanthimitwthikalngkhnhaxyunnxaccatxngthuknamawiekharahdwy odychewlainkarhakhatxbethakb O log N inkrnithielwraythisud khuxmicudkracayknxyangimepnraebiyb xikthangeluxkhnungkhux karichokhrngsrangkhxmulaebb thiidthukxxkaebbmaephuxrxngrbkarkhnhacudthiiklthisud aebbphlwtsubenuxngcakwamnmiwithithimiprasiththiphaphinkarephimaelalbkhxngkhxmul inkrnithwipkhxngpriphumiemthriks withikarkhyayaelacakdekht ruckknphayitchuxwa tnimemthriks yktwxyangcak aela odykarichklumtwelkhcakpriphumisammitiaelaisekhaipintnimbiexsphi aelaihcudthikahndthimacakpriphumiediywkn karhaphllphththiepnipidsahrbpyhakarhacudthiiklekhiyngthisudrahwangklumkhxngcudaela dngkhaxthibaykhxngkaraeksmkartxipni inthangptibti erannsnicaekhkarhakhasbestxnidkidkhxngklumkhxngcudthnghmdthipraktihehninrayathangthisnthisudcakcudthikahndiwkxnhna cudprasngkhkhxngaetlakingkhxngtnimnikhuxkaredawacudthiiklthisudcakinklumthitngxyuinkhrunghnungkhxngpriphumithiprakxbipdwycudthitxngkarru withinixacimidphlesmxipaetmnepnkarerimtninkaraekikhpyhakhxngtwexngthidi hlngcakthiichwithiniwnsakhrbthukkingaelw eracasamarthepriybethiybwarayathangthiidcakphllphthkbrayathangthisnthisudcakcudthitxngkarthungranabthiaebngiw wakingihnnnichrayathangthisnthisud odyrayathangthisnthisudxaccaekidkhunxikcakthankhxmulxikxnthithukaebngkidephraachannbangthikhunxaccatxngphicarnathngsxngfngthithukaebng aetthungxyangirktamtharayathangipklbcakcudthitxngkarkbranabthiaebngiw nnyawkwarayathangthithukkhnhakxnhnani erakimcaepnthicatxngwiekhraahxikfngnungaelw withiniichewlasnkwawithikarkhnhaaebbesntrngephraawarayathangrahwang cudthitxngkarthrabkbklumkhxngcudthiiklthisudnnekuxbcaethiybethakbsuny withinicaichidphlktxemuxmikarkhnhaodyichcudthitxngkarthrab Locality sensitive hashing aexlexsexch khuxkhntxnthiichsahrbcbklumcudtangthixyuinthiwangihxyuepnthi odyxangxingcakrayathangcakkarkrathakaremthriksbncudehlann cudthiiklkninemthriks thithukeluxknncathukcdekhaipxyuinthiediywknodythimisthitikhwamnacaepnthisungkwa karkhnhaephuxnbanthiiklthisudinpriphumithimimitinxy rupaebbodykwangkhxngtnimnnxangxingmacakkarephimkhakhunepnsxngethakhxngthankhxmulthikhngthi esnrxbnxk inewlakhxngkarkhnhannethakb O c12 log n ody c nnethakbkarkhyaytwthikhngthikhxngkhxmulnn Vector Approximation Files inolkhlaymiti raylaexiydphayinkhxngtnimnnimsamarthnamaichpraoychnidephraawakhaepxresntkhxngcudnncatxngthuknamatrwcsxbdwy inkarephimprasiththiphaphihkbwithikhnhaepnesntrng rupaebbkarbibxdkhxngkarekbewketxrinaerm nnidthukichinkarkhdcaaenkkhxmulinkarpraemininkhrngaerk tweluxksudthaynnsamarthhaidcakinkhntxnthisxngodykarichkarpldplxykhxmulcakdiskephuxkarkhanwnrayathang Compression Clustering Based Search karcalxngkarekhathungiflnnepnwithiechphaathiichsahrbkarkhnhakhxmulaebbyx odythixngkhprakxbkhxngkhxmulthithukyxnnidthukyxcakewxrchnetmodyirkhxbngkhbichethkhnikhkaryxaelabibxdinolkhlaymitinneriykwa Vector Quantization VQ thisrangodykarcdklum thankhxmulidthukhnaelayxlngmacnehluxaekhchinkhxmulthinaechuxthuxthisud praoychnkhxngethkhnikhninnmakkwaVA File tree based indexes aela sequential scansingthiaeprphnmikhaaeprphnmakmayinocthyexnexnexsaetkhaaeprphnsxngtwthiphbecxbxythisudkhux karkhnhaephuxnbanthiiklthisudepnrayathang k aelakarpramanhaephuxnbanthiiklthisud k ephuxnbanthiiklthisud k nearest neighbor karkhnhaephuxnbanthiiklthisud k tw aesdngkhaephuxnbanthiiklkbcudthitxngkarthrabthisud k tw ethkhnikhniichxyangephrhlayickarwiekhraahkhadkhaenephuxthicapramanhruxcaaenkcudodyxangxingcakkhxsrupkhxngcudxuninlaaewkiklekhiyng krafkhxngephuxnbanthiiklthisud k ephuxnban khuxkrafthithukcudidthukechuxmtxekhakb k thiiklsudinraaewkediywkn karkhadkhaenhruxpramancudthiiklthisud Approximate nearest neighbor inkarprayuktichinbangxyang mnxacepnthiyxbrbsahrbkarkhnecxkarkhadedathidikhxngcudthiiklthisudinlaaewknn sahrbkrniehlannerasamarthichsmkarthiimrbrxngkarkhnhacudthiiklthisudthiaethcringodyesmxip aetkhxdikhxngmnkkhuxmnsamarthnaipichinkarphthnakhwamerwindankarkhnhaaelacdekbkhxmul aetthungxyangirktamsmkarthiwawamarthkhnhacudrxbthiiklthisudidxyubxyaetthngnithngnnmnkkhunxyukbkhxmulthiichinkarwiekhraah khntxnwithithirxngrbkarkhnhaephuxnbanthiiklthisudaebbkhadkhaen xathiechn best bin first aela based search karpramanhaephuxnbanthiiklthisud nnkalngepnthiniymsahrbtxkrkbkhasapkhxngmiti xtraswnrayathangkhxngephuxnbanthiiklthisud Nearest neighbor distance ratio xtraswnrayathangkhxngephuxnbanthiiklthisud nnichimidkbrayathangodytrngrahwangcuderimaerkkbcudthixyuinlaaewkediywknaetsdswnkhxngaetlacudnikhunxyukbrayathangkhxngcudkxnhnanithixyuinlaaewkediywkn ethkhnikhidthuknaipichkb CBIR inkarkhnharupphaphphancaktwxyangkhatham odyxangxingcakkhwamiklekhiyngkhxngkhunsmbtitangkhxngrupphaphehlann inechinglukethkhnikhniidnaipichinpyhasahrbkarcbkhu thukephuxnbanthiiklthisud All nearest neighbors sahrbkhntxnxun twxyangechn eraxacmi N cudkhxmulaelaeratxngkarthithrabwacudinlaaewkihnthixyuiklcudkhxmul N ehlann eraxacsamarthaekpyhaniidodykarichwithiexnexnexskbthukcud aetaephnkarnthidikwannkhuxkarichkhxmulthisbsxnrahwang Ncudthitxngkarthrab ephuxthicasrangkarkhnhathimiprasiththiphaphthimakyingkhun dngechntwxyangthingaythicaklawthungtxipni emuxireraidharayathangrahwacud X kb cud Y eraksamarthrurayathangrahwang Y kb X inewlaediywkn ephraachannkhntxnkarkhanwnthiehmuxnknsamarthnaipichidxikemuxeratxngkarharayathangcakcud X ipyngcudsxngcudthitangknxangxingAndrews L A template for the nearest neighbor problem C C Users Journal vol 19 no 11 November 2001 40 49 2001 ISSN 1075 2838 www ddj com architect 184401449 Arya S D M Mount N S Netanyahu R Silverman and A Y Wu An Optimal Algorithm for Approximate Nearest Neighbor Searching in Fixed Dimensions Journal of the ACM vol 45 no 6 pp 891 923 Beyer K Goldstein J Ramakrishnan R and Shaft U 1999 When is nearest neighbor meaningful In Proceedings of the 7th ICDT Jerusalem Israel Chung Min Chen and Yibei Ling A Sampling Based Estimator for Top k Query ICDE 2002 617 627 Samet H 2006 Foundations of Multidimensional and Metric Data Structures Morgan Kaufmann ISBN 0123694469 Zezula P Amato G Dohnal V and Batko M Similarity Search The Metric Space Approach Springer 2006 ISBN 0 387 29146 6