Algoritma untuk pencarian tag cepat

Masalahnya adalah sebagai berikut.

• Ada satu set entitas E sederhana, masing-masing memiliki satu set tag T terlampir. Setiap entitas mungkin memiliki jumlah tag yang berubah-ubah. Jumlah entitas hampir 100 juta, dan jumlah total tag adalah sekitar 5000.

Jadi data awal adalah seperti ini:

E1 - T1, T2, T3, ... Tn
E2 - T1, T5, T100, ... Tk
..
Ez - T10, T12, ... Tl

Data awal ini sangat jarang diperbarui.

• Entah bagaimana aplikasi saya menghasilkan ekspresi logis pada tag seperti ini:

  T1 & T2 & T3 | (T5 &! T6)

• Yang saya perlukan adalah menghitung sejumlah entitas yang cocok dengan ekspresi yang diberikan (perhatikan - bukan entitas, tetapi hanya nomornya). Yang ini mungkin tidak sepenuhnya akurat, tentu saja.

Apa yang saya dapatkan sekarang adalah pencarian tabel memori yang sederhana, memberi saya waktu eksekusi 5-10 detik pada satu utas.

Saya ingin tahu, apakah ada cara efisien untuk menangani hal ini? Pendekatan apa yang akan Anda rekomendasikan? Apakah ada algoritma umum atau struktur data untuk ini?

Memperbarui

Sedikit klarifikasi seperti yang diminta.

1. Tobjek sebenarnya adalah string konstan yang relatif pendek. Tapi itu sebenarnya tidak masalah - kita selalu dapat menetapkan beberapa ID dan beroperasi pada bilangan bulat.
2. Kita pasti bisa mengatasinya.

saya akan melakukan ini di sql memiliki tabel tautan EntityCategoryantara eidentitas cidreferensi dan kategori referensi menggunakan self-joins:

    select count(ec1.eid)
    from EntityCategory ec1 
    left join EntityCategory ec2 on ec1.eid=ec2.eid 
    left join EntityCategory ec3 on ec1.eid=ec3.eid 
    ...
    where 
      ec1.cid={categoryId1} and 
      ec2.cid={categoryId2} and
      ec3.cid={categoryId3} ...

Setelah menulis jawaban ini, saya mungkin harus menandai pertanyaan sebagai "terlalu luas" - kita dapat berbicara lama tentang berbagai strategi, pada akhirnya tolok ukur harus dijalankan dengan data Anda.

Setiap tag dapat diwakili secara efisien oleh integer. Setiap entitas memiliki satu set tag. Memilih implementasi himpunan yang benar adalah penting - B-tree dan array yang diurutkan dimungkinkan. Dengan set ini, kami hanya akan melakukan tes keanggotaan. Karena kedua struktur melakukan ini dalam O (log t) (dengan t tag per entitas), saya lebih suka array karena representasi mereka yang lebih padat.

Kita sekarang dapat menyaring semua entitas dalam operasi O (n · log t · p) , di mana p adalah panjang jalur rata-rata di pohon keputusan predikat. Pohon keputusan ini dapat dipesan sehingga keputusan dapat dicapai dengan cepat. Tanpa data statistik, hanya dimungkinkan untuk mengeluarkan sub-ekspresi umum.

Urutan pencarian entitas tidak terlalu penting. Di sisi lain dapat menguntungkan untuk mengurutkannya sehingga entitas pada indeks 0untuk isemua memiliki tag tertentu, sedangkan sisanya tidak. Ini mengurangi n saat mencari tag spesifik ini (di pohon keputusan, ini harus menjadi tes pertama). Ini dapat diperluas ke beberapa level, tetapi hal ini menyulitkan dan membutuhkan memori O (2 ^k ) dengan klevel. Dengan beberapa level, tag dengan gain tertinggi harus diputuskan terlebih dahulu, di mana gain adalah jumlah entitas yang tidak harus dilihat kali kemungkinan membuangnya. Gain menjadi maksimal untuk peluang 50:50 atau ketika 50% entitas memiliki tag khusus ini. Ini akan memungkinkan Anda untuk mengoptimalkan bahkan jika pola akses tidak diketahui.

Anda juga bisa membuat set yang mengindeks entitas dengan setiap tag yang digunakan - satu set dengan semua entitas untuk T1, selanjutnya untuk T2. Optimalisasi (ruang dan waktu) yang jelas adalah berhenti ketika suatu set berisi lebih dari setengah dari semua elemen, dan untuk menyimpan elemen-elemen yang tidak memiliki tag ini - dengan cara ini, membangun indeks untuk semua tag akan memakan waktu kurang dari ½ · n · truang (dengan t tag total). Perhatikan bahwa menyimpan kumpulan pelengkap dapat membuat pengoptimalan lain lebih sulit. Sekali lagi, saya akan (mengurutkan) array untuk set.

Jika Anda juga mewakili entitas Anda melalui rentang integer, Anda dapat memampatkan ruang yang digunakan untuk set indeks dengan hanya menyimpan anggota awal dan akhir dari rentang kontinu. Implementasi-bijaksana ini mungkin akan dilakukan dengan bit tinggi untuk menunjukkan apakah suatu entri adalah rentang terikat atau entri biasa.

Jika sekarang kami memiliki kumpulan indeks (dan dengan demikian statistik pada tag) kami dapat mengoptimalkan predikat kami sehingga properti yang tidak mungkin diuji terlebih dahulu (strategi gagal-cepat). Ini berarti bahwa jika T1itu umum dan T2jarang, maka predikat T1 & T2harus dievaluasi dengan mengulangi semua T2entri kumpulan indeks dan menguji setiap elemen T1.

Jika kami menggunakan array yang diurutkan untuk mengimplementasikan set indeks, maka banyak langkah evaluasi dapat diimplementasikan sebagai operasi penggabungan. T1 & T2berarti bahwa kita mengambil T1dan T2mendaftar, mengalokasikan target array ukuran input yang lebih besar dan melakukan algoritma berikut sampai kedua input kosong: Jika T1[0] < T2[0], lalu T1++(buang kepala). Jika T1[0] > T2[0]demikian T2++. Jika kedua kepala adalah sama, lalu copy nomor yang ke array sasaran, dan kenaikan ketiga pointer ( T1, T2, target). Jika predikatnya adalah T1 | T2, maka tidak ada elemen yang dibuang tetapi yang lebih kecil disalin. Predikat formulir T1 & ¬T2juga dapat diimplementasikan menggunakan strategi penggabungan, tetapi ¬T1atau T1 | ¬T2tidak bisa.

Ini harus dipertimbangkan ketika memesan pohon keputusan predikat: Pelengkap harus terjadi pada RHS suatu &, atau pada akhirnya, ketika penghitungan akhir ditentukan dan elemen yang sebenarnya tidak harus dilihat.

Tanpa menggunakan set indeks, setiap utas dapat menyaring melalui bagian entitas dan mengembalikan jumlah elemen yang cocok dengan predikat, yang dapat disimpulkan. Saat menggunakan set indeks, maka setiap utas akan diberi satu simpul di pohon keputusan. Dibutuhkan dua aliran input yang sesuai dengan set yang dipesan, dan mengembalikan aliran yang digabungkan. Perhatikan bahwa setiap node dalam pohon keputusan memiliki set yang sesuai yang mewakili semua entitas yang memenuhi sub-ekspresi itu, dan bahwa karena urutan set, tidak perlu mengetahui seluruh set sekaligus untuk menggabungkan mereka .

Strategi yang berbeda seperti menggabungkan set yang diindekskan atau memfilter melalui daftar entitas dapat digabungkan ke tingkat tertentu. Penyaringan memiliki kinerja yang sangat mudah ditebak. Jika kueri sangat spesifik sehingga penggunaan kumpulan indeks mengurangi ruang pencarian secara drastis, maka menggabungkan operasi bisa menjadi lebih baik. Penting untuk dicatat bahwa menggabungkan banyak set input besar dapat menghasilkan kinerja yang jauh lebih buruk daripada pencarian brute-force. Algoritma yang sangat optimal akan memilih strategi yang sesuai berdasarkan ukuran input, struktur permintaan dan indikator statistik.

Selain itu, caching hasil parsial dapat bermanfaat jika diharapkan bahwa permintaan serupa akan dijalankan di masa depan, meskipun mereka tidak mempercepat proses awal.