Detta dokument undersöker MaxRS problem i rumsliga databaser. Eftersom en uppsättning O viktade punkter och en rektangulär region r av en given storlek, målet med MaxRS problemet är att hitta en plats för r så att summan av vikterna av alla punkter som omfattas av r maximeras. Detta problem är användbart i många platsbaserade applikationer som att hitta den bästa platsen för en ny franchisebutik med ett begränsat leveranssortiment och hitta den mest attraktiva platsen för en turist med ett begränsat räckvidd. Problemet har dock främst studerats i teorin, särskilt i beräkningsgeometrin. De befintliga algoritmerna från beräkningsgeometrigemenskapen är in-minnesalgoritmer som inte garanterar skalbarheten. I detta dokument föreslår vi en skalbar extern-minnesalgoritm (ExactMaxRS ) för MaxRS-problemet, vilket är optimalt när det gäller I/O-komplexet. Dessutom föreslår vi en approximationsalgoritm (ApproxMaxCRS ) för MaxCRS-problemet som är en cirkelversion av MaxRS-problemet. Vi bevisar korrekthet och optimalitet av ExactMaxRS algoritm tillsammans med approximationen bunden av CaMaxCRS algoritm. Från omfattande experimentella resultat, visar vi att ExactMaxRS algoritm är två storleksordningar snabbare än metoder anpassade från befintliga algoritmer, och approximationen bunden i praktiken är mycket bättre än den teoretiska gränsen för CaMaxCRS algoritm.
Choi m.fl. REF föreslog en algoritm för att lösa MaxRS-problem vid externt minne med optimal I/O-kostnad.
A Scalable Algorithm for Maximizing Range Sum in Spatial Databases
{'venue': 'PVLDB', 'journal': 'PVLDB', 'mag_field_of_study': ['Computer Science']}