SPRQ-træ i distribueret DOPRI system
Forfatter
Algreen, Kim
Semester
4. semester
Uddannelse
Udgivelsesår
2005
Abstract
Rapporten beskriver udviklingen af en type distribueret lokationsbaseret service, kaldet et DOPRI-system, og en hurtig datastruktur i arbejdshukommelsen (main memory). Datastrukturen bygger på PR-Quadtræet og kaldes et SPRQ-træ; den bruges til at indeksere todimensionelle objekter (så de kan findes og opdateres hurtigt). Vi undersøger både forskellige positionsbestemmelsesteknikker og den programmeringsteknologi, der egner sig til at opbygge et distribueret DOPRI-system. Systemet skal kunne betjene mange brugere, opdatere deres positioner hyppigt, dække store områder og fungere både indendørs og udendørs. For at understøtte disse krav placeres datastrukturen i arbejdshukommelsen, fordi operationer i hukommelsen er væsentligt hurtigere end diskoperationer. Rapporten vurderer også, om det er praktisk og muligt at have både datastrukturen og dele af systemets øvrige information i arbejdshukommelsen i stedet for på disk.
The report describes the development of a type of distributed location-based service, called a DOPRI system, and a fast in-memory (main-memory) data structure. The data structure is based on the PR Quadtree and is called the SPRQ tree; it indexes two-dimensional objects (so they can be found and updated quickly). We examine both different positioning techniques and the programming technologies suitable for building a distributed DOPRI system. The system must serve many users, update their positions frequently, cover large areas, and work both indoors and outdoors. To meet these requirements, the data structure is kept in main memory because memory operations are much faster than disk operations. The report also investigates whether it is practical and feasible to keep both the data structure and parts of the system’s information in main memory rather than on disk.
[Dette resumé er genereret ved hjælp af AI]