आकाश को सूचकांक

स्थानिक खोज की आवश्यकता काफी बार उठती है। साथ ही स्थानिक जोइन में - दो सेट सुविधाओं के प्रतिच्छेदन का पता लगाना। हमेशा भारी तोपखाने को आकर्षित नहीं करना चाहते हैं। ठीक है, चलो "थोड़ा खून, एक शक्तिशाली झटका" के साथ समस्या को हल करने का एक तरीका है।

परिचय

यह ज्ञात है कि एक से अधिक आयामी वस्तुओं को अनुक्रमित करना एक महत्वपूर्ण समस्या है, हालांकि इसके लिए आवश्यकता काफी बड़ी है। जो कठिनाइयाँ होती हैं वे प्रकृति में उद्देश्यपूर्ण होती हैं। कोई फर्क नहीं पड़ता कि हम क्या करते हैं, भौतिक माध्यम पर सूचकांक फ़ाइल अनुक्रमिक (एक-आयामी) है और हमें कुछ प्रकार के ट्रैवर्सल ऑफ प्लेन (स्थान) प्रदान करना चाहिए। इसी समय, सूचकांक फ़ाइल में बहुत दूर नहीं अंतरिक्ष में करीब बिंदुओं को व्यवस्थित करने की एक सहज इच्छा है। दुर्भाग्य से, बिना ब्रेक के यह संभव नहीं है।

जीआईएस समुदाय में स्थानिक अनुक्रमण के लिए रवैया आम तौर पर दुगुना है। एक ओर, इस समुदाय के सदस्यों की एक उचित संख्या में विश्वास है कि कोई समस्या नहीं है, अगर ऐसी कोई आवश्यकता उत्पन्न हुई थी, तो उन्होंने इसे दो तरीकों से प्रबंधित किया होगा। और दूसरी ओर, एक राय है कि "सब कुछ हमारे सामने पहले ही चुरा लिया गया है", अधिकांश आधुनिक डीबीएमएस किसी तरह इस समस्या को हल करने का प्रबंधन करते हैं, कुछ काफी पहले और सामान्य तौर पर, सफलतापूर्वक।

जैसा कि अक्सर होता है, तथ्य यह है कि हम एक गोफर नहीं देखते हैं इसका मतलब यह नहीं है कि यह मौजूद नहीं है। एक बार जब डेटा वॉल्यूम काफी बढ़ जाता है, तो यह पाया जाता है कि स्थानिक सूचकांक के निर्माण के बाद से ही समस्या हो सकती है या तो एल्गोरिथ्म परिभाषा से परे चला जाता है, या निर्माण का समय अस्वीकार्य रूप से लंबा हो जाता है, या खोज अप्रभावी होती है ... जैसे ही स्थानिक डेटा तेजी से बदलना शुरू होता है, स्थानिक सूचकांक नीचा दिखाना शुरू कर सकता है। सूचकांक के पुनर्निर्माण में मदद मिलती है, लेकिन लंबे समय तक नहीं।

यहां हम स्थानिक डेटा को अनुक्रमित करने के सबसे सरल मामले को देखते हैं - बिंदु सुविधाओं के साथ काम करना। हम एक व्यापक वक्र का उपयोग करके निर्देशांक की ईमानदार कोडिंग का उपयोग करेंगे। बेशक, अन्य तरीके हैं, पिक्सेल-ब्लॉक इंडेक्स, आर-ट्री, क्वाड-ट्री, सबसे खराब। शायद यह एक और लेख के लिए विषय है, लेकिन अब हम एक व्यापक वक्र की मदद से बिंदु वस्तुओं के साथ बिल्कुल काम का वर्णन कर रहे हैं।
हम यह नहीं कहेंगे कि प्रस्तावित विधि आदर्श है, लेकिन इसके कम से कम दो फायदे हैं - यह बहुत सरल और बहुत प्रभावी है। इसकी मदद से, सचमुच "घुटने पर" आप काफी गंभीर समस्याओं को हल कर सकते हैं।

डेटा के रूप में हम एक स्टार एटलस लेते हैं और यादृच्छिक संख्याओं के साथ इसके सिमुलेशन। प्रत्येक डेटा सेट में कई ऑब्जेक्ट होते हैं, जिनमें से प्रत्येक का वर्णन किया गया है:

• एक्स - समन्वय, 32-बिट पूर्णांक मान
• Y - समन्वय, 32-बिट पूर्णांक मान
• वैल - 32-बिट पूर्णांक मान

डेटा का परीक्षण करें

हमारे पास कई डेटा सेट हैं:

1. 55M - इस सेट में 55,368,239 ऑब्जेक्ट्स होते हैं जिनके निर्देशांक अंतराल में यादृच्छिक संख्याएँ 0 ... 2 ** 27 X और 0 ... 2 ** 26 Y में होते हैं, VAL हमेशा 0 होता है।
   
2. 526M - इस सेट में 526,280,881 ऑब्जेक्ट होते हैं जिनके निर्देशांक अंतराल में यादृच्छिक संख्याएँ 0 ... 2 ** 27 एक्स में हैं और 0 ... 2 ** 27 वाई में, वैल हमेशा 0 है।
   
3. USNO-SA2.0 - यह 55.368.239 सितारों की एक सूची है, जो ftp://ftp.nofs.navy.mil से प्राप्त की गई है।
   एक्स-समन्वय (दशमलव घंटों में आरए (राइट एसेन्शन)) * 15 * 3600 * 100 है
   वाई - समन्वय - (दशमलव डिग्री में डीईसी) +90) * 3600 * 100
   वैल एक निश्चित मूल्य है, जो अन्य चीजों के अलावा, लाल और नीले रंग की श्रेणियों में चमक शामिल करता है।
   
4. USNO-A2.0 - यह 526,280,881 सितारों की एक सूची है, जिसे ftp://ftp.nofs.navy.mil से प्राप्त किया जा सकता है। इस डेटा के लिए केवल अनुमान प्रदान किए गए हैं। इसकी वस्तुओं के मूल्य USNO-SA2.0 के समान हैं

सिद्धांत

स्वीपिंग कर्व का विचार असतत स्थान को क्रमबद्ध करना है। एक विशेषता को एन-आयामी अंतरिक्ष में एक बिंदु द्वारा दर्शाया गया है। समतल पर एक बिंदु स्वयं का प्रतिनिधित्व करता है, एक सपाट आकृति का वर्णन करने वाली एक आयताकार सीमा एक 4-आयामी बिंदु है, आदि। इस तरह का एक बिंदु एक निश्चित लंबाई की संख्या है जिससे निपटना काफी आसान है। विशेष रूप से, इस तरह की संख्या को नियमित बी-पेड़ में रखा जा सकता है। खोज क्वेरी को स्वीपिंग वक्र के निरंतर खंडों में विभाजित किया गया है और प्रत्येक खंड के लिए एक सबक्वेरी की गई है। सभी बिंदु जो कि उप-अंतराल के अंतराल में आते हैं, वे आवश्यक हैं।

इस प्रकार, हमें एक वक्र की आवश्यकता है जो हमारे प्रत्येक बिंदु (इस मामले में दो आयामी) असतत स्थान का दौरा करेगा। विकल्प क्या हैं?

1. इग्लू। 2-आयामी स्थान को लाइन द्वारा लाइन किया जाता है, जैसे चित्र ट्यूब में स्कैन। दो-आयामी अंतरिक्ष में समान रूप से वितरित बिंदु वस्तुओं के लिए और छोटे प्रश्नों के लिए, यह विधि आदर्श है। इसके नुकसान हैं:
   
   • प्रभावी रूप से 2-आयामी स्थान पर काम करता है, अन्यथा यह बहुत अधिक उप-क्षेत्र उत्पन्न करता है।
     
   • बड़े खोज विस्तार के लिए, बड़ी संख्या में उपश्रेणियाँ बनाता है।
     
   • क्लस्टरिंग प्रवण डेटा के लिए अक्षम
     
   
   
2. स्व-समान वक्र। व्यापक वक्र प्रकृति में भग्न है, इकाई सेल (उदाहरण के लिए, 2x2 वर्ग) को एक निश्चित तरीके से गिना जाता है, जिसके बाद प्रत्येक उप-सेल को एक समान तरीके से क्रमांकित किया जाता है। सबसे प्रसिद्ध ऐसे वक्र तथाकथित जेड-ऑर्डर (या बिट-इंटरलेविंग) हैं, जिनमें से प्रकृति नाम से है। 64x64 के रिज़ॉल्यूशन के साथ एक प्लेन की संख्या इस प्रकार है:
   
   तस्वीर में नीली आयत एक विशिष्ट खोज क्वेरी है, हर बार जब यह एक वक्र को पार करती है, तो एक नया उपकुंजी उत्पन्न होता है। वास्तव में, लापरवाह उपयोग के साथ, यह विधि इग्लू की तुलना में और भी अधिक उपश्रेणियां उत्पन्न करती है। यह इस तथ्य की व्याख्या करता है कि यह विधि व्यावहारिक रूप से डीबीएमएस में उपयोग नहीं की जाती है। हालांकि, समानता स्वयं इसे एक अद्भुत विशेषता के साथ संपन्न करती है - असमान रूप से वितरित डेटा के लिए अनुकूलन। इसके अलावा, वक्र के निरंतर खंड अंतरिक्ष के महत्वपूर्ण क्षेत्रों को कवर कर सकते हैं, जो उपयोगी है यदि आप इसका उपयोग कर सकते हैं।
   
3. एक अन्य विकल्प एक स्व-समान वक्र है: एक हिल्बर्ट यू-आकार का वक्र:
   
   
   जेड-ऑर्डर के विपरीत, इस वक्र में निरंतरता है, जो थोड़ी अधिक कुशलता से खोज करने की अनुमति देता है, एक महत्वपूर्ण नुकसान एक मूल्य से निर्देशांक की गणना की अपेक्षाकृत उच्च लागत है और इसके विपरीत।
   
   2X2 आत्म-समानता के साथ तीसरा विकल्प: एक्स-आकार का वक्र स्वयं को प्रतिच्छेद करता है और लेखक को स्थानिक अनुक्रमण के लिए इसके उपयोग की पूर्ववर्ती जानकारी नहीं है।
   
   मूर वक्र को भी जाना जाता है - हिल्बर्ट वक्र, सीरपिन्स्की वक्र, गोस्पर वक्र, का एक एनालॉग ...
   
4. हम तथाकथित का उपयोग करेंगे कैस्केड इग्लू:
   
   इस चित्र को प्राप्त करने के लिए, हमने निर्देशांक सीमा को 3 बिट्स और मिश्रित X & Y के टुकड़ों में विभाजित किया - अर्थात। व्यापक वक्र का मान इस प्रकार प्राप्त होता है:
   
   • बिट्स 0 से 3 बिट्स हैं 0 से 3 एक्स निर्देशांक
   • बिट्स 3 से 6 Y के 3 बिट्स हैं
   • बिट्स 6 से 9 बिट्स 3 से 6 एक्स निर्देशांक हैं
   • बिट्स 9 से 12 Y के 3 से 6 बिट्स होते हैं
   इस प्रकार, हम एक क्षैतिज स्कैन के साथ 8X8 ब्लॉक प्राप्त करते हैं, जो स्वयं के बीच एक क्षैतिज स्कैन बनाते हैं।
   लेकिन यह सिद्धांत को प्रदर्शित करना है। अनुक्रमण के लिए, हम 17 बिट्स के ब्लॉक बनाएंगे। यदि आप क्यों 17 में रुचि रखते हैं, तो उस पर और बाद में।
   

परिणाम

सूचकांक निर्माण

डेटासेट	डिस्क आकार (Kb)	समय का निर्माण	मेम आकार (एमबी)
55M	211.250	6'45 ''	40
526M	1,767,152	125 '	85
USNO-SA2.0	376.368	4'38 ''	40
USNO-A2.0	3,150,000	125 '	85

जहां:

• डिस्क का आकार - किलोबाइट में परिणामी सूचकांक फ़ाइल का आकार
• बिल्ड टाइम - मिनट / सेकंड में इसके निर्माण पर खर्च किया गया समय
• एमईएम आकार - एमबी में पीक का आकार इंडेक्स बिल्डर द्वारा आवश्यक है

सूचकांक खोज

निम्न तालिकाएँ निर्मित इंडेक्स पर क्वेरीज़ के लिए विशिष्ट मानों को सूचीबद्ध करती हैं। यादृच्छिक रूप से चयनित (निश्चित रूप से आबादी वाले क्षेत्र में) वर्ग के विस्तार के लिए 100,000 खोजों के कुल मूल्य दिए गए हैं।

• 55M
  

  अत्यधिक आकार	समय (सेकंड)	NObj	RDisk	isk (RDisk)
  2x2	58	23	118.435	0.39
  4x4	59	100	118.555	0.39
  10x10	59	600	118.918	0.4
  20x20	60	2622	119.221	0.4
  120x120	62	89.032	123.575	0.45
  1200x1200	98	8,850,098	174.846	0.82
  7200x7200	408	318,664,063	567.137	1.3

  जहां:
  
  • विस्तृत आकार - खोज सीमा का आकार, USNO-SA (X) .0 के मामले में इकाई 1 चाप दूसरा है
  • 100,000 अनुरोधों पर खर्च किए गए सेकंड में समय
  • एनओबीजे - सभी अनुरोधों द्वारा प्राप्त वस्तुओं की संख्या
  • RDisk - डिस्क रीड ऑपरेशंस की कुल संख्या (आंतरिक कैश से याद आती है), यह मान समय के बहुत अधिक संकेत है यहां तक ​​कि आकार में सैकड़ों मेगाबाइट की एक फ़ाइल प्रभावी रूप से ऑपरेटिंग सिस्टम द्वारा कैश की गई है
  • σ (RDisk) डिस्क परिचालनों की संख्या का मानक विचलन है, हम ध्यान दें कि प्रयोगों के परिणामों के अनुसार, RDisk का सबसे खराब मूल्य औसत से अधिक नहीं था (RDisk) + 12 *) (RDisk)
  
  
• 526M
  
  

  अत्यधिक आकार	समय (सेकंड)	NObj	RDisk
  2x2	738	110	185.672
  4x4	741	445	185.734
  10x10	730	2903	186.560
  20x20	774	11.615	187.190
  120x120	800	421.264	196.080
  1200x1200	1200	42,064,224	307.904
  7200x7200	3599	+१५१४४७१४८०	1,442,489

  जहां स्पीकर 55M के समान हैं।
  यह उल्लेखनीय है कि, जबकि डिस्क एक्सेस की संख्या नगण्य रूप से (एक तिहाई से) बदल गई है, क्वेरी निष्पादन समय 10 गुना से अधिक बढ़ गया है - ऑपरेटिंग सिस्टम द्वारा इंडेक्स फ़ाइल के कुशल कैशिंग की कमी का परिणाम है।
  
• USNO-SA2.0
  

  अत्यधिक आकार	समय (सेकंड)	NObj	RDisk	isk (RDisk)
  2x2	48	28	143.582	0.5
  4x4	50	115	143.887	0.5
  10x10	45	657	144.085	0.5
  20x20	45	2,585	144.748	0.51
  120x120	47	94.963	151.223	0.56
  1200x1200	80	9,506,746	224.016	0.97
  7200x7200	387	345,165,845	842.853	2.97

  जहां स्पीकर 55M के समान हैं
  
• USNO-A2.0 (ग्रेड)
  

  अत्यधिक आकार	समय (सेकंड)	NObj	RDisk	isk (RDisk)
  2x2	~ 600	~ 130	~ 200,200	~ 0.4
  4x4	~ 600	~ 500	~ 200,200	~ 0.4
  10x10	~ 600	~ 3,000	~ 200,200	~ 0.4
  20x20	~ 600	~ 12,000	~ 200,200	~ 0.4
  120x120	~ 600	~ 450,000	~ 250,200	~ 0.5
  1200x1200	~ 1,000	~ 45,000,000	~ 300,200	~ १.४
  7200x7200	~ 3500	~ 1,600,000,000	~ 1,500,200	~ २.०

  जहां स्पीकर 526M के समान हैं
  

स्थानिक जोइन

निम्न तालिकाएँ अनुक्रमणिका में शामिल होने के लिए विशिष्ट मानों को सूचीबद्ध करती हैं। जुड़ने से हमारा तात्पर्य एक निश्चित सीमा के भीतर स्थित सभी वस्तुओं की खोज से है। उदाहरण के लिए, यदि क्वेरी पैरामीटर 0.25 चाप दूसरा है, तो एक सूचकांक से प्रत्येक तत्व के लिए, दूसरे सूचकांक में सीमा + - 0.25, अर्थात् के साथ एक खोज की जाएगी। संदर्भ बिंदु पर पक्षों 0.5x0.5 चाप दूसरा और केंद्र के साथ एक वर्ग।

• USNO-SA2.0 बनाम USNO-SA2.0
  

  अत्यधिक आकार	समय (सेकंड)	NObj
  0.5x0.5	175	2
  2x2	191	410
  6x6	212	4412

  जहां:
  
  • एक्सटेंट साइज - आर्क सेकंड में खोज सीमा
  • समय (सेकंड) - सेकंड में क्वेरी निष्पादन का समय
  • एनओबीजे - पाया वस्तुओं की संख्या (खुद सहित नहीं), इस मामले में यह आधे से विभाजित करना आवश्यक है यह ऑटो-जॉइन है
  
  
• 55M बनाम USNO-SA2.0
  

  अत्यधिक आकार	समय (सेकंड)	NObj
  0.5x0.5	150	925
  2x2	165	13.815
  6x6	181	122.295

  जहां कॉलम USNO-SA2.0 बनाम USNO-SA2.0 के समान हैं।
  
• 526M बनाम 526M
  

  अत्यधिक आकार	समय (सेकंड)	NObj
  0.5x0.5	1601	0
  2x2	1813	916
  6x6	2180	9943

  जहां कॉलम USNO-SA2.0 बनाम USNO-SA2.0 के समान हैं।
  

यह कैसे और क्यों काम करता है?

शुरू करने के लिए, हम महत्वपूर्ण बिंदुओं पर ध्यान दें:

1. बड़ी फ़ाइलों के लिए, डिस्क कैशिंग काम नहीं करता है, आपको इस पर भरोसा नहीं करना चाहिए।
2. अनुरोध प्रसंस्करण समय में मुख्य रूप से डिस्क रीड समय होते हैं, बाकी सब कुछ अपेक्षाकृत छोटा होता है।
3. बेतरतीब ढंग से वितरित प्रश्नों के लिए, कोई कैशिंग काम नहीं करता है, यदि इंडेक्स को बी-ट्री के रूप में व्यवस्थित किया जाता है, तो आपको पेज कैश पर भरोसा नहीं करना चाहिए और उस पर अत्यधिक मेमोरी बर्बाद नहीं करनी चाहिए।
4. स्थानिक रूप से करीबी प्रश्नों के लिए, एक छोटा (कई दसियों पृष्ठ) कैश पर्याप्त है।

तो, आइए समझने की कोशिश करें कि डेटा की व्यवस्था कैसे की जाती है।

• वैश्विक सीमा - 2 ** 26 X 2 ** 27 या 180X360 डिग्री।
• 180 डिग्री 180 * 60 * 60 = 648000 चाप सेकंड है।
• 1 << 26 = 67 108 864. इसलिए, एक कोणीय दूसरा ~ 100 नमूने हैं।
• एक वस्तु का औसत 1600 = (2 * 648000 * 648000/500000000) वर्ग चाप सेकंड ~ (40,00040) है।
• या 40 * 100 = 4000 नमूने।
• ~ 1000 वस्तुओं को बी-ट्री पृष्ठ पर रखा गया है।
• अगर हम कैस्केड इग्लू ब्लॉक के साथ पेड़ के पृष्ठ को बनाना चाहते हैं, तो हम इस ब्लॉक को 4000 * sqrt (1000) => ~ 1 << 17 आकार में बनाएंगे
• वह जादू नंबर 17 है।
• तो, औसत पृष्ठ पर एक सीमा (40 * 32) ~ 1200X1200 चाप सेकंड है।
• आंकड़ों में, इस तरह के पृष्ठ को कैस्केड इग्लू के दो आसन्न ब्लॉकों पर शारीरिक रूप से स्थित होने की संभावना है
• इसलिए, आकार में 600X600 कोणीय सेकंड तक के खोज प्रश्नों को शीट पेज के केवल एक पढ़ने की आवश्यकता होती है।
• यह देखते हुए कि 4-स्तरीय इंडेक्स ट्री और ऊपरी दो स्तरों को प्रभावी ढंग से कैश किया गया है, इस आकार के एक औसत क्वेरी के लिए डिस्क से दो भौतिक रीड की आवश्यकता होती है।
• जिसे समझाना आवश्यक था।

तो कैसे खोज सभी एक ही है?

1. हमने ब्लॉक इंडेक्स डिवाइस के अनुसार खोज की सीमा को टुकड़ों में काट दिया।
2. हद का प्रत्येक टुकड़ा एक इंडेक्स ब्लॉक से मेल खाता है और स्वतंत्र रूप से संसाधित होता है।
3. ब्लॉक के अंदर हम खोज रेंज की सीमाएँ पाते हैं
4. हम पूरी सीमा को घटाते हैं, खोज सीमा के बाहर गिरने वाली हर चीज को छानते हैं।

थोड़ा निराशाजनक भी, कितना सरल है।

परिणाम

1. यहां तक ​​कि सबसे बड़ी विशेषता जिसे हम जानते हैं (~ 3,000,000,000) घंटे में अनुक्रमित किया जा सकता है।
2. इस तरह के सूचकांक को स्टोर करने के लिए आवश्यक डिस्क मेमोरी की मात्रा दसियों (~ 30) गीगाबाइट में मापी जाती है और वस्तुओं की संख्या में लगभग रैखिक होती है
3. खोज के लिए आवश्यक RAM की मात्रा बहुत कम है (एमबी यूनिट्स), इंडेक्स का उपयोग किया जा सकता है, जिसमें एम्बेडेड सिस्टम भी शामिल है
4. छोटी सीमा तक स्थानिक खोज के लिए (जिसका आकार वस्तुओं के बीच औसत दूरी के बराबर है), इस मामले में खोज समय 2-3 डिस्क संचालन के समय तक पहुंचता है, अर्थात। लगभग शारीरिक सीमा तक
5. अपेक्षाकृत बड़े प्रश्नों के लिए, खोज समय चयन में वस्तुओं की संख्या पर अधिक निर्भर है
6. किसी भी स्थिति में, समय पूर्वानुमेय रहता है, जो इस सूचकांक के उपयोग की अनुमति देता है, जिसमें वास्तविक समय प्रणाली भी शामिल है।

पुनश्च

वर्णित कार्य 2004 में अलेक्जेंडर अर्टुशिन के साथ उल्लेखनीय कंपनी डाटाएस्ट के सहयोग से किया गया था। उस समय, लेखक खुद इस कंपनी के कर्मचारी थे और हां, एवगेनी मोइसेव एमोइसेव के लिए उनकी सहमति से प्रकाशन किया जाता है।
उन दिनों में लोहे वर्तमान के लिए एक मैच नहीं था, लेकिन मूल बिंदु नहीं बदले हैं।