ในด้านการรู้จำรูปแบบ iDistance เป็นเทคนิคการจัดทำดัชนีและการประมวลผลคำค้นหาสำหรับคำค้นหาเพื่อนบ้านที่ ใกล้ที่สุด k ตัว (k-nearest neighbor )บนข้อมูลจุดในพื้นที่เมตริกหลายมิติคำค้นหา kNN เป็นหนึ่งในปัญหาที่ยากที่สุดสำหรับข้อมูลหลายมิติ โดยเฉพาะอย่างยิ่งเมื่อมิติของข้อมูลสูง iDistance ได้รับการออกแบบมาเพื่อประมวลผลคำค้นหา kNN ในพื้นที่มิติสูงได้อย่างมีประสิทธิภาพ และทำงานได้ดีเยี่ยมสำหรับข้อมูลที่มีการกระจายแบบเบ้ซึ่งมักเกิดขึ้นในชุดข้อมูลในชีวิตจริง

iDistance ใช้กลยุทธ์การค้นหาแบบสองขั้นตอน โดยเริ่มจากการกรองพื้นที่ผู้สมัครเบื้องต้นและปรับปรุงผลลัพธ์ในภายหลัง ซึ่งเป็นแนวทางที่สอดคล้องกับหลักการกรองและปรับปรุง (Filter and Refine Principle: FRP)หมายความว่าดัชนีจะตัดพื้นที่การค้นหาเพื่อกำจัดผู้สมัครที่ไม่น่าจะเป็นไปได้ก่อน จากนั้นจึงตรวจสอบเพื่อนบ้านที่ใกล้ที่สุดที่แท้จริงในขั้นตอนการปรับปรุง โดยปฏิบัติตามแบบแผน FRP ทั่วไปที่ใช้ในอัลกอริธึมการค้นหาฐานข้อมูล^{[ 1 ]}ดัชนี iDistance ยังสามารถเสริมด้วยโมเดลการเรียนรู้ของเครื่องเพื่อเรียนรู้การกระจายข้อมูลสำหรับการค้นหาและการจัดเก็บข้อมูลหลายมิติที่ดีขึ้น^{[ 2 ]}

การสร้างดัชนี iDistance ประกอบด้วยสองขั้นตอน:

1. มีการเลือกจุดอ้างอิงจำนวนหนึ่งในพื้นที่ข้อมูล วิธีการเลือกจุดอ้างอิงมีหลากหลาย การใช้จุดศูนย์กลางของกลุ่มข้อมูลเป็นจุดอ้างอิงเป็นวิธีที่มีประสิทธิภาพที่สุด จุดข้อมูลจะถูกแบ่งออกเป็นเซลล์โวโรนอยโดยอาศัยจุดอ้างอิงที่เลือกไว้อย่างเหมาะสม
2. มีการคำนวณระยะห่างระหว่างจุดข้อมูลกับจุดอ้างอิงที่ใกล้ที่สุด ระยะห่างนี้บวกกับค่าการปรับขนาดเรียกว่าiDistance ของจุด นั้น ด้วยวิธีนี้ จุดในพื้นที่หลายมิติจะถูกแมปไปยังค่าหนึ่งมิติ จากนั้น สามารถใช้ B ⁺ -treeเพื่อจัดทำดัชนีจุดโดยใช้ iDistance เป็นคีย์ได้

รูปทางด้านขวาแสดงตัวอย่างการเลือกจุดอ้างอิงสามจุด (O ₁ , O ₂ , O ₃ ) จากนั้นจุดข้อมูลจะถูกแมปไปยังพื้นที่หนึ่งมิติและจัดทำดัชนีในโครงสร้าง B ⁺ -tree มีการเสนอส่วนขยายต่างๆ เพื่อให้การเลือกจุดอ้างอิงมีประสิทธิภาพในการค้นหาข้อมูลมากขึ้น รวมถึงการใช้แมชชีนเลิร์นนิงเพื่อเรียนรู้การระบุจุดอ้างอิง

ในการประมวลผลคำค้นหา kNN คำค้นหาจะถูกแปลงเป็นคำค้นหาช่วงแบบหนึ่งมิติจำนวนหนึ่ง ซึ่งสามารถประมวลผลได้อย่างมีประสิทธิภาพบน B ⁺ -tree ในภาพด้านบน คำค้นหาQถูกแปลงเป็นค่าใน B ⁺ -tree ในขณะที่ "ทรงกลม" การค้นหา kNN ถูกแปลงเป็นช่วงใน B ⁺ -tree ทรงกลมการค้นหาจะขยายออกไปเรื่อยๆ จนกว่าจะพบ kNN ซึ่งสอดคล้องกับการค้นหาช่วงที่ขยายออกไปเรื่อยๆ ใน B ⁺ -tree

เทคนิค iDistance สามารถมองได้ว่าเป็นวิธีการเร่งความเร็วในการสแกนแบบลำดับ แทนที่จะสแกนระเบียนตั้งแต่ต้นจนจบไฟล์ข้อมูล iDistance จะเริ่มการสแกนจากจุดที่สามารถค้นหาเพื่อนบ้านที่ใกล้ที่สุดได้ตั้งแต่เนิ่นๆ ด้วยความน่าจะเป็นสูงมาก

iDistance ถูกนำไปใช้ในแอปพลิเคชันหลายอย่าง รวมถึง

• การดึงรูปภาพ^{[ 3 ]}
• การจัดทำดัชนีวิดีโอ^{[ 4 ]}
• การค้นหาความคล้ายคลึงในระบบ P2P ^{[ 5 ]}
• การประมวลผลแบบเคลื่อนที่^{[ 6 ]}
• ระบบแนะนำ^{[ 7 ]}

iDistance ได้รับการเสนอครั้งแรกโดย Cui Yu, Beng Chin Ooi, Kian-Lee Tan และHV Jagadishในปี 2544 ^{[ 8 ]}ต่อมา พวกเขาร่วมกับ Rui Zhang ได้ปรับปรุงเทคนิคและทำการศึกษาอย่างครอบคลุมมากขึ้นในปี 2548 ^{[ 9 ]}

• กรองและปรับปรุง
• ฟังก์ชันที่เรียนรู้ได้

• การใช้งาน iDistance ในภาษา C โดย Rui Zhang
• การใช้งาน iDistance ของ Google ในภาษา C++
• การแยกขั้นตอนการกรองและการปรับแต่งตั้งแต่เนิ่นๆ ในการเพิ่มประสิทธิภาพการค้นหาเชิงพื้นที่
• หลักการกรองและปรับปรุง (FRP)