Cấu trúc dữ liệu để tìm các phím lân cận với các bit tương tự

Question

Tôi có một số dữ liệu, lên đến một triệu và một tỷ bản ghi, mỗi bản ghi được biểu thị bằng bitfield, khoảng 64 bit cho mỗi khóa. Các bit độc lập, bạn có thể tưởng tượng chúng về cơ bản là các bit ngẫu nhiên.

Nếu tôi có khóa kiểm tra và tôi muốn tìm tất cả các giá trị trong dữ liệu của tôi bằng cùng một khóa, bảng băm sẽ nhổ ra các giá trị đó rất dễ dàng, trong O (1).

Cấu trúc thuật toán/dữ liệu nào sẽ tìm thấy tất cả các bản ghi hiệu quả nhất tương tự với khóa truy vấn? Ở đây có nghĩa là hầu hết các bit giống nhau, nhưng một số tối thiểu được phép sai. Điều này được đo theo truyền thống bởi Hamming distance., chỉ đếm số bit không khớp. Có hai cách truy vấn này có thể được thực hiện, có thể bằng cách chỉ định tỷ lệ không khớp như "cung cấp cho tôi danh sách tất cả các khóa hiện có có ít hơn 6 bit khác với truy vấn của tôi" hoặc đơn giản là các kết quả phù hợp nhất, như "cung cấp cho tôi danh sách 10.000 khóa có số bit khác nhau thấp nhất từ ​​truy vấn của tôi".

Bạn có thể bị tạm thời chạy đến k-nearest-neighbor algorithms, nhưng ở đây chúng tôi đang nói về các bit độc lập, do đó, dường như các cấu trúc như quadtrees không hữu ích.

Sự cố có thể được giải quyết bằng cách thử nghiệm sức mạnh vũ phu đơn giản một bảng băm cho số lượng bit khác nhau thấp. Nếu chúng ta muốn tìm tất cả các khóa khác nhau một chút so với truy vấn của chúng ta, ví dụ, chúng ta có thể liệt kê tất cả 64 khóa có thể và kiểm tra tất cả chúng. Nhưng điều này phát nổ nhanh chóng, nếu chúng ta muốn cho phép hai bit khác biệt, thì chúng ta phải thăm dò 64 * 63 = 4032 lần. Nó trở nên tồi tệ hơn theo cấp số nhân cho số bit cao hơn.

Vậy có cấu trúc hoặc chiến lược dữ liệu nào khác làm cho loại truy vấn này hiệu quả hơn không? Cơ sở dữ liệu/cấu trúc có thể được xử lý nhiều như bạn muốn, đó là tốc độ truy vấn cần được tối ưu hóa.

Answer 1

Điều bạn muốn là BK-Tree . Đó là một cây lý tưởng để lập chỉ mục các không gian số liệu (vấn đề của bạn là một) và hỗ trợ cả các truy vấn lân cận và gần nhất. Tôi đã viết an article về nó một thời gian trước đây.

BK-Cây thường được mô tả với tham chiếu đến văn bản và sử dụng khoảng cách levenshtein để xây dựng cây, nhưng thật đơn giản để viết một về chuỗi nhị phân và khoảng cách hamming.

Answer 2

Vâng, bạn có thể chèn tất cả các khóa lân cận cùng với khóa gốc. Điều đó có nghĩa là bạn lưu trữ (64 k chọn) gấp nhiều lần dữ liệu, cho k bit khác nhau, và nó sẽ yêu cầu bạn quyết định k trước. Mặc dù bạn luôn có thể mở rộng k bởi hàng xóm truy vấn lực lượng vũ phu, và điều này sẽ tự động truy vấn những người hàng xóm của hàng xóm của bạn mà bạn đã chèn vào. Điều này cũng mang lại cho bạn một sự cân bằng không gian thời gian: ví dụ, nếu bạn chấp nhận một 64-dữ liệu blowup và 64 lần chậm hơn, bạn có thể nhận được hai bit khoảng cách.

Answer 3

Tôi muốn sử dụng số inverted index, như công cụ tìm kiếm. Về cơ bản, bạn có từ vựng cố định là 64 từ. Sau đó, độ tương đồng được đo bằng khoảng cách hamming, thay vì độ tương tự cosin giống như một công cụ tìm kiếm sẽ muốn sử dụng. Việc xây dựng chỉ mục sẽ chậm, nhưng bạn phải có khả năng truy vấn nó với tốc độ tìm kiếm thông thường.

Cuốn sách Introduction to Information Retrieval bao gồm việc xây dựng, lưu trữ, nén và truy vấn hiệu quả các chỉ mục ngược.

Answer 4

"Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions", từ năm 2008, có vẻ là kết quả tốt nhất kể từ đó. Tôi sẽ không cố gắng tóm tắt kể từ khi tôi đọc nó hơn một năm trước và nó là lông. Đó là từ một trang trên locality-sensitive hashing, cùng với việc triển khai phiên bản trước đó của lược đồ. Để có thêm các con trỏ tổng quát, hãy đọc lên trên nearest neighbor search.

Đây là loại câu hỏi đã được hỏi trước: Fastest way to find most similar string to an input?

Answer 5

này nghe có vẻ như một sự phù hợp tốt cho S-Tree, mà là giống như một file đảo thứ bậc.nguồn lực tốt về chủ đề này bao gồm các giấy tờ sau:

Hierarchical Bitmap Index: An Efficient and Scalable Indexing Technique for Set-Valued Attributes.

Improved Methods for Signature-Tree Construction (2000)

Trích dẫn từ cái đầu tiên:

Các thứ bậc chỉ số bitmap e ffi ciently hỗ trợ khăn lớp ferent các truy vấn, bao gồm các truy vấn con, superset và tương tự. Thử nghiệm của chúng tôi cho thấy chỉ mục bitmap phân cấp hoạt động tốt hơn các kỹ thuật lập chỉ mục khác được thiết lập một cách đáng kể.

Các giấy tờ này bao gồm các tham chiếu đến nghiên cứu khác mà bạn có thể thấy hữu ích, chẳng hạn như M-Trees.

Answer 6

Tạo cây nhị phân (cụ thể là trie) biểu thị mỗi khóa trong bộ bắt đầu của bạn theo cách sau: Nút gốc là từ trống, di chuyển xuống cây sang bên trái nối thêm 0 và di chuyển xuống bên phải nối thêm 1. Cây sẽ chỉ có nhiều lá khi bộ bắt đầu của bạn có các phần tử, do đó kích thước nên được quản lý.

Bây giờ bạn có thể thực hiện truy cập đệ quy của cây này, cho phép tối đa n "độ lệch" từ khóa truy vấn trong mỗi dòng thực thi đệ quy, cho đến khi bạn tìm thấy tất cả các nút trong tập hợp bắt đầu nằm trong số đó độ lệch.

Answer 7

Nếu dữ liệu không quá thưa thớt, biểu đồ có các phím như đỉnh và các cạnh nối các nút 'lân cận' (Hamming distance = 1) có thể rất hiệu quả về thời gian. Không gian sẽ rất lớn, vì vậy trong trường hợp của bạn, tôi không nghĩ rằng nó sẽ là một sự cân bằng đáng giá.

Answer 8

Tôi chưa hoàn toàn nghĩ về điều này, nhưng tôi có ý tưởng về nơi tôi sẽ bắt đầu.

Bạn có thể chia không gian tìm kiếm lên thành một số xô trong đó mỗi thùng có xô chìa khóa và các phím trong xô là chìa khóa tương tự hơn để chốt xô này hơn bất kỳ phím nào xô khác. Để tạo khóa thùng, bạn có thể tạo ngẫu nhiên các khóa 64 bit và loại bỏ bất kỳ khóa nào quá gần với bất kỳ khóa nhóm nào được tạo trước đó hoặc bạn có thể thực hiện một số thuật toán tạo các khóa không giống nhau. Để tìm khóa gần nhất với khóa kiểm tra, trước tiên hãy tìm khóa thùng gần nhất và sau đó kiểm tra từng khóa trong nhóm. (Trên thực tế, có thể, nhưng không có khả năng, cho khóa gần nhất ở trong một nhóm khác - bạn có cần tìm khóa gần nhất hoặc khóa rất gần đủ tốt không?)

Answer 9

Nếu bạn đồng ý với thuật toán ngẫu nhiên (monte carlo trong trường hợp này), bạn có thể sử dụng minhash.

Answer 10

Cơ sở dữ liệu/cấu trúc có thể được xử lý trước như nhiều như bạn thích

Vâng ... NẾU đó là sự thật. Sau đó, tất cả những gì bạn cần là một ma trận tương tự về khoảng cách hamming của bạn. Làm cho ma trận thưa thớt bằng cách cắt tỉa các khoảng cách lớn. Nó không nhận được bất kỳ nhanh hơn và không phải là nhiều của một con heo bộ nhớ.

Answer 11

• cấu trúc dữ liệu cho bộ lớn mô tả ở đây: Detecting Near-Duplicates for Web Crawling hoặc
• trong bộ nhớ Trie: Judy-arrays at sourceforge.net

Answer 12

Giả sử bạn phải truy cập mỗi hàng để kiểm tra giá trị của nó (hoặc nếu bạn chỉ mục trên các bitfield sau đó mỗi mục nhập chỉ mục), sau đó bạn có thể viết kiểm tra thực tế khá hiệu quả bằng cách sử dụng

Một xor B

Để tìm bit khác nhau, sau đó đếm bit kết quả, sử dụng kỹ thuật như this.

Điều này mang lại hiệu quả cho bạn khoảng cách hấp dẫn.

Vì điều này có thể biên dịch xuống hàng chục hướng dẫn cho mỗi thử nghiệm, điều này có thể chạy khá nhanh.

Answer 13

Nếu bạn đồng ý với việc xác minh, tôi nghĩ bạn có cách tốt để giải quyết câu hỏi 2. Tôi giả sử bạn có 2^30 dữ liệu và cutoff và bạn muốn tìm tất cả các điểm trong phạm vi cutoff khoảng cách từ test.

 
One_Try() 
    1. Generate randomly a 20-bit subset S of 64 bits 
    2. Ask for a list of elements that agree with test on S (about 2^10 elements) 
    3. Sort that list by Hamming distance from test 
    4. Discard the part of list after cutoff 

Bạn lặp lại One_Try nhiều như bạn cần trong khi hợp nhất danh sách. Bạn càng có nhiều cố gắng, bạn càng tìm thấy nhiều điểm hơn. Ví dụ: nếu x nằm trong 5 bit, bạn sẽ tìm thấy nó trong một lần thử với khoảng (2/3)^5 = xác suất 13%. Do đó, nếu bạn lặp lại 100 lần thử, bạn sẽ tìm thấy tất cả nhưng khoảng 10^{- 6} trong số x đó. Tổng thời gian: 100*(1000*log 1000).

Ưu điểm chính của việc này là bạn có thể ra câu trả lời cho câu hỏi 2 như bạn tiến hành, kể từ sau khi vài cố gắng đầu tiên bạn chắc chắn sẽ tìm thấy tất cả mọi thứ trong khoảng cách không quá 3 bit vv

Nếu bạn có nhiều máy tính, bạn cung cấp cho chúng nhiều lần thử, vì chúng hoàn toàn song song: mỗi máy tính sẽ lưu trước một số bảng băm.