Approximate Membership Query Filter
અંદાજિત સભ્યપદ ક્વેરી ફિલ્ટર (AMQ-ફિલ્ટર) એ જગ્યા-કાર્યક્ષમ સંભવિત માહિતી માળખાઓનું એક જૂથ છે જે અંદાજિત સભ્યપદ પ્રશ્નોને ટેકો આપે છે. એક અંદાજિત સભ્યપદ ક્વેરી જવાબ આપે છે કે શું કોઈ તત્વ સમૂહમાં છે કે નહીં, જેનો ખોટો હકારાત્મક દર છે. બ્લૂમ ફિલ્ટર્સ એ સૌથી વધુ જાણીતા એ. એમ. ક્યુ.-ફિલ્ટર્સ છે, પરંતુ અન્ય એ. એમ. ક્યુ.-ફિલ્ટર્સ પણ છે જે વધારાની કામગીરીને ટેકો આપે છે અથવા અલગ જગ્યાની જરૂરિયાતો ધરાવે છે. એ. એમ. ક્યુ.-ફિલ્ટરની સંખ્યાબંધ એપ્લિકેશનો છે, મુખ્યત્વે ડિસ્ટ્રિબ્યુટેડ સિસ્ટમ્સ અને ડેટાબેઝમાં. ત્યાં, તેનો ઉપયોગ ઘણીવાર નેટવર્ક વિનંતી અથવા I/O કામગીરીને ટાળવા માટે થાય છે જે અસ્તિત્વમાં ન હોય તેવા તત્વોની વિનંતી કરવાથી પરિણમે છે. અંદાજિત સભ્યપદ ક્વેરી સમસ્યા અંદાજિત સભ્યપદ ક્વેરી સમસ્યા એ છે કે ઘટકોના સમૂહ વિશેની માહિતીને જગ્યા-કાર્યક્ષમ રીતે સંગ્રહિત કરવી. ધ્યેય એ છે કે કોઈ તત્વ સમૂહમાં છે કે નહીં તે પ્રશ્નોના જવાબ આપવાનું છે જ્યારે મહત્તમ સંભાવના સાથે ખોટા હકારાત્મકને મંજૂરી આપે છે. બધા AMQ-ફિલ્ટર આ ઓપરેશન લુકઅપને સપોર્ટ કરે છે. ગતિશીલ AMQ-ગાળકો કોઈપણ સમયે દાખલ કરવાની મંજૂરી આપે છે જ્યારે સ્થિર AMQ-ગાળકોને વધારાના ઘટકો દાખલ કર્યા પછી પુનઃબીલ્ડ કરવા પડે છે. કેટલાક AMQ-ફિલ્ટર ઘટકોને કાઢી નાખવા અથવા બે ગાળકોને મર્જ કરવા જેવી વધારાની કામગીરીઓને ટેકો આપે છે. લુકઅપ એ નક્કી કરી શકે છે કે શું કોઈ તત્વ ચોક્કસપણે સમૂહમાં નથી અથવા જો કોઈ તત્વ સંભવતઃ સમૂહમાં છેઃ હંમેશા સાચું આપે છે. : ની સંભાવના સાથે ખોટું પરત કરો. ફોલ્સ પોઝિટિવ એ તત્વની શોધ છે જે સમૂહનો ભાગ નથી, પરંતુ શોધ કોઈપણ રીતે સાચું આપે છે. આવું થવાની સંભાવના એ ખોટો હકારાત્મક દર છે. ફોલ્સ નેગેટિવ્સ (લુકઅપ ફોલ્સ રિટર્ન કરે છે જો કે તત્વ સમૂહનો ભાગ છે) ને AMQ-ફિલ્ટર્સ માટે મંજૂરી નથી. દાખલ એક તત્વ દાખલ કર્યા પછી આ તત્વ માટે શોધ સાચું પરત ફરવું આવશ્યક છે. ડાયનેમિક AMQ-ફિલ્ટર્સ ડેટા સ્ટ્રક્ચરનું પુનઃનિર્માણ કર્યા વિના એક સમયે એક તત્વ દાખલ કરવાનું સમર્થન કરે છે. દરેક દાખલ કર્યા પછી અન્ય એ. એમ. ક્યુ.-ફિલ્ટરનું પુનઃનિર્માણ કરવું પડશે. તેને સ્થિર AMQ-ફિલ્ટર કહેવામાં આવે છે. ફોલ્સ પોઝિટિવ રેટ વિ. સ્પેસ સંગ્રહના કદ અને ફોલ્સ પોઝિટિવ રેટ વચ્ચે ટ્રેડઓફ છે. સંગ્રહસ્થાનની જગ્યા વધારવાથી ખોટા હકારાત્મક દરમાં ઘટાડો થાય છે. સૈદ્ધાંતિક નીચલી સીમા દરેક તત્વ માટે બિટ્સ છે. ગતિશીલ એ. એમ. ક્યુ.-ફિલ્ટર આ નીચલી સીમા સુધી પહોંચી શકતા નથી. તેમને દાખલ કરવા માટે ઓછામાં ઓછા બિટ્સની જરૂર હોય છે. વિવિધ AMQ-ફિલ્ટરમાં ખોટા હકારાત્મક દર અને જગ્યાની જરૂરિયાતોની વિવિધ શ્રેણીઓ હોય છે. શ્રેષ્ઠ AMQ-ફિલ્ટર પસંદ કરવું એ એપ્લિકેશન પર આધાર રાખે છે. ડેટા સ્ટ્રક્ચર્સ અંદાજિત સભ્યપદ ક્વેરી સમસ્યાને હલ કરવાની વિવિધ રીતો છે. સૌથી વધુ જાણીતું ડેટા માળખું બ્લૂમ ફિલ્ટર્સ છે, પરંતુ અન્ય ડેટા માળખાં છે જે કેટલાક ખોટા હકારાત્મક દર અને જગ્યાની જરૂરિયાતો માટે વધુ સારું પ્રદર્શન કરે છે, વધારાની કામગીરીને ટેકો આપે છે, અથવા અન્ય નિવેશ અને શોધ સમય ધરાવે છે. કેટલાક જાણીતા એ. એમ. ક્યુ.-ફિલ્ટર્સ છેઃ બ્લૂમ ફિલ્ટર એ બ્લૂમ ફિલ્ટર એ હેશ કાર્યો સાથે બિટ્સની થોડી શ્રેણી છે. દરેક હેશ ફંક્શન એરેમાં એક સ્થાને એક તત્વને મેપ કરે છે. શરૂઆતમાં, એરેના તમામ બિટ્સ શૂન્ય પર સેટ કરવામાં આવે છે. તત્વ દાખલ કરવા માટે, તમામ હેશ વિધેયોની ગણતરી કરવામાં આવે છે અને એરેમાં તમામ અનુરૂપ બિટ્સ એક પર સેટ કરવામાં આવે છે. તત્વ શોધવા માટે, તમામ હેશ કાર્યોની ગણતરી કરવામાં આવે છે. જો તમામ અનુરૂપ બિટ્સ સુયોજિત હોય, તો સાચું પરત કરવામાં આવે છે. ખોટા હકારાત્મક દરને ઘટાડવા માટે, હેશ કાર્યોની સંખ્યા વધારી શકાય છે. ક્વોશન્ટ ફિલ્ટર ક્વોશન્ટ ફિલ્ટરનો વિચાર એ છે કે કોઈ તત્વને હેશ કરવું અને તેના ફિંગરપ્રિન્ટને ઓછામાં ઓછા નોંધપાત્ર બિટ્સમાં વિભાજિત કરવું જેને રિમેન્ડર અને સૌથી નોંધપાત્ર બિટ્સ જેને ક્વોશન્ટ કહેવાય છે. ભાગાકાર એ નક્કી કરે છે કે હેશ કોષ્ટકમાં બાકીની રકમ ક્યાં સંગ્રહિત છે. હેશ ટેબલમાં દરેક સ્લોટ માટે વધારાના ત્રણ બિટ્સનો ઉપયોગ સોફ્ટ અથડામણને ઉકેલવા માટે થાય છે (સમાન ભાગાકાર પરંતુ અલગ અવશેષો). ક્વોશન્ટ ફિલ્ટર્સ દ્વારા ઉપયોગમાં લેવાતી જગ્યા બ્લૂમ ફિલ્ટર્સ સાથે તુલનાત્મક છે, પરંતુ ક્વોશન્ટ ફિલ્ટર્સને તેમના ખોટા હકારાત્મક દરને અસર કર્યા વિના મર્જ કરી શકાય છે. કોયલ ફિલ્ટર કોયલ હેશિંગ પર આધારિત છે, પરંતુ હેશ ટેબલમાં માત્ર તત્વોની આંગળીની છાપ સંગ્રહિત કરવામાં આવે છે. દરેક તત્વમાં બે સંભવિત સ્થાનો છે. બીજા સ્થાનની ગણતરી પ્રથમ સ્થાન અને તત્વના ફિંગરપ્રિન્ટના આધારે કરવામાં આવે છે. જો કોઈ તત્વ માટે બંને સંભવિત સ્લોટ ભરેલા હોય તો પહેલેથી જ દાખલ કરેલા ઘટકોને ખસેડવા માટે આ જરૂરી છે. લોડ થ્રેશોલ્ડ સુધી પહોંચ્યા પછી કોયલ ફિલ્ટર દાખલ કરવાની ઝડપ ઘટી જાય છે. શક્ય છે કે દાખલ કરવામાં નિષ્ફળ જાય અને ટેબલને ફરીથી ધોવું પડે. જ્યારે કે બ્લૂમ ફિલ્ટર્સમાં હંમેશા સતત નિવેશનો સમય હોય છે, પરંતુ જેમ જેમ લોડ પરિબળ વધે છે તેમ તેમ ખોટા હકારાત્મક દરમાં પણ વધારો થાય છે. કોયલ ફિલ્ટર તત્વોને કાઢી નાખવાનું સમર્થન કરે છે જો આપણે ચોક્કસપણે જાણતા હોઈએ કે તત્વ દાખલ કરવામાં આવ્યું હતું. બ્લૂમ ફિલ્ટર્સ અને ક્વોશન્ટ ફિલ્ટર્સ પર આ એક ફાયદો છે જે આ કામગીરીને ટેકો આપતા નથી. Xor ફિલ્ટર એ સ્થિર AMQ-ફિલ્ટર છે જે બ્લૂમિયર ફિલ્ટર પર આધારિત છે અને વિચારને સંપૂર્ણ હેશ કોષ્ટકોનો ઉપયોગ કરે છે. કોયલ ફિલ્ટર્સની જેમ જ તેઓ હેશ ટેબલમાં તત્વોની ફિંગરપ્રિન્ટ્સ સાચવે છે. વિચાર એ છે કે જો આપેલ ત્રણ હેશ વિધેયોની xor એ તત્વની ફિંગરપ્રિન્ટ હોય તો તે માટે ક્વેરી સાચી છે. હેશ ટેબલ બનાવતી વખતે, દરેક તત્વને તેના ત્રણ સ્લોટમાંથી એક એવી રીતે સોંપવામાં આવે છે કે આ સ્લોટને અન્ય કોઈ તત્વો સોંપવામાં ન આવે. બધા ઘટકો સોંપવામાં આવ્યા પછી, અમે દરેક તત્વ માટે તેના સ્લોટનું મૂલ્ય તત્વના અન્ય બે (સોંપાયેલ નથી) સ્લોટના xor અને તત્વની ફિંગરપ્રિન્ટ પર સેટ કરીએ છીએ. આ બાંધકામ અલ્ગોરિધમ નિષ્ફળ થઈ શકે છે અને હેશ કોષ્ટકનું પુનઃનિર્માણ કર્યા વિના કોઈ ગતિશીલ નિવેશ શક્ય નથી. આ હેશ ટેબલ તત્વ દીઠ માત્ર બિટ્સનો ઉપયોગ કરીને બનાવી શકાય છે. આ ફિલ્ટરનો ગેરલાભ એ છે કે જો વધારાના ઘટકો ઉમેરવામાં આવે તો ડેટા સ્ટ્રક્ચરને ફરીથી બનાવવું પડશે. તેનો ઉપયોગ એવી એપ્લિકેશનોમાં થાય છે જ્યાં પછીથી કોઈ તત્વોને ઉમેરવાની જરૂર નથી અને જગ્યા મહત્વની છે. એપ્લિકેશન એ. એમ. ક્યુ.-ફિલ્ટર્સની લાક્ષણિક એપ્લિકેશનો ડિસ્ટ્રિબ્યુટેડ સિસ્ટમ્સ અને ડેટાબેઝ સિસ્ટમ્સ છે. એ. એમ. ક્યુ.-ફિલ્ટર ડેટાબેઝ અથવા દૂરસ્થ મેમરીના કીઓના સમૂહના પ્રોક્સી તરીકે કાર્ય કરે છે. ડેટાબેઝ અથવા રિમોટ મેમરીમાં અનુમાનિત ધીમી ક્વેરી કરવામાં આવે તે પહેલાં AMQ-ફિલ્ટરનો ઉપયોગ ડેટાબેઝ અથવા રિમોટ મેમરીમાં કી છે કે કેમ તે અંદાજિત કરવા માટે થાય છે. ધીમી ક્વેરી ત્યારે જ કરવામાં આવે છે જ્યારે AMQ-ફિલ્ટર સાચું આવે. માત્ર ખોટા હકારાત્મક પરિણામ બિનજરૂરી I/O કામગીરી અથવા દૂરસ્થ પ્રવેશ તરફ દોરી જાય છે. એપ્લિકેશન્સ અસંખ્ય છે અને તેમાં પેકેજ અને રિસોર્સ રાઉટીંગ, પી2પી નેટવર્ક્સ અને ડિસ્ટ્રિબ્યુટેડ કેશીંગનો સમાવેશ થાય છેઃ એએમક્યુ-ફિલ્ટર્સનો ઉપયોગ ઘણીવાર મોંઘા ડિસ્ક ઍક્સેસને ટાળવા માટે ઇન-મેમરી ડેટા સ્ટ્રક્ચર તરીકે થાય છે. એક એપ્લિકેશન લોગ-સ્ટ્રક્ચર્ડ મર્જ-ટ્રીઝ અથવા એલએસએમ-ટ્રીઝ છે. તેમની પાસે ઝડપી ઇન-મેમરી ઘટક હોય છે અને ડિસ્ક પર એક અથવા બહુવિધ ઘટકો હોય છે જે પોતે વૃક્ષો હોય છે. જ્યાં સુધી તે તેના મહત્તમ કદ સુધી ન પહોંચે ત્યાં સુધી ઘટકો ઇન-મેમરી ઘટકમાં દાખલ કરવામાં આવે છે, જ્યારે ઇન-મેમરી ઘટક ડિસ્ક ઘટકો સાથે ભળી જાય છે. શોધને ઝડપી બનાવવા માટે ઘણા એલએસએમ-વૃક્ષો બ્લૂમ ફિલ્ટર્સ અથવા ક્વોશન્ટ ફિલ્ટર્સ જેવા એએમક્યુ-ફિલ્ટર્સનો અમલ કરે છે. તે ગાળકો દરેક ઘટક માટે અંદાજિત છે કે તેમાં કયા ઘટકો સંગ્રહિત છે. એલએસએમ-વૃક્ષોનો ઉપયોગ અપાચે એસ્ટરિક્સડીબી, બિગટેબલ, એચબેઝ, લેવલડીબી, એસક્યુએલાઇટ 4 જેવા ડેટાબેઝમાં થાય છે. નેટવર્ક્સ AMQ-ફિલ્ટર્સ માટે ઘણી બધી એપ્લિકેશનો ઓફર કરે છે. તેનો ઉપયોગ અલગ સર્વર પર સ્થિત ડેટાના સમૂહને અંદાજિત કરવા માટે થાય છે. ઘણા કિસ્સાઓમાં તે AMQ-ફિલ્ટર્સને અપરિવર્તનીય તરીકે જોઈ શકાય છે. જો દૂરસ્થ સર્વર પરનો સેટ બદલાય તો પણ AMQ-ફિલ્ટરને ઘણીવાર તરત જ અપડેટ કરવામાં આવતું નથી, પરંતુ કેટલાક ખોટા હકારાત્મકને સહન કરવામાં આવે છે. આ એપ્લિકેશનનું એક ઉદાહરણ વેબ કેશ શેરિંગ છે. જો પ્રોક્સી પાસે કેશ મિસ હોય તો તે નક્કી કરવા માંગે છે કે અન્ય પ્રોક્સી પાસે વિનંતી કરેલ ડેટા છે કે નહીં. તેથી, પ્રોક્સીને ખબર હોવી જોઈએ અથવા ઓછામાં ઓછું અંદાજિત હોવું જોઈએ કે જો અન્ય પ્રોક્સી વિનંતી કરેલ વેબ પૃષ્ઠ ધરાવે છે. આને સમયાંતરે વેબ પૃષ્ઠોના યુઆરએલના સ્થિર એએમક્યુ-ફિલ્ટરને પ્રસારિત કરીને આર્કાઇવ કરી શકાય છે, જે પ્રોક્સીએ યુઆરએલ સૂચિને પ્રસારિત કરવાને બદલે કેશ કર્યા છે. આ સેટિંગમાં, જો સમયાંતરે અપડેટ્સ વચ્ચે કેશ બદલાઈ જાય તો ખોટા નકારાત્મક થઈ શકે છે. આ જ ખ્યાલ P2P નેટવર્ક પર લાગુ કરી શકાય છે. એ. એમ. ક્યુ.-ફિલ્ટરનો ઉપયોગ નેટવર્કના દરેક નોડ પર શું સંગ્રહિત છે તેનો અંદાજ કાઢવા માટે થઈ શકે છે. ફિલ્ટરને નોડના વાસ્તવિક દસ્તાવેજોના આઇડી અથવા કીવર્ડ્સથી ભરી શકાય છે. ખોટા હકારાત્મક માત્ર કેટલીક બિનજરૂરી વિનંતીઓ તરફ દોરી જાય છે. AMQ-ફિલ્ટર્સ પાસે P2P નેટવર્ક્સમાં વધુ એપ્લિકેશનો છે, ઉદાહરણ તરીકે વિવિધ નોડ્સ પર સંગ્રહિત સમૂહો વચ્ચેનો તફાવત અથવા આંતરછેદ શોધવો. સંદર્ભો સંભવિત માહિતી માળખાં