Tính P-đầy đủ trong duyệt chỉ mục ngược: Đánh giá độ phức tạp của truy vấn Boolean trên đồ thị DAG

Tác giả: Amir Aavani

Các AI agent hiện đại ngày càng phụ thuộc vào cơ sở hạ tầng tìm kiếm để thực thi các quy trình suy luận neuro-symbolic phức tạp. Các quy trình này thường được biên dịch thành các truy vấn Boolean lồng nhau sâu, phi đơn điệu trên các trường văn bản. Tuy nhiên, các chiến lược đánh giá truy vấn tiêu chuẩn trên chỉ mục đảo ngược (inverted indices) đối mặt với những giới hạn lý thuyết nghiêm trọng khi xử lý các cấu trúc này. Các mô hình iterator có trạng thái (Document-at-a-Time) bị giới hạn về mặt cấu trúc bởi đánh giá công thức NC^1, dẫn đến sự bùng nổ theo cấp số nhân O(2^|Q|) trong độ phức tạp truy vấn ở trường hợp xấu nhất khi giải mã logic hội tụ lại (re-convergent logic). Ngược lại, các mô hình hiện thực hóa đệ quy (Term-at-a-Time) phải chịu mức phạt độ phức tạp không gian Ω(|U|) (Universal Scan) khi đánh giá phủ định logic trên toàn bộ tập hợp tài liệu.

Trong bài báo này, chúng tôi thiết lập các ranh giới lý thuyết của việc thực thi logic phức tạp một cách nguyên bản trên chỉ mục đảo ngược. Chúng tôi chính thức hóa một ngôn ngữ truy xuất (L_R) dựa trên Đồ thị có hướng không chu trình (DAGs) và chứng minh rằng bài toán đánh giá của nó là P-Complete nghiêm ngặt. Để làm cho việc đánh giá trở nên khả thi, chúng tôi giới thiệu ComputePN, một thuật toán đánh giá tất định, nhận biết độ thưa (sparsity-aware). Bằng cách tách biệt phủ định logic khỏi việc hiện thực hóa ở quy mô toàn bộ thông qua biểu diễn kép Positive-Negative mới, và sử dụng tính năng ghi nhớ (memoization) DAG nguyên bản, ComputePN giới hạn chặt chẽ thời gian đánh giá ở mức O(|Q| · |U_active|). Cách tiếp cận này đánh giá thành công các truy vấn P-Complete một cách nguyên bản trên chỉ mục, tránh được cả nút thắt mở rộng cây tổ hợp và mức phạt quét toàn bộ, đặt nền tảng chính thức cho truy xuất tính toán.

Các bài đọc liên quan và cập nhật.

Bài báo này giới thiệu Wally, một hệ thống tìm kiếm riêng tư hỗ trợ các truy vấn tìm kiếm ngữ nghĩa và từ khóa hiệu quả trên các cơ sở dữ liệu lớn. Khi có đủ số lượng khách hàng thực hiện truy vấn, hiệu suất của Wally tốt hơn đáng kể so với các hệ thống trước đây. Trong các hệ thống tìm kiếm riêng tư trước đây, với mỗi truy vấn của khách hàng, máy chủ phải thực hiện ít nhất một thao tác mật mã đắt đỏ cho mỗi mục nhập cơ sở dữ liệu. Kết quả là, hiệu suất bị suy giảm…

Đọc thêm

Bài báo này đã được chấp nhận tại Industry Track của hội nghị SIGIR 2024.

Trợ lý ảo (VAs) là các nền tảng Truy xuất thông tin quan trọng giúp người dùng hoàn thành nhiều tác vụ khác nhau thông qua các lệnh bằng giọng nói. Hệ thống nhận dạng giọng nói (speech-to-text) sử dụng các truy vấn ưu tiên (query priors), được huấn luyện hoàn toàn trên văn bản, để phân biệt giữa các lựa chọn thay thế gây nhầm lẫn về mặt ngữ âm. Do đó, việc tạo ra các truy vấn tổng hợp tương tự như cách sử dụng VA hiện tại có thể cải thiện đáng kể…

Đọc thêm