44 : m_id(id), m_region(r), m_pData(nullptr), m_dataLength(len)
103 ptr +=
sizeof(uint32_t);
119 uint8_t* regiondata =
nullptr;
124 *data =
new uint8_t[len];
125 uint8_t* ptr = *data;
130 ptr +=
sizeof(uint32_t);
138 memcpy(ptr, regiondata, regionsize);
152 uint32_t indexCapacity,
153 uint32_t leafCapacity,
195 uint32_t indexCapacity,
196 uint32_t leafCapacity,
203 uint32_t bindex =
static_cast<uint32_t
>(std::floor(static_cast<double>(indexCapacity * fillFactor)));
204 uint32_t bleaf =
static_cast<uint32_t
>(std::floor(static_cast<double>(leafCapacity * fillFactor)));
211 bl.
bulkLoadUsingSTR(static_cast<RTree*>(tree), stream, bindex, bleaf, 10000, 100);
230 double fillFactor(0.0);
231 uint32_t indexCapacity(0);
232 uint32_t leafCapacity(0);
233 uint32_t dimension(0);
234 uint32_t pageSize(0);
235 uint32_t numberOfPages(0);
264 throw Tools::IllegalArgumentException(
"createAndBulkLoadNewRTree: Property FillFactor must be in range (0.0, 0.5) for LINEAR or QUADRATIC index types");
303 var = ps.
getProperty(
"ExternalSortBufferPageSize");
315 var = ps.
getProperty(
"ExternalSortBufferTotalPages");
328 uint32_t bindex =
static_cast<uint32_t
>(std::floor(static_cast<double>(indexCapacity * fillFactor)));
329 uint32_t bleaf =
static_cast<uint32_t
>(std::floor(static_cast<double>(leafCapacity * fillFactor)));
336 bl.
bulkLoadUsingSTR(static_cast<RTree*>(tree), stream, bindex, bleaf, pageSize, numberOfPages);
359 m_pStorageManager(&sm),
360 m_rootID(StorageManager::
NewPage),
361 m_headerID(StorageManager::
NewPage),
364 m_indexCapacity(100),
366 m_nearMinimumOverlapFactor(32),
367 m_splitDistributionFactor(0.4),
368 m_reinsertFactor(0.3),
412 uint8_t* buffer =
nullptr;
416 buffer =
new uint8_t[len];
417 memcpy(buffer, pData, len);
420 insertData_impl(len, buffer, *mbr,
id);
430 bool ret = deleteData_impl(*mbr,
id);
440 #ifdef HAVE_PTHREAD_H 441 Tools::LockGuard lock(&m_lock);
446 std::stack<NodePtr> st;
447 NodePtr root = readNode(m_rootID);
452 NodePtr n = st.top(); st.pop();
457 visitSubTree(n, vId);
459 uint64_t *obj =
new uint64_t[nObj];
462 Data data =
Data((uint32_t)(
sizeof(uint64_t) * nObj), (uint8_t *) obj, n->m_nodeMBR, n->
getIdentifier());
464 ++(m_stats.m_u64QueryResults);
470 for (uint32_t cChild = 0; cChild < n->m_children; ++cChild)
476 ++(m_stats.m_u64QueryResults);
484 for (uint32_t cChild = 0; cChild < n->m_children; ++cChild)
486 st.push(readNode(n->m_pIdentifier[cChild]));
506 std::stack<NodePtr> st;
507 NodePtr root = readNode(m_rootID);
512 NodePtr n = st.top(); st.pop();
518 for (uint32_t cChild = 0; cChild < n->m_children; ++cChild)
522 Data data =
Data(n->m_pDataLength[cChild], n->m_pData[cChild], *(n->m_ptrMBR[cChild]), n->m_pIdentifier[cChild]);
524 ++(m_stats.m_u64QueryResults);
538 for (uint32_t cChild = 0; cChild < n->m_children; ++cChild)
540 st.push(readNode(n->m_pIdentifier[cChild]));
569 auto ascending = [](
const NNEntry* lhs,
const NNEntry* rhs) {
return lhs->m_minDist > rhs->m_minDist; };
570 std::priority_queue<NNEntry*, std::vector<NNEntry*>, decltype(ascending)> queue(ascending);
572 queue.push(
new NNEntry(m_rootID,
nullptr, 0.0));
575 double knearest = 0.0;
577 while (! queue.empty())
579 NNEntry* pFirst = queue.top();
583 if (count >= k && pFirst->m_minDist > knearest)
break;
587 if (pFirst->m_pEntry ==
nullptr)
590 NodePtr n = readNode(pFirst->m_id);
593 for (uint32_t cChild = 0; cChild < n->m_children; ++cChild)
597 Data* e =
new Data(n->m_pDataLength[cChild], n->m_pData[cChild], *(n->m_ptrMBR[cChild]), n->m_pIdentifier[cChild]);
600 queue.push(
new NNEntry(n->m_pIdentifier[cChild], e, nnc.
getMinimumDistance(query, *e)));
604 queue.push(
new NNEntry(n->m_pIdentifier[cChild],
nullptr, nnc.
getMinimumDistance(query, *(n->m_ptrMBR[cChild]))));
610 v.
visitData(*(static_cast<IData*>(pFirst->m_pEntry)));
611 ++(m_stats.m_u64QueryResults);
613 knearest = pFirst->m_minDist;
614 delete pFirst->m_pEntry;
620 while (! queue.empty())
622 NNEntry* e = queue.top(); queue.pop();
623 if (e->m_pEntry !=
nullptr)
delete e->m_pEntry;
738 m_readNodeCommands.push_back(std::shared_ptr<ICommand>(pCommand));
741 m_writeNodeCommands.push_back(std::shared_ptr<ICommand>(pCommand));
744 m_deleteNodeCommands.push_back(std::shared_ptr<ICommand>(pCommand));
752 std::stack<ValidateEntry> st;
753 NodePtr root = readNode(m_rootID);
755 if (root->m_level != m_stats.m_u32TreeHeight - 1)
757 std::cerr <<
"Invalid tree height." << std::endl;
761 std::map<uint32_t, uint32_t> nodesInLevel;
762 nodesInLevel.insert(std::pair<uint32_t, uint32_t>(root->m_level, 1));
764 ValidateEntry e(root->m_nodeMBR, root);
769 e = st.top(); st.pop();
772 tmpRegion = m_infiniteRegion;
774 for (uint32_t cDim = 0; cDim < tmpRegion.
m_dimension; ++cDim)
776 tmpRegion.
m_pLow[cDim] = std::numeric_limits<double>::max();
777 tmpRegion.
m_pHigh[cDim] = -std::numeric_limits<double>::max();
779 for (uint32_t cChild = 0; cChild < e.m_pNode->m_children; ++cChild)
781 tmpRegion.
m_pLow[cDim] = std::min(tmpRegion.
m_pLow[cDim], e.m_pNode->m_ptrMBR[cChild]->m_pLow[cDim]);
782 tmpRegion.
m_pHigh[cDim] = std::max(tmpRegion.
m_pHigh[cDim], e.m_pNode->m_ptrMBR[cChild]->m_pHigh[cDim]);
786 if (! (tmpRegion == e.m_pNode->m_nodeMBR))
788 std::cerr <<
"Invalid parent information." << std::endl;
791 else if (! (tmpRegion == e.m_parentMBR))
793 std::cerr <<
"Error in parent." << std::endl;
797 if (e.m_pNode->m_level != 0)
799 for (uint32_t cChild = 0; cChild < e.m_pNode->m_children; ++cChild)
801 NodePtr ptrN = readNode(e.m_pNode->m_pIdentifier[cChild]);
802 ValidateEntry tmpEntry(*(e.m_pNode->m_ptrMBR[cChild]), ptrN);
804 std::map<uint32_t, uint32_t>::iterator itNodes = nodesInLevel.find(tmpEntry.m_pNode->m_level);
806 if (itNodes == nodesInLevel.end())
808 nodesInLevel.insert(std::pair<uint32_t, uint32_t>(tmpEntry.m_pNode->m_level, 1l));
812 nodesInLevel[tmpEntry.m_pNode->m_level] = nodesInLevel[tmpEntry.m_pNode->m_level] + 1;
821 for (uint32_t cLevel = 0; cLevel < m_stats.m_u32TreeHeight; ++cLevel)
823 if (nodesInLevel[cLevel] != m_stats.m_nodesInLevel[cLevel])
825 std::cerr <<
"Invalid nodesInLevel information." << std::endl;
829 nodes += m_stats.m_nodesInLevel[cLevel];
832 if (nodes != m_stats.m_u32Nodes)
834 std::cerr <<
"Invalid number of nodes information." << std::endl;
883 "(0.0, 0.5) for LINEAR or QUADRATIC index types");
886 "(0.0, 1.0) for RSTAR index type");
919 throw Tools::IllegalArgumentException(
"initNew: Property NearMinimumOverlapFactor must be Tools::VT_ULONG and less than both index and leaf capacities");
1014 m_stats.m_u32TreeHeight = 1;
1015 m_stats.m_nodesInLevel.push_back(0);
1017 Leaf root(
this, -1);
1018 m_rootID = writeNode(&root);
1055 throw Tools::IllegalArgumentException(
"initOld: Property NearMinimumOverlapFactor must be Tools::VT_ULONG and less than both index and leaf capacities");
1057 m_nearMinimumOverlapFactor = var.
m_val.
ulVal;
1128 void SpatialIndex::RTree::RTree::storeHeader()
1130 const uint32_t headerSize =
1144 m_stats.m_u32TreeHeight *
sizeof(uint32_t);
1146 uint8_t* header =
new uint8_t[headerSize];
1147 uint8_t* ptr = header;
1149 memcpy(ptr, &m_rootID,
sizeof(
id_type));
1153 memcpy(ptr, &m_fillFactor,
sizeof(
double));
1154 ptr +=
sizeof(double);
1155 memcpy(ptr, &m_indexCapacity,
sizeof(uint32_t));
1156 ptr +=
sizeof(uint32_t);
1157 memcpy(ptr, &m_leafCapacity,
sizeof(uint32_t));
1158 ptr +=
sizeof(uint32_t);
1159 memcpy(ptr, &m_nearMinimumOverlapFactor,
sizeof(uint32_t));
1160 ptr +=
sizeof(uint32_t);
1161 memcpy(ptr, &m_splitDistributionFactor,
sizeof(
double));
1162 ptr +=
sizeof(double);
1163 memcpy(ptr, &m_reinsertFactor,
sizeof(
double));
1164 ptr +=
sizeof(double);
1165 memcpy(ptr, &m_dimension,
sizeof(uint32_t));
1166 ptr +=
sizeof(uint32_t);
1167 char c = (char) m_bTightMBRs;
1168 memcpy(ptr, &c,
sizeof(
char));
1169 ptr +=
sizeof(char);
1170 memcpy(ptr, &(m_stats.m_u32Nodes),
sizeof(uint32_t));
1171 ptr +=
sizeof(uint32_t);
1172 memcpy(ptr, &(m_stats.m_u64Data),
sizeof(uint64_t));
1173 ptr +=
sizeof(uint64_t);
1174 memcpy(ptr, &(m_stats.m_u32TreeHeight),
sizeof(uint32_t));
1175 ptr +=
sizeof(uint32_t);
1177 for (uint32_t cLevel = 0; cLevel < m_stats.m_u32TreeHeight; ++cLevel)
1179 memcpy(ptr, &(m_stats.m_nodesInLevel[cLevel]),
sizeof(uint32_t));
1180 ptr +=
sizeof(uint32_t);
1183 m_pStorageManager->
storeByteArray(m_headerID, headerSize, header);
1188 void SpatialIndex::RTree::RTree::loadHeader()
1190 uint32_t headerSize;
1191 uint8_t* header =
nullptr;
1192 m_pStorageManager->
loadByteArray(m_headerID, headerSize, &header);
1194 uint8_t* ptr = header;
1196 memcpy(&m_rootID, ptr,
sizeof(
id_type));
1200 memcpy(&m_fillFactor, ptr,
sizeof(
double));
1201 ptr +=
sizeof(double);
1202 memcpy(&m_indexCapacity, ptr,
sizeof(uint32_t));
1203 ptr +=
sizeof(uint32_t);
1204 memcpy(&m_leafCapacity, ptr,
sizeof(uint32_t));
1205 ptr +=
sizeof(uint32_t);
1206 memcpy(&m_nearMinimumOverlapFactor, ptr,
sizeof(uint32_t));
1207 ptr +=
sizeof(uint32_t);
1208 memcpy(&m_splitDistributionFactor, ptr,
sizeof(
double));
1209 ptr +=
sizeof(double);
1210 memcpy(&m_reinsertFactor, ptr,
sizeof(
double));
1211 ptr +=
sizeof(double);
1212 memcpy(&m_dimension, ptr,
sizeof(uint32_t));
1213 ptr +=
sizeof(uint32_t);
1215 memcpy(&c, ptr,
sizeof(
char));
1216 m_bTightMBRs = (c != 0);
1217 ptr +=
sizeof(char);
1218 memcpy(&(m_stats.m_u32Nodes), ptr,
sizeof(uint32_t));
1219 ptr +=
sizeof(uint32_t);
1220 memcpy(&(m_stats.m_u64Data), ptr,
sizeof(uint64_t));
1221 ptr +=
sizeof(uint64_t);
1222 memcpy(&(m_stats.m_u32TreeHeight), ptr,
sizeof(uint32_t));
1223 ptr +=
sizeof(uint32_t);
1225 for (uint32_t cLevel = 0; cLevel < m_stats.m_u32TreeHeight; ++cLevel)
1228 memcpy(&cNodes, ptr,
sizeof(uint32_t));
1229 ptr +=
sizeof(uint32_t);
1230 m_stats.m_nodesInLevel.push_back(cNodes);
1236 void SpatialIndex::RTree::RTree::insertData_impl(uint32_t dataLength, uint8_t* pData,
Region& mbr,
id_type id)
1240 std::stack<id_type> pathBuffer;
1241 uint8_t* overflowTable =
nullptr;
1245 NodePtr root = readNode(m_rootID);
1247 overflowTable =
new uint8_t[root->m_level];
1248 memset(overflowTable, 0, root->m_level);
1250 NodePtr l = root->chooseSubtree(mbr, 0, pathBuffer);
1251 if (l.
get() == root.
get())
1256 l->insertData(dataLength, pData, mbr,
id, pathBuffer, overflowTable);
1258 delete[] overflowTable;
1259 ++(m_stats.m_u64Data);
1263 delete[] overflowTable;
1268 void SpatialIndex::RTree::RTree::insertData_impl(uint32_t dataLength, uint8_t* pData,
Region& mbr,
id_type id, uint32_t level, uint8_t* overflowTable)
1272 std::stack<id_type> pathBuffer;
1273 NodePtr root = readNode(m_rootID);
1274 NodePtr n = root->chooseSubtree(mbr, level, pathBuffer);
1276 assert(n->m_level == level);
1278 if (n.
get() == root.
get())
1283 n->insertData(dataLength, pData, mbr,
id, pathBuffer, overflowTable);
1286 bool SpatialIndex::RTree::RTree::deleteData_impl(
const Region& mbr,
id_type id)
1290 std::stack<id_type> pathBuffer;
1291 NodePtr root = readNode(m_rootID);
1292 NodePtr l = root->findLeaf(mbr,
id, pathBuffer);
1293 if (l.
get() == root.
get())
1299 if (l.
get() !=
nullptr)
1303 --(m_stats.m_u64Data);
1313 uint32_t dataLength;
1318 else page = n->m_identifier;
1328 std::cerr << e.
what() << std::endl;
1332 if (n->m_identifier < 0)
1334 n->m_identifier = page;
1335 ++(m_stats.m_u32Nodes);
1340 m_stats.m_nodesInLevel[n->m_level] = m_stats.m_nodesInLevel.at(n->m_level) + 1;
1347 m_stats.m_nodesInLevel[n->m_level] = m_stats.m_nodesInLevel[n->m_level] + 1;
1351 ++(m_stats.m_u64Writes);
1353 for (
size_t cIndex = 0; cIndex < m_writeNodeCommands.size(); ++cIndex)
1355 m_writeNodeCommands[cIndex]->execute(*n);
1363 uint32_t dataLength;
1368 m_pStorageManager->
loadByteArray(page, dataLength, &buffer);
1372 std::cerr << e.
what() << std::endl;
1379 memcpy(&nodeType, buffer,
sizeof(uint32_t));
1387 if (n.
get() ==
nullptr)
1394 n->m_identifier = page;
1397 ++(m_stats.m_u64Reads);
1399 for (
size_t cIndex = 0; cIndex < m_readNodeCommands.size(); ++cIndex)
1401 m_readNodeCommands[cIndex]->execute(*n);
1414 void SpatialIndex::RTree::RTree::deleteNode(
Node* n)
1422 std::cerr << e.
what() << std::endl;
1426 --(m_stats.m_u32Nodes);
1427 m_stats.m_nodesInLevel[n->m_level] = m_stats.m_nodesInLevel[n->m_level] - 1;
1429 for (
size_t cIndex = 0; cIndex < m_deleteNodeCommands.size(); ++cIndex)
1431 m_deleteNodeCommands[cIndex]->execute(*n);
1437 std::stack<NodePtr> st;
1438 NodePtr root = readNode(m_rootID);
1440 if (root->m_children > 0 && query.
intersectsShape(root->m_nodeMBR)) st.push(root);
1442 while (! st.empty())
1444 NodePtr n = st.top(); st.pop();
1446 if (n->m_level == 0)
1450 for (uint32_t cChild = 0; cChild < n->m_children; ++cChild)
1458 Data data =
Data(n->m_pDataLength[cChild], n->m_pData[cChild], *(n->m_ptrMBR[cChild]), n->m_pIdentifier[cChild]);
1460 ++(m_stats.m_u64QueryResults);
1468 for (uint32_t cChild = 0; cChild < n->m_children; ++cChild)
1470 if (query.
intersectsShape(*(n->m_ptrMBR[cChild]))) st.push(readNode(n->m_pIdentifier[cChild]));
1483 for (uint32_t cChild1 = 0; cChild1 < n1->m_children; ++cChild1)
1487 for (uint32_t cChild2 = 0; cChild2 < n2->m_children; ++cChild2)
1493 if (n1->m_level == 0)
1495 if (n1->m_pIdentifier[cChild1] != n2->m_pIdentifier[cChild2])
1497 assert(n2->m_level == 0);
1499 std::vector<const IData*> v;
1500 Data e1(n1->m_pDataLength[cChild1], n1->m_pData[cChild1], *(n1->m_ptrMBR[cChild1]), n1->m_pIdentifier[cChild1]);
1501 Data e2(n2->m_pDataLength[cChild2], n2->m_pData[cChild2], *(n2->m_ptrMBR[cChild2]), n2->m_pIdentifier[cChild2]);
1510 selfJoinQuery(n1->m_pIdentifier[cChild1], n2->m_pIdentifier[cChild2], rr, vis);
1518 void SpatialIndex::RTree::RTree::visitSubTree(
NodePtr subTree,
IVisitor& v)
1520 std::stack<NodePtr> st;
1523 while (! st.empty())
1525 NodePtr n = st.top(); st.pop();
1530 for (uint32_t cChild = 0; cChild < n->m_children; ++cChild)
1532 Data data =
Data(n->m_pDataLength[cChild], n->m_pData[cChild], *(n->m_ptrMBR[cChild]), n->m_pIdentifier[cChild]);
1534 ++(m_stats.m_u64QueryResults);
1539 for (uint32_t cChild = 0; cChild < n->m_children; ++cChild)
1541 st.push(readNode(n->m_pIdentifier[cChild]));
1549 os <<
"Dimension: " << t.m_dimension << std::endl
1550 <<
"Fill factor: " << t.m_fillFactor << std::endl
1551 <<
"Index capacity: " << t.m_indexCapacity << std::endl
1552 <<
"Leaf capacity: " << t.m_leafCapacity << std::endl
1553 <<
"Tight MBRs: " << ((t.m_bTightMBRs) ?
"enabled" :
"disabled") << std::endl;
1557 os <<
"Near minimum overlap factor: " << t.m_nearMinimumOverlapFactor << std::endl
1558 <<
"Reinsert factor: " << t.m_reinsertFactor << std::endl
1559 <<
"Split distribution factor: " << t.m_splitDistributionFactor << std::endl;
1567 os <<
"Leaf pool hits: " << t.m_leafPool.
m_hits << std::endl
1568 <<
"Leaf pool misses: " << t.m_leafPool.
m_misses << std::endl
1569 <<
"Index pool hits: " << t.m_indexPool.
m_hits << std::endl
1570 <<
"Index pool misses: " << t.m_indexPool.
m_misses << std::endl
1571 <<
"Region pool hits: " << t.m_regionPool.
m_hits << std::endl
1572 <<
"Region pool misses: " << t.m_regionPool.
m_misses << std::endl
1573 <<
"Point pool hits: " << t.m_pointPool.m_hits << std::endl
1574 <<
"Point pool misses: " << t.m_pointPool.m_misses << std::endl;
std::vector< uint64_t > & GetResults()
virtual void deleteByteArray(const id_type id)=0
uint64_t GetResultCount() const
SIDX_DLL ISpatialIndex * loadRTree(IStorageManager &in, id_type indexIdentifier)
virtual void containsWhatQuery(const IShape &query, IVisitor &v)
void bulkLoadUsingSTR(RTree *pTree, IDataStream &stream, uint32_t bindex, uint32_t bleaf, uint32_t pageSize, uint32_t numberOfPages)
Data(uint32_t len, uint8_t *pData, Region &r, id_type id)
void storeToByteArray(uint8_t **data, uint32_t &len) override
virtual void intersectsWithQuery(const IShape &query, IVisitor &v)
virtual void insertData(uint32_t len, const uint8_t *pData, const IShape &shape, id_type shapeIdentifier)
virtual void getStatistics(IStatistics **out) const
uint64_t getNumberOfData() const override
virtual void addCommand(ICommand *pCommand, CommandType ct)
void loadFromByteArray(const uint8_t *data) override
uint32_t getByteArraySize() override
void getShape(IShape **out) const override
virtual void storeByteArray(id_type &id, const uint32_t len, const uint8_t *const data)=0
RTree(IStorageManager &, Tools::PropertySet &)
virtual void getIndexProperties(Tools::PropertySet &out) const
void getData(uint32_t &len, uint8_t **data) const override
virtual bool isIndexValid()
virtual void pointLocationQuery(const Point &query, IVisitor &v)
SIDX_DLL ISpatialIndex * returnRTree(IStorageManager &ind, Tools::PropertySet &in)
std::ostream & operator<<(std::ostream &os, const RTree &t)
virtual void queryStrategy(IQueryStrategy &qs)
virtual void loadByteArray(const id_type id, uint32_t &len, uint8_t **data)=0
virtual uint32_t getDimension() const =0
virtual bool intersectsRegion(const Region &in) const
SIDX_DLL ISpatialIndex * createAndBulkLoadNewRTree(BulkLoadMethod m, IDataStream &stream, IStorageManager &sm, double fillFactor, uint32_t indexCapacity, uint32_t leafCapacity, uint32_t dimension, RTreeVariant rv, id_type &indexIdentifier)
virtual void visitNode(const INode &in)=0
virtual void nearestNeighborQuery(uint32_t k, const IShape &query, IVisitor &v, INearestNeighborComparator &)
virtual bool intersectsShape(const IShape &in) const =0
virtual void internalNodesQuery(const IShape &query, IVisitor &v)
virtual uint32_t getNumberOfNodesInLevel(uint32_t l) const
virtual void visitData(const IData &in)=0
void storeToByteArray(uint8_t **data, uint32_t &length) override
virtual void makeInfinite(uint32_t dimension)
Tools::PoolPointer< Node > NodePtr
id_type getIdentifier() const override
uint32_t getDimension() const override
virtual double getMinimumDistance(const IShape &query, const IShape &entry)=0
virtual void selfJoinQuery(const IShape &s, IVisitor &v)
uint32_t getByteArraySize() override
void storeToByteArray(uint8_t **data, uint32_t &len) override
id_type getIdentifier() const override
virtual Region getIntersectingRegion(const Region &r) const
void loadFromByteArray(const uint8_t *data) override
virtual bool deleteData(const IShape &shape, id_type id)
virtual void getMBR(Region &out) const =0
SIDX_DLL ISpatialIndex * createNewRTree(IStorageManager &sm, double fillFactor, uint32_t indexCapacity, uint32_t leafCapacity, uint32_t dimension, RTreeVariant rv, id_type &indexIdentifier)
virtual void getNextEntry(const IEntry &previouslyFetched, id_type &nextEntryToFetch, bool &bFetchNextEntry)=0
virtual bool containsShape(const IShape &in) const =0
void loadFromByteArray(const uint8_t *data) override
std::string what() override
virtual void deleteData(const Region &mbr, id_type id, std::stack< id_type > &pathBuffer)