Ett geometriskt mönster är en uppsättning punkter med alla parvisa avstånd (eller, mer allmänt, relativa avstånd) angivna. Att hitta matchningar till sådana mönster har tillämpningar för rumsliga data i seismiska, astronomiska och transportsammanhang. Ett särskilt intressant geometriskt mönster i astronomi är Einsteinkorset, som är ett astronomiskt fenomen där en enda kvasar observeras som fyra olika himmelsobjekt (på grund av gravitationslinsering) när den fångas av jordteleskop. Att hitta sådana kors, liksom andra geometriska mönster, är ett utmanande problem eftersom det potentiella antalet grupper av element som komponerar former är exponentiellt stor i storleken på datasetet och mönstret. I det här dokumentet betecknar vi geometriska mönster som konstellationsförfrågningar och föreslår algoritmer för att hitta dem i stora dataapplikationer. Våra metoder kombinerar quadtrees, matris multiplikation, och unindexed gå bearbetning för att upptäcka uppsättningar av punkter som matchar ett geometriskt mönster inom vissa additiv faktor på pairwise avstånd. Våra distribuerade experiment visar att valet av kompositionsalgoritm (matrisförökning eller inhägnade slingor) beror på den frihet som införs i frågegeometrin genom distansadditivfaktorn. Tre tydligt identifierade block av tröskelvärden styr valet av den bästa sammansättningsalgoritmen. Slutligen, att lösa problemet för relativa avstånd kräver en ny kontinuerlig-till-diskrete omvandling. Såvitt vi vet är denna uppsats den första som undersöker stjärnbildsfrågor i stor skala.
Constellation frågor REF är en klass av paket frågor, där en geometrisk form definierar de globala begränsningarna.
Constellation Queries over Big Data
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science']}