DOI: https://doi.org/10.1145/3725413
تاريخ النشر: 2025-06-17
المؤلف: Jianyang Gao وآخرون
الموضوع الرئيسي: تقنيات استرجاع الصور والفيديو المتقدمة
نظرة عامة
يقدم هذا القسم طريقة جديدة للتكميم تمتد لتقنية RaBitQ الحالية لاستعلامات الجار الأقرب التقريبية (ANN) في الفضاء الإقليدي عالي الأبعاد. بينما أظهرت RaBitQ أداءً متفوقًا من حيث الدقة والكفاءة عند معدلات ضغط عالية (32x)، إلا أنها لا تستوعب دقة أعلى من خلال زيادة استخدام المساحة. تحتفظ الطريقة المقترحة بالضمانات النظرية لـ RaBitQ وتحقق الأمثلية التقريبية فيما يتعلق بالتوازن بين المساحة وحدود الخطأ. كما تتميز بتنفيذات فعالة تعزز كفاءة المساحة والوقت لاستعلامات ANN، متفوقة على المعايير الحالية في الاختبارات التجريبية على مجموعات البيانات الواقعية.
في الختام، تقدم خوارزمية التكميم الجديدة تحسينات كبيرة على RaBitQ، خاصة في دعم معدلات الضغط المعتدلة مع الحفاظ على استرجاع عالٍ دون الحاجة لإعادة الترتيب. تظهر مزايا متسقة في الدقة التجريبية والضمانات النظرية مقارنة بأساليب التكميم القياسية. تسهل الطريقة المقارنات الفعالة للمسافات من خلال الاستفادة من البتات الأولية لرموز التكميم لتقليص المرشحين، مما يعزز الكفاءة الحسابية. تشمل التطبيقات المستقبلية التكيفات لتقدير المنتج الداخلي والتشابه الكوني، واستراتيجيات لضغط المتجهات بما يتجاوز 32x، والفوائد المحتملة لسيناريوهات بحث ANN وأنظمة التعلم الآلي، خاصة في تحسين استدلال وتدريب الشبكات العصبية.
مقدمة
تتناول مقدمة الورقة التحديات المرتبطة باستعلامات الجار الأقرب (NN) في الفضاءات الإقليدية عالية الأبعاد، خاصة في سياق قواعد البيانات الكبيرة حيث تعيق لعنة الأبعاد الاستعلامات الدقيقة. للتخفيف من أوقات الاستجابة الطويلة، انتقل الباحثون نحو استعلامات الجار الأقرب التقريبية (ANN)، مع التركيز بشكل أساسي على الإعدادات في الذاكرة التي تحسن توازن الوقت والدقة. ومع ذلك، فإن الاعتماد على الذاكرة الرئيسية يفرض قيودًا كبيرة في التطبيقات الواقعية، مما يستلزم طرقًا تقلل من استخدام المساحة مع الحفاظ على أداء بحث عالٍ، خاصة من حيث معدلات الاسترجاع.
تسلط الورقة الضوء على قيود الأساليب الحالية، مثل التكميم المنتج (PQ)، التي غالبًا ما تؤدي إلى استرجاع ضعيف بسبب الضغط المفرط. تقدم تقدمًا حديثًا، RaBitQ، تحسينات في كل من الدقة التجريبية والضمانات النظرية لتقدير المسافات ولكنها مقيدة بمعدلات ضغط عالية. يقترح المؤلفون توسيع RaBitQ لتحقيق معدلات ضغط معتدلة، مما يتجنب الحاجة لإعادة الترتيب مع ضمان تقدير المسافة غير المنحاز والأمثلية التقريبية في حدود الخطأ. تتضمن هذه الطريقة الجديدة بناء كتاب رموز من متجهات مشوهة، ومطابقة، ومُدورة عشوائيًا من أعداد صحيحة غير موقعة بــ \(B\) بت، مما يسمح بتقدير المسافة بكفاءة دون فك ضغط شامل. تختتم الورقة بتلخيص المساهمات، بما في ذلك تقديم طريقة تكميم جديدة، وتطبيقها على استعلامات ANN، والتحقق التجريبي الواسع الذي يظهر أداءً متفوقًا في الاسترجاع والدقة مقارنة بالمعايير الحالية.
طرق
تم إجراء الإعداد التجريبي لهذه الدراسة على آلة عالية الأداء مزودة بمعالجين Intel Xeon Gold 6418H، مع إجمالي 48 نواة و96 خيطًا، بالإضافة إلى 1 تيرابايت من الذاكرة العشوائية. تم تجميع كود المصدر بلغة C++ المستخدم في التجارب باستخدام إصدار GCC 11.4.0 مع تعيين علامات تحسين إلى `-Ofast -march=native`، وكان نظام التشغيل هو Ubuntu 22.04 LTS. وفقًا لمعايير البحث السابقة، تم تنفيذ تقييم أداء البحث في سياق خيط واحد، بينما تم تقييم أوقات الفهرسة باستخدام عدة خيوط. كود المصدر للتجارب متاح للجمهور على الرابط المقدم لمستودع GitHub.
من المتوقع أن تسهم نتائج التجارب في تقديم رؤى قيمة حول مقاييس الأداء للطرق المقترحة، بما يتماشى مع المنهجيات التي تم وضعها في الدراسات السابقة.
نقاش
في هذا القسم، يناقش المؤلفون التقدم في استعلامات الجار الأقرب التقريبية (ANN)، مع التركيز بشكل خاص على طريقة تكميم جديدة تسمى RaBitQ. تقوم هذه الطريقة بضغط متجهات البيانات في فضاء إقليدي عالي الأبعاد إلى تمثيلات منخفضة الأبعاد، تحديدًا سلاسل بــ $D$ بت، مع الحفاظ على مُقدّر غير منحاز للمسافات المربعة. يؤكد المؤلفون على أهمية تقليل استهلاك الذاكرة من خلال تخزين المتجهات المضغوطة فقط، وهو ما يمثل انحرافًا عن الأساليب التقليدية التي تعتمد على متجهات البيانات الخام المخزنة في الذاكرة العشوائية. تحقق طريقة RaBitQ حد خطأ أمثل تقريبي لتقدير المنتجات الداخلية، مع ضمان نظري لاحتمالية خطأ قدرها $O(1/\sqrt{D})$، وهو أمر مهم للبيانات عالية الأبعاد.
يقترح المؤلفون أيضًا توسيع RaBitQ الذي يسمح بمعدلات ضغط معتدلة مع تحسين الدقة. ينتقدون نهج الطريقة الأصلية في حشو المتجهات، مما يؤدي إلى دقة دون المستوى، ويقترحون بدلاً من ذلك بناء كتاب رموز في الفضاء الأصلي بــ $D$ بعد. يحافظ هذا النهج الجديد على عدم الانحياز وحدود الخطأ للمُقدّر مع السماح بالحساب الفعال للمنتجات الداخلية. تُظهر الطريقة الموسعة أنها تتطلب عددًا لوغاريتميًا من البتات بالنسبة للدقة المطلوبة، مما يحقق كل من التطبيق العملي والأمثلية النظرية. يخلص المؤلفون إلى أن طريقتهم يمكن دمجها بفعالية مع تقنيات الفهرسة الحالية، مثل أنظمة الملفات المعكوسة (IVF)، لتعزيز أداء استعلامات ANN في الذاكرة.
DOI: https://doi.org/10.1145/3725413
Publication Date: 2025-06-17
Author(s): Jianyang Gao et al.
Primary Topic: Advanced Image and Video Retrieval Techniques
Overview
The section presents a novel quantization method that extends the existing RaBitQ technique for approximate nearest neighbor (ANN) queries in high-dimensional Euclidean space. While RaBitQ has demonstrated state-of-the-art performance in terms of accuracy and efficiency at high compression rates (32x), it does not accommodate higher accuracy through increased space usage. The proposed method retains RaBitQ’s theoretical guarantees and achieves asymptotic optimality regarding the trade-off between space and error bounds. It also features efficient implementations that enhance both space and time efficiency for ANN queries, outperforming existing baselines in empirical tests on real-world datasets.
In conclusion, the new quantization algorithm offers significant improvements over RaBitQ, particularly in supporting moderate compression rates while maintaining high recall without the need for re-ranking. It demonstrates consistent advantages in empirical accuracy and theoretical guarantees compared to standard quantization methods. The method facilitates efficient distance comparisons by leveraging initial bits of quantization codes to prune candidates, enhancing computational efficiency. Future applications include adaptations for inner product and cosine similarity estimation, strategies for compressing vectors beyond 32x, and potential benefits for ANN search scenarios and machine learning systems, particularly in optimizing neural network inference and training.
Introduction
The introduction of the paper addresses the challenges associated with nearest neighbor (NN) queries in high-dimensional Euclidean spaces, particularly in the context of large-scale databases where exact queries are hindered by the curse of dimensionality. To mitigate long response times, researchers have shifted towards approximate nearest neighbor (ANN) queries, focusing primarily on in-memory settings that optimize the time-accuracy trade-off. However, the reliance on main memory poses significant constraints in real-world applications, necessitating methods that minimize space usage while maintaining high search performance, particularly in terms of recall rates.
The paper highlights the limitations of existing methods, such as product quantization (PQ), which often result in poor recall due to excessive lossy compression. A recent advancement, RaBitQ, offers improvements in both empirical accuracy and theoretical guarantees for distance estimation but is restricted to high compression rates. The authors propose an extension of RaBitQ to achieve moderate compression rates, thereby avoiding the need for re-ranking while ensuring unbiased distance estimation and asymptotic optimality in error bounds. This new method involves constructing a codebook from shifted, normalized, and randomly rotated vectors of \(B\)-bit unsigned integers, allowing for efficient distance estimation without exhaustive decompression. The paper concludes by summarizing the contributions, including the introduction of a novel quantization method, its application to ANN queries, and extensive experimental validation demonstrating superior performance in recall and accuracy compared to existing baselines.
Methods
The experimental setup for this study was conducted on a high-performance machine equipped with two Intel Xeon Gold 6418H CPUs, featuring a total of 48 cores and 96 threads, alongside 1TB of RAM. The C++ source code utilized in the experiments was compiled using GCC version 11.4.0 with optimization flags set to `-Ofast -march=native`, and the operating system was Ubuntu 22.04 LTS. Consistent with prior research benchmarks, the evaluation of search performance was executed in a single-threaded context, while indexing times were assessed using multiple threads. The source code for the experiments is publicly accessible at the provided GitHub repository link.
The results of the experiments are anticipated to contribute valuable insights into the performance metrics of the proposed methods, aligning with the methodologies established in previous studies.
Discussion
In this section, the authors discuss advancements in approximate nearest neighbor (ANN) queries, particularly focusing on a new quantization method called RaBitQ. This method compresses data vectors in a high-dimensional Euclidean space into lower-dimensional representations, specifically $D$-bit strings, while maintaining an unbiased estimator for squared distances. The authors emphasize the importance of reducing memory consumption by storing only compressed vectors, which is a departure from traditional methods that rely on raw data vectors stored in RAM. The RaBitQ method achieves an asymptotically optimal error bound for estimating inner products, with a theoretical guarantee of $O(1/\sqrt{D})$ error probability, which is significant for high-dimensional data.
The authors also propose an extension to RaBitQ that allows for moderate compression rates while improving accuracy. They critique the original method’s approach of padding vectors, which leads to sub-optimal accuracy, and instead suggest constructing a codebook in the original $D$-dimensional space. This new approach maintains the unbiasedness and error bounds of the estimator while allowing for efficient computation of inner products. The extended method is shown to require a logarithmic number of bits relative to the desired accuracy, achieving both practical applicability and theoretical optimality. The authors conclude that their method can be effectively integrated with existing indexing techniques, such as inverted file (IVF) systems, to enhance the performance of in-memory ANN queries.