Partitionering är ett viktigt steg i flera databasalgoritmer, inklusive sortering, aggregering, och ansluter. Partitionering är också grundläggande för att dela upp arbetet i lika stora (eller balanserade) parallella deluppgifter. I detta dokument strävar vi efter att hitta, materialisera och underhålla en uppsättning partitionerande element (splitters) för en datauppsättning. Till skillnad från traditionella partitionering element, våra splitters definierar både ojämlikhet och jämlikhet partitioner, vilket gör att vi kan binda storleken på ojämlikhet partitioner. Vi tillhandahåller en algoritm för att bestämma en optimal uppsättning splitters från en sorterad datamängd och visa att det har tids komplexitet O(k lg 2 N ), där k är antalet splitters begärt och N är storleken på datamängden. Vi visar hur algoritmen kan utökas till par av tabeller, så att går kan delas upp i arbetsenheter som har balanserade kostnader. Vi demonstrerar experimentellt (a) att hitta den optimala uppsättningen splitters kan göras effektivt, och (b) att använda precomputed splitters kan förbättra tiden att sortera en data som är inställd på upp till 76%, med särskilda fördelar i närvaro av några tunga hitters.
Ross och Cieslewicz studerade problemet med att hitta optimala splitters för en uppsättning av en dimensionella punkter REF.
Optimal splitters for database partitioning with size bounds
{'venue': "ICDT '09", 'journal': None, 'mag_field_of_study': ['Computer Science']}