Range query (computer science)
કોમ્પ્યુટર વિજ્ઞાનમાં, શ્રેણી ક્વેરી સમસ્યામાં એરેની અંદર તત્વોના આપેલ અંતરાલ સંબંધિત ઘણા પ્રશ્નોના અસરકારક જવાબ આપવાનો સમાવેશ થાય છે. ઉદાહરણ તરીકે, એક સામાન્ય કાર્ય, જેને રેન્જ મિનિમમ ક્વેરી તરીકે ઓળખવામાં આવે છે, તે સંખ્યાઓની સૂચિમાં આપેલ શ્રેણીની અંદર સૌથી નાનું મૂલ્ય શોધવાનું છે. વ્યાખ્યા એરેને સ્વીકારતા કાર્યને જોતાં, એરે પરની શ્રેણી ક્વેરી બે સૂચકાંકો લે છે અને જ્યારે સબએરે પર લાગુ થાય છે ત્યારે તેનું પરિણામ આપે છે. ઉદાહરણ તરીકે, ફંક્શન માટે કે જે એરેમાં તમામ મૂલ્યોનો સરવાળો આપે છે, શ્રેણી ક્વેરી શ્રેણીમાં તમામ મૂલ્યોનો સરવાળો આપે છે. ઉકેલો ઉપસર્ગ સરવાળો શ્રેણી સરવાળા પ્રશ્નોના જવાબ ઇનપુટની સમાન લંબાઈની શ્રેણીની પૂર્વ-ગણતરી કરીને સતત સમય અને રેખીય જગ્યામાં આપી શકાય છે, જેમ કે દરેક અનુક્રમણિકા માટે, તત્વ એ તેના પ્રથમ તત્વોનો સરવાળો છે. કોઈપણ ક્વેરીની ગણતરી પછી નીચે મુજબ કરી શકાય છેઃ આ વ્યૂહરચનાને અન્ય કોઈપણ દ્વિસંગી કામગીરી સુધી વિસ્તૃત કરી શકાય છે જેનું વ્યસ્ત કાર્ય સારી રીતે વ્યાખ્યાયિત અને સરળતાથી ગણતરી કરી શકાય તેવું છે. તેને સમાન પૂર્વ-પ્રક્રિયા સાથે દ્વિ-પરિમાણીય એરે સુધી પણ વિસ્તૃત કરી શકાય છે. ડાયનેમિક રેન્જ ક્વેરીઝ સમસ્યાના વધુ મુશ્કેલ સબસેટમાં ડાયનેમિક ડેટા પર રેન્જ ક્વેરીઝ ચલાવવાનો સમાવેશ થાય છે; એટલે કે, ડેટા કે જે દરેક ક્વેરી વચ્ચે પરિવર્તન કરી શકે છે. એરે મૂલ્યોને અસરકારક રીતે અપડેટ કરવા માટે, સેગમેન્ટ ટ્રી જેવા વધુ વ્યવહારદક્ષ ડેટા સ્ટ્રક્ચર્સ જરૂરી છે. ઉદાહરણો સેમિગ્રુપ ઓપરેટરો જ્યારે શ્રેણી ક્વેરીમાં રસ ધરાવતું કાર્ય સેમિગ્રુપ ઓપરેટર હોય, ત્યારે તેની કલ્પના હંમેશા વ્યાખ્યાયિત થતી નથી, તેથી અગાઉના વિભાગમાં વ્યૂહરચના કામ કરતી નથી. એન્ડ્રુ યાઓએ દર્શાવ્યું હતું કે શ્રેણીના પ્રશ્નો માટે એક કાર્યક્ષમ ઉકેલ અસ્તિત્વમાં છે જેમાં અર્ધસમૂહ સંચાલકો સામેલ છે. તેમણે સાબિત કર્યું કે કોઈપણ અચળાંક માટે, સમય અને જગ્યાની પૂર્વ-પ્રક્રિયા સૂચિ પર શ્રેણી પ્રશ્નોના જવાબ આપવા માટે પરવાનગી આપે છે જ્યાં સમયસર અર્ધસમૂહ સંચાલક છે, જ્યાં એકરમેન કાર્યનો ચોક્કસ કાર્યાત્મક વ્યસ્ત છે. કેટલાક અર્ધસમૂહ સંચાલકો છે જે થોડા વધુ સારા ઉકેલો સ્વીકારે છે. ઉદાહરણ તરીકે, જ્યારે. ધારો કે પછી લઘુત્તમ તત્વની અનુક્રમણિકા આપે છે. પછી અનુરૂપ ન્યૂનતમ શ્રેણી ક્વેરી સૂચવે છે. એવા ઘણા ડેટા સ્ટ્રક્ચર્સ છે જે સમય અને જગ્યાના પ્રી-પ્રોસેસિંગનો ઉપયોગ કરીને સમયની રેન્જ મિનિમમ ક્વેરીનો જવાબ આપવાની મંજૂરી આપે છે. આવો જ એક ઉકેલ આ સમસ્યા અને સૌથી ઓછી સામાન્ય પૂર્વજોની સમસ્યા વચ્ચેની સમાનતા પર આધારિત છે. એરેના કાર્ટેશિયન વૃક્ષનું મૂળ અને ડાબી અને જમણી બાજુએ અનુક્રમે કાર્ટેશિયન વૃક્ષ અને કાર્ટેશિયન વૃક્ષ હોય છે. રેન્જ મિનિમમ ક્વેરી એ અને માં સૌથી નીચો સામાન્ય પૂર્વજ છે. કારણ કે સૌથી નીચો સામાન્ય પૂર્વજ સમય અને જગ્યાની પૂર્વ-પ્રક્રિયાનો ઉપયોગ કરીને સતત સમયમાં ઉકેલી શકાય છે, શ્રેણી લઘુત્તમ ક્વેરી પણ કરી શકે છે. જ્યારે ઉકેલ સમાન હોય છે. કાર્ટેશિયન વૃક્ષો રેખીય સમયમાં બનાવી શકાય છે. મોડ એરેનો મોડ એ તત્વ છે જે તેમાં સૌથી વધુ દેખાય છે. દાખલા તરીકે મોડ છે. ટાઇના કિસ્સામાં, સૌથી વધુ વારંવાર આવતા કોઈપણ તત્વોને મોડ તરીકે પસંદ કરી શકાય છે. રેન્જ મોડ ક્વેરીમાં પ્રી-પ્રોસેસિંગનો સમાવેશ થાય છે જેથી આપણે કોઈપણ શ્રેણીમાં મોડ શોધી શકીએ. આ સમસ્યાને ઉકેલવા માટે કેટલાક ડેટા સ્ટ્રક્ચર્સ તૈયાર કરવામાં આવ્યા છે, અમે નીચેના કોષ્ટકમાં કેટલાક પરિણામોનો સારાંશ આપીએ છીએ. તાજેતરમાં જોર્ગેન્સેન એટ અલ. કોષોનો ઉપયોગ કરતી કોઈપણ માહિતી માળખા માટે કોષ-તપાસ મોડેલ પર નીચલા બાઉન્ડ સાબિત થયું. મધ્યસ્થ આ ચોક્કસ કેસ ખાસ રસ ધરાવે છે કારણ કે મધ્યસ્થ શોધવાની ઘણી એપ્લિકેશનો છે. બીજી બાજુ, મધ્યસ્થ સમસ્યા, પસંદગી સમસ્યાનો એક વિશેષ કેસ, મધ્યસ્થ અલ્ગોરિધમનો ઉપયોગ કરીને O (n) માં ઉકેલી શકાય છે. જો કે રેન્જ મીડીયન ક્વેરીઝ દ્વારા તેનું સામાન્યીકરણ તાજેતરનું છે. રેન્જ મીડીયન ક્વેરી જ્યાં A, i અને j નો સામાન્ય અર્થ હોય છે તે તેનું મીડીયન એલિમેન્ટ આપે છે. સમાનરૂપે, રેન્કનું તત્વ પાછું આપવું જોઈએ. સેમીગ્રુપ ઓપરેટરો માટે યાઓના અભિગમ સહિત ઉપર ચર્ચા કરવામાં આવેલી અગાઉની કોઈપણ પદ્ધતિઓને અનુસરીને રેન્જ મીડીયન ક્વેરીઝ ઉકેલી શકાતી નથી. આ સમસ્યાના બે પ્રકારોનો અભ્યાસ કરવામાં આવ્યો છે, ઓફલાઇન સંસ્કરણ, જ્યાં રસના તમામ કે ક્વેરીઝ બેચમાં આપવામાં આવે છે, અને એક સંસ્કરણ જ્યાં તમામ પૂર્વ-પ્રક્રિયા અગાઉથી કરવામાં આવે છે. ઓફલાઇન સંસ્કરણને સમય અને જગ્યા સાથે ઉકેલી શકાય છે. ક્વિકસેલેક્ટ અલ્ગોરિધમનો નીચેનો સ્યુડોકોડ દર્શાવે છે કે આપણે સેટ કરેલી રેન્જ મીડિયન્સ શોધવા માટે, અલગ-અલગ તત્વોની બિનવર્ગીકૃત શ્રેણીમાં રેન્કના તત્વને કેવી રીતે શોધવું. રેન્જમિડીયન (A, i, j, r) {જો A.length () = = 1 વળતર A [1] જો A.low અવ્યાખ્યાયિત હોય તો m = મધ્યક (A) A.low = [e in A | e <= m] A.high = [e in A | e> m] ગણતરી કરો કે A [i, j] ના તત્વોની સંખ્યા જે A.low સાથે સંબંધિત છે જો r <= t પછી વળતરની શ્રેણીમિડીયન (A.low, i, j, r) અન્યથા વળતરની શ્રેણીમિડીયન (A.high, i, j, r-t)} પ્રક્રિયા પાર્ટીશનો, 's મધ્યકનો ઉપયોગ કરીને, બે એરેમાં અને જ્યાં પહેલામાં સમાવેશ થાય છે જો આપણે જાણતા હોઈએ કે તેના ઘટકોની સંખ્યા છે અને આ સંખ્યા તેના કરતા મોટી છે તો આપણે ક્રમના તત્વની શોધ ચાલુ રાખવી જોઈએ; અન્યથા આપણે ક્રમના તત્વની શોધ કરવી જોઈએ. શોધવા માટે, તે મહત્તમ અનુક્રમણિકા શોધવા માટે પૂરતું છે જેમ કે અંદર છે અને મહત્તમ અનુક્રમણિકા જેમ કે અંદર છે. પછી. પાર્ટીશનિંગ ભાગને ધ્યાનમાં લીધા વિના કોઈપણ ક્વેરી માટેનો કુલ ખર્ચ એ છે કે મોટાભાગના રિકર્શન કૉલ્સ કરવામાં આવે છે અને તેમાંના દરેકમાં માત્ર સતત સંખ્યાબંધ કામગીરી કરવામાં આવે છે (અપૂર્ણાંક કાસ્કેડિંગનું મૂલ્ય મેળવવા માટે તેનો ઉપયોગ કરવો જોઈએ). જો માધ્યમો શોધવા માટે રેખીય અલ્ગોરિધમનો ઉપયોગ કરવામાં આવે, તો શ્રેણી મધ્યસ્થ પ્રશ્નો માટે પૂર્વ-પ્રક્રિયાની કુલ કિંમત છે. સમસ્યાના ઓનલાઇન સંસ્કરણને ઉકેલવા માટે અલ્ગોરિધમમાં પણ ફેરફાર કરી શકાય છે. બહુમતી વસ્તુઓના આપેલ સમૂહમાં વારંવાર ઘટકો શોધવું એ ડેટા માઇનિંગમાં સૌથી મહત્વપૂર્ણ કાર્યોમાંનું એક છે. જ્યારે મોટાભાગની વસ્તુઓની આવર્તન સમાન હોય ત્યારે વારંવાર ઘટકો શોધવાનું મુશ્કેલ કાર્ય હોઈ શકે છે. તેથી, જો આવી વસ્તુઓને શોધવા માટે મહત્વના અમુક થ્રેશોલ્ડનો ઉપયોગ કરવામાં આવે તો તે વધુ ફાયદાકારક હોઈ શકે છે. મોટાભાગના એરે શોધવા માટેના સૌથી પ્રખ્યાત અલ્ગોરિધમ્સમાંથી એક બોયર અને મૂરે દ્વારા પ્રસ્તાવિત કરવામાં આવ્યું હતું, જેને બોયર-મૂર બહુમતી મત અલ્ગોરિધમ તરીકે પણ ઓળખવામાં આવે છે. બોયર અને મૂરેએ સમય પર અને જગ્યાનો ઉપયોગ કરીને સ્ટ્રિંગના બહુમતી તત્વ (જો તેમાં એક હોય તો) શોધવા માટે એક અલ્ગોરિધમનો પ્રસ્તાવ મૂક્યો. બોયર અને મૂરેના કાર્યના સંદર્ભમાં અને સામાન્ય રીતે કહીએ તો, વસ્તુઓના સમૂહમાં બહુમતી તત્વ (ઉદાહરણ તરીકે શબ્દમાળા અથવા એરે) તે છે જેની સંખ્યા તે સમૂહના કદના અડધાથી વધુ છે. થોડા વર્ષો પછી, મિશ્રા અને ગ્રીસે બોયર અને મૂરેના અલ્ગોરિધમનો વધુ સામાન્ય સંસ્કરણની દરખાસ્ત કરી હતી, જેમાં સરણીમાં તમામ વસ્તુઓને શોધવા માટે સરખામણીનો ઉપયોગ કરવામાં આવ્યો હતો, જેની સાપેક્ષ આવૃત્તિઓ અમુક સીમા કરતાં વધારે હોય છે. શ્રેણી-બહુમતી ક્વેરી એ છે કે, કદના ડેટા સ્ટ્રક્ચર (ઉદાહરણ તરીકે એરે) ની પેટા શ્રેણી આપવામાં આવે તો, તે આપેલ શ્રેણીમાં (અથવા કેટલાક પ્રકાશનોમાં સમાન) વખત કરતાં વધુ દેખાતી તમામ અલગ વસ્તુઓનો સમૂહ પરત કરે છે. વિવિધ માળખામાં કે જે શ્રેણી-બહુમતી ક્વેરીઝને ટેકો આપે છે, તે ક્યાં તો સ્થિર (પૂર્વ-પ્રક્રિયા દરમિયાન નિર્દિષ્ટ) અથવા ગતિશીલ (ક્વેરી સમયે નિર્દિષ્ટ) હોઈ શકે છે. આવા ઘણા અભિગમો એ હકીકત પર આધારિત છે કે, શ્રેણીના કદને ધ્યાનમાં લીધા વિના, આપેલ માટે ઓછામાં ઓછી સંબંધિત આવર્તન સાથે સૌથી અલગ ઉમેદવાર હોઈ શકે છે. આ દરેક ઉમેદવારોની સતત ચકાસણી કરીને, પૂછપરછનો સમય પ્રાપ્ત થાય છે. શ્રેણી-બહુમતી ક્વેરી એ અર્થમાં વિઘટનક્ષમ છે કે પાર્ટીશનો સાથેની શ્રેણીમાં-બહુમતી અને ક્યાંય અથવા બંનેમાં-બહુમતી હોવી જોઈએ. આ વિઘટનક્ષમતાને કારણે, કેટલાક ડેટા સ્ટ્રક્ચર્સ રેન્જ ટ્રીમાં ક્વેરી રેન્જના અંતિમ બિંદુઓના સૌથી ઓછા સામાન્ય પૂર્વજ (એલસીએ) ને શોધીને અને દરેક અંતિમ બિંદુથી (કદના) ઉમેદવારોના બે સેટને માન્ય કરીને એક-પરિમાણીય એરે પર બહુમતી પ્રશ્નોના જવાબ આપે છે. દ્વિ-પરિમાણીય એરે ગેગી એટ અલ. એક ડેટા માળખું પ્રસ્તાવિત કર્યું જે એરે પર શ્રેણી-બહુમતી ક્વેરીઝને સપોર્ટ કરે છે. આ માહિતી માળખામાં દરેક ક્વેરી માટે થ્રેશોલ્ડ અને લંબચોરસ શ્રેણી નિર્દિષ્ટ કરવામાં આવે છે, અને તમામ તત્વોનો સમૂહ કે જે સંબંધિત આવર્તન (તે લંબચોરસ શ્રેણીની અંદર) કરતા વધારે અથવા સમાન હોય છે તે આઉટપુટ તરીકે પરત કરવામાં આવે છે. આ માહિતી માળખું ગતિશીલ થ્રેશોલ્ડ (ક્વેરી સમયે નિર્દિષ્ટ) અને પૂર્વ-પ્રક્રિયા થ્રેશોલ્ડને ટેકો આપે છે જેના આધારે તે બનાવવામાં આવે છે. પૂર્વ-પ્રક્રિયા દરમિયાન, એરે પર ઊભી અને આડી અંતરાલોનો સમૂહ બનાવવામાં આવે છે. એકસાથે, ઊભી અને આડી અંતરાલ એક બ્લોક બનાવે છે. દરેક બ્લોક સુપરબ્લોકનો ભાગ છે જે તેના કરતા નવ ગણો મોટો છે (બ્લોકના આડા અંતરાલના ત્રણ ગણો અને તેના ઊભી અંતરાલના ત્રણ ગણો). દરેક બ્લોક માટે ઉમેદવારોનો સમૂહ (મહત્તમ ઘટકો સાથે) સંગ્રહિત કરવામાં આવે છે જેમાં તેના સંબંધિત સુપરબ્લોકમાં ઓછામાં ઓછી સંબંધિત આવર્તન (ઉપર સૂચવ્યા મુજબ પૂર્વ-પ્રક્રિયા થ્રેશોલ્ડ) ધરાવતા ઘટકોનો સમાવેશ થાય છે. આ ઘટકો તેમની આવર્તન અનુસાર બિન-વધતા ક્રમમાં સંગ્રહિત થાય છે અને તે જોવાનું સરળ છે કે, કોઈપણ તત્વ કે જે ઓછામાં ઓછું બ્લોકમાં સંબંધિત આવર્તન ધરાવે છે તે તેના ઉમેદવારોનો સમૂહ દેખાતો હોવો જોઈએ. દરેક બહુમતી ક્વેરીનો પ્રથમ જવાબ ક્વેરી બ્લોક અથવા સમયસર પ્રદાન કરેલા ક્વેરી લંબચોરસમાં સમાયેલ સૌથી મોટો બ્લોક શોધીને આપવામાં આવે છે. પ્રાપ્ત ક્વેરી બ્લોક માટે, પ્રથમ ઉમેદવારોને સમયસર પરત કરવામાં આવે છે (ચકાસણી કર્યા વિના), તેથી આ પ્રક્રિયા કેટલાક ખોટા હકારાત્મક વળતર આપી શકે છે. અન્ય ઘણા ડેટા સ્ટ્રક્ચર્સ (નીચે ચર્ચા કર્યા મુજબ) એ દરેક ઉમેદવારને સતત સમયે ચકાસવા માટેની પદ્ધતિઓ પ્રસ્તાવિત કરી છે અને આમ કોઈ ખોટા હકારાત્મક પરત ન કરતી વખતે ક્વેરી સમય જાળવી રાખ્યો છે. જે કિસ્સાઓમાં ક્વેરી બ્લોક તેના કરતા નાનો હોય છે તે નીચેના ફોર્મના આ ડેટા સ્ટ્રક્ચરના વિવિધ ઉદાહરણોને સંગ્રહિત કરીને નિયંત્રિત કરવામાં આવે છેઃ-th ઇન્સ્ટન્સની પૂર્વ-પ્રક્રિયા થ્રેશોલ્ડ ક્યાં છે. આમ, ક્વેરી બ્લોક્સ માટે-th ઉદાહરણ કરતાં નાના પ્રશ્નો પૂછવામાં આવે છે. ઉપર સૂચવ્યા મુજબ, આ માહિતી માળખામાં પૂછપરછનો સમય હોય છે અને તેની હફમેન-એન્કોડેડ નકલ સંગ્રહિત કરીને થોડી જગ્યાની જરૂર પડે છે (પરિબળની નોંધ લો અને હફમેન કોડિંગ પણ જુઓ). એક-પરિમાણીય એરે ચાન એટ અલ. પ્રસ્તાવિત ડેટા સ્ટ્રક્ચર કે જે એક-પરિમાણીય એરે, (ક્વેરી સમયે નિર્દિષ્ટ) અને થ્રેશોલ્ડ (ક્વેરી સમયે નિર્દિષ્ટ) આપવામાં આવે છે, તે જગ્યાના શબ્દોની જરૂર હોય તે સમયે તમામ બહુમતીની સૂચિ પરત કરવામાં સક્ષમ છે. આવા પ્રશ્નોના જવાબ આપવા માટે, ચાન એટ અલ. એ નોંધવાની શરૂઆત કરો કે ત્યાં એક માહિતી માળખું અસ્તિત્વમાં છે જે જગ્યાના શબ્દોની જરૂર હોય તે સમયની શ્રેણીમાં ટોપ-કે સૌથી વધુ વારંવાર વસ્તુઓને પરત કરવા માટે સક્ષમ છે. એક-પરિમાણીય શ્રેણી માટે, એક-બાજુવાળા ટોપ-કે શ્રેણી ક્વેરીને ફોર્મની થવા દો. શ્રેણીઓની મહત્તમ શ્રેણી માટે જેમાં એક અલગ તત્વની આવર્તન અપરિવર્તિત (અને તેની બરાબર) રહે છે, એક આડી રેખા ખંડ બનાવવામાં આવે છે. આ રેખા ખંડનું-અંતરાલ તેને અનુરૂપ છે અને તેનું-મૂલ્ય તેની બરાબર છે. બરાબર એક અલગ તત્વની આવર્તનમાં ફેરફાર કરવા માટે દરેક તત્વને ઉમેરવાથી, ઉપરોક્ત પ્રક્રિયા રેખા વિભાગો બનાવે છે. વધુમાં, ઊભી રેખા માટે તેને છેદતા તમામ ક્ષિતિજ રેખા ખંડોને તેમની આવર્તન અનુસાર ગોઠવવામાં આવે છે. નોંધ લો કે,-અંતરાલ સાથેનું દરેક આડી રેખા ખંડ બરાબર એક અલગ તત્વને અનુરૂપ છે, જેમ કે. ટોપ-કે ક્વેરીનો જવાબ પછી વર્ટિકલ રે શૂટ કરીને અને તેને છેદે છે તે પ્રથમ આડી રેખા સેગમેન્ટ્સની જાણ કરીને (ઉપરથી યાદ રાખો કે આ રેખા રેખા સેગમેન્ટ્સ પહેલેથી જ તેમની આવર્તન અનુસાર સૉર્ટ કરવામાં આવ્યા છે) સમયસર આપી શકાય છે. ચાન એટ અલ. પહેલા એક શ્રેણી વૃક્ષ બનાવો જેમાં દરેક શાખા નોડ એકતરફી શ્રેણી ટોપ-કે ક્વેરીઝ માટે ઉપર વર્ણવેલ માહિતી માળખાની એક નકલ સંગ્રહિત કરે છે અને દરેક પાન તેમાંથી એક તત્વનું પ્રતિનિધિત્વ કરે છે. દરેક નોડ પર ટોપ-કે ડેટા સ્ટ્રક્ચર તે નોડના સબટ્રીઝમાં અસ્તિત્વમાં રહેલા મૂલ્યોના આધારે બનાવવામાં આવ્યું છે અને તે એકતરફી શ્રેણીના ટોપ-કે પ્રશ્નોના જવાબ આપવા માટે છે. મહેરબાની કરીને નોંધ કરો કે એક-પરિમાણીય શ્રેણી માટે, શ્રેણી વૃક્ષને બે અર્ધભાગમાં વિભાજીત કરીને અને બંને અર્ધભાગ પર પુનરાવર્તન કરીને બનાવી શકાય છે; તેથી, પરિણામી શ્રેણી વૃક્ષના દરેક નોડ શ્રેણીનું પ્રતિનિધિત્વ કરે છે. તે પણ જોઈ શકાય છે કે આ શ્રેણી વૃક્ષને જગ્યાના શબ્દોની જરૂર છે, કારણ કે ત્યાં સ્તરો છે અને દરેક સ્તરમાં ગાંઠો છે. તદુપરાંત, શ્રેણી વૃક્ષના દરેક સ્તર પર તમામ ગાંઠો તેમના પેટા વૃક્ષોના કુલ ઘટકો ધરાવે છે અને ત્યાં સ્તરો હોવાથી, આ શ્રેણી વૃક્ષની જગ્યા જટિલતા છે. આ માળખાનો ઉપયોગ કરીને, સાથે પરની શ્રેણી-બહુમતી ક્વેરીનો જવાબ નીચે મુજબ આપવામાં આવે છે. પ્રથમ, લીફ નોડ્સનો સૌથી નીચો સામાન્ય પૂર્વજ (એલ. સી. એ.) અને તે સતત સમયમાં જોવા મળે છે. નોંધ લો કે ત્યાં એક ડેટા માળખું અસ્તિત્વમાં છે જેમાં જગ્યાના બિટ્સની જરૂર પડે છે જે સમયસર એલસીએ પ્રશ્નોના જવાબ આપવા માટે સક્ષમ છે. ચાલો એલ. સી. એ. ને સૂચવીએ અને, શ્રેણી-બહુમતી ક્વેરીઝ (ઉપર અને અંદર વર્ણવ્યા મુજબ) ની વિઘટનક્ષમતાનો ઉપયોગ કરીને અને તે અનુસાર, દ્વિ-પક્ષીય શ્રેણી ક્વેરીને બે એકતરફી શ્રેણી ટોપ-કે ક્વેરીઝ (થી અને) માં રૂપાંતરિત કરી શકાય છે. આ બે એકતરફી શ્રેણી ટોપ-કે ક્વેરીઓ સમયસર તેમની દરેક શ્રેણીમાં ટોપ-() સૌથી વધુ વારંવાર આવતા ઘટકોને પરત કરે છે. આ વારંવાર ઘટકો બહુમતી માટેના ઉમેદવારોનો સમૂહ બનાવે છે જેમાં એવા ઉમેદવાર હોય છે જેમાંથી કેટલાક ખોટા હકારાત્મક હોઈ શકે છે. ત્યારબાદ દરેક ઉમેદવારનું રેખીય-અવકાશ માહિતી માળખું (લેમ્મા 3 ઇંચમાં વર્ણવ્યા મુજબ) નો ઉપયોગ કરીને સતત મૂલ્યાંકન કરવામાં આવે છે, જે સમયસર નક્કી કરવામાં સક્ષમ હોય છે કે એરેની આપેલ પેટા શ્રેણીમાં કોઈ ચોક્કસ તત્વના ઓછામાં ઓછા ઉદાહરણો છે કે નહીં. ટ્રી પાથ ગેગી એટ અલ. એક માહિતી માળખું પ્રસ્તાવિત કર્યું જે પ્રશ્નોને ટેકો આપે છે, જેમ કે, બે ગાંઠો આપવામાં આવે છે અને વૃક્ષમાં, એવા તત્વોની સૂચિની જાણ કરવામાં સક્ષમ હોય છે જે એકથી બીજા માર્ગની સરખામણીમાં વધુ સંબંધિત આવર્તન ધરાવે છે. વધુ ઔપચારિક રીતે, ચાલો લેબલ કરેલું વૃક્ષ બનીએ જેમાં દરેક નોડમાં કદના મૂળાક્ષરનું લેબલ હોય. ચાલો નોડના લેબલને સૂચવીએ. ચાલો એકથી બીજા સુધીના અનન્ય માર્ગને દર્શાવીએ જેમાં મધ્ય નોડ્સની મુલાકાત લેવાના ક્રમમાં સૂચિબદ્ધ છે. આપેલ, અને એક નિશ્ચિત (પૂર્વ-પ્રક્રિયા દરમિયાન નિર્દિષ્ટ) થ્રેશોલ્ડ, ક્વેરીએ તમામ લેબલ્સનો સમૂહ પરત કરવો આવશ્યક છે જે એક કરતા વધુ વખત દેખાય છે. આ માહિતી માળખું બનાવવા માટે, પ્રથમ નોડ્સને ચિહ્નિત કરવામાં આવે છે. આ કોઈપણ નોડને ચિહ્નિત કરીને કરી શકાય છે જે ઓછામાં ઓછું ત્રણ (ઊંચાઈ) ના તળિયેથી અંતર ધરાવે છે અને જેની ઊંડાઈ દ્વારા વિભાજીત થાય છે. આમ કર્યા પછી, તે જોઇ શકાય છે કે દરેક નોડ અને તેના નજીકના ચિહ્નિત પૂર્વજ વચ્ચેનું અંતર તેના કરતા ઓછું છે. ચિહ્નિત નોડ માટે, વિવિધ સિક્વન્સ (રુટ તરફના પાથ) સંગ્રહિત કરવામાં આવે છે, જ્યાં નોડના સીધા પેરેન્ટનું લેબલ પરત કરે છે. બીજી રીતે કહીએ તો, દરેક ચિહ્નિત નોડ માટે, મૂળ તરફ બે લંબાઈ (વત્તા નોડ માટે જ એક) ની શક્તિ ધરાવતા તમામ પાથનો સમૂહ સંગ્રહિત થાય છે. વધુમાં, દરેક માટે, તમામ બહુમતી ઉમેદવારોનો સમૂહ સંગ્રહિત કરવામાં આવે છે. વધુ સ્પષ્ટ રીતે, તેમાં તમામ બહુમતી અથવા લેબલ્સનો સમૂહ હોય છે જે એક કરતા વધુ વખત દેખાય છે. તે જોવાનું સરળ છે કે ઉમેદવારોના સમૂહમાં દરેક માટે સૌથી અલગ લેબલ્સ હોઈ શકે છે. ગેગી એટ અલ. પછી નોંધ લો કે કોઈપણ ચિહ્નિત નોડથી તેના પૂર્વજોમાંના એક સુધીના માર્ગમાં તમામ બહુમતીનો સમૂહ કેટલાકમાં (લેમ્મા 2 ઇંચ) સમાવવામાં આવ્યો છે કારણ કે લંબાઈ બરાબર છે આમ ત્યાં એક અસ્તિત્વમાં છે જેની લંબાઈ x અને z વચ્ચેનું અંતર ક્યાં છે તેની વચ્ચે છે. આનું અસ્તિત્વ સૂચવે છે કે 'થી' સુધીના માર્ગમાં બહુમતી 'માં બહુમતી હોવી જોઈએ, અને તેથી તેમાં દેખાવું જોઈએ. તે જોવાનું સરળ છે કે આ માહિતી માળખાને જગ્યાના શબ્દોની જરૂર છે, કારણ કે બાંધકામના તબક્કામાં ઉપર જણાવ્યા મુજબ ગાંઠો ચિહ્નિત કરવામાં આવે છે અને દરેક ચિહ્નિત ગાંઠો માટે કેટલાક ઉમેદવાર સમૂહો સંગ્રહિત કરવામાં આવે છે. વ્યાખ્યા મુજબ, આવા સમૂહોના દરેક ચિહ્નિત નોડ માટે સ્ટોર્સ છે, જેમાંના દરેકમાં ઉમેદવારોનો સમાવેશ થાય છે. તેથી, આ માહિતી માળખાને જગ્યાના શબ્દોની જરૂર છે. મહેરબાની કરીને નોંધ કરો કે દરેક નોડ પણ સંગ્રહિત કરે છે જે રુટથી રુટ સુધીના પાથ પરના ઉદાહરણોની સંખ્યાની બરાબર છે, આ જગ્યાની જટિલતામાં વધારો કરતું નથી કારણ કે તે માત્ર નોડ દીઠ શબ્દોની સતત સંખ્યા ઉમેરે છે. બે નોડ્સ વચ્ચેની દરેક ક્વેરીનો જવાબ શ્રેણી-બહુમતી ક્વેરીઝના વિઘટનક્ષમતા ગુણધર્મ (ઉપર સમજાવ્યા મુજબ) નો ઉપયોગ કરીને અને ક્વેરી પાથને અને વચ્ચે ચાર સબપાથમાં તોડીને આપી શકાય છે. ચાલો અને અને સાથે અને અનુક્રમે સૌથી નજીકના ચિહ્નિત પૂર્વજો હોવા સાથે સૌથી નીચો સામાન્ય પૂર્વજ બનીએ. 'થી' નો માર્ગ અનુક્રમે 'થી' અને 'થી' ના માર્ગોમાં વિઘટિત થાય છે (આ માર્ગોનું કદ વ્યાખ્યા કરતાં નાનું છે, જે બધાને ઉમેદવાર તરીકે ગણવામાં આવે છે), અને 'થી' અને 'થી' ના માર્ગો (ઉપર વર્ણવ્યા મુજબ યોગ્ય શોધીને અને તેના તમામ લેબલને ઉમેદવાર તરીકે ધ્યાનમાં લઈને). મહેરબાની કરીને નોંધ કરો કે, બાઉન્ડ્રી નોડ્સને તે મુજબ નિયંત્રિત કરવા પડે છે જેથી આ તમામ સબપાથ અલગ પડે અને તેમાંથી ઉમેદવારોનો સમૂહ મેળવવામાં આવે. આ દરેક ઉમેદવારોને પછી ક્વેરીના સંયોજનનો ઉપયોગ કરીને ચકાસવામાં આવે છે જે લેબલ અને દરેક નોડના ક્ષેત્રો ધરાવતા નોડના સૌથી નીચા પૂર્વજને પરત કરે છે. - બીટ રેમ અને કદના મૂળાક્ષર પર, રેખીય જગ્યાની જરૂરિયાતો હોવા છતાં ક્વેરીનો જવાબ સમયસર આપી શકાય છે. તેથી, દરેક ઉમેદવારની સમયસર ચકાસણી કરવાથી માર્ગ પરની તમામ બહુમતીના સમૂહને પરત કરવા માટે કુલ ક્વેરી સમય મળે છે. સંબંધિત સમસ્યાઓ ઉપર વર્ણવેલ તમામ સમસ્યાઓનો અભ્યાસ ઉચ્ચ પરિમાણો તેમજ તેમની ગતિશીલ આવૃત્તિઓ માટે કરવામાં આવ્યો છે. બીજી બાજુ, શ્રેણી પ્રશ્નો વૃક્ષો જેવા અન્ય માહિતી માળખાઓ સુધી વિસ્તૃત થઈ શકે છે, જેમ કે સ્તર પૂર્વજ સમસ્યા. સમસ્યાઓનો સમાન પરિવાર ઓર્થોગોનલ શ્રેણીના પ્રશ્નો છે, જેને ગણતરીના પ્રશ્નો તરીકે પણ ઓળખવામાં આવે છે. લેવલ પૂર્વજ સમસ્યા પણ જુઓ સૌથી ઓછી સામાન્ય પૂર્વજ સંદર્ભો બાહ્ય કડીઓ ઓપન ડેટા સ્ટ્રક્ચર-પ્રકરણ 13-ડેટા સ્ટ્રક્ચર્સ ફોર ઇન્ટિજર્સ ડેટા સ્ટ્રક્ચર્સ ફોર રેન્જ મીડિયન ક્વેરીઝ-ગેર્થ સ્ટોલ્ટિંગ બ્રોડલ અને એલન ગ્રોનલંડ જોર્ગેન્સેન એરે