# Resource Indexing and Querying in Large Connected Environments
## 5 Proposed Approach
### Index Generation Algorithm
After creating a minimal cycle and if \(\beta\
eq 0\), we make a diagonal in the uncovered zones (lines 13-18). With the remaining rows, we index covered zones where the sum of indexes is the lowest. The purpose of doing this is to favor more covered zones over uncovered ones. Figure 4 illustrates in step 3 the result of this step. In our case, \(d3\) and \(d4\) will add z5 and z6, respectively. At this stage, we can access all the uncovered zones. Once this is done, we can start alternating between covered and uncovered zones. We add entries for zones having the lowest number of indexes per column. The last matrix of our example demonstrates this step. An index is added for the covered zone \(z4\) only, since all the other devices are saturated. \(\alpha\) is decremented at the end of this step. We also note that the same functions used above are repeated (lines 19-30) because \(\beta\) may become 0 before \(\alpha\). After the algorithm converges (line 31), we check that the indexes are distributed equally between zones and all devices have a number of entries for covered zones greater than uncovered zones'. If this is not the case, we remove entries from uncovered zones and add them to covered zones.In essence, because of variations in the capacities of different devices, certain columns may have more indexes than others. This results in the adjustment of indexes in specific rows, to achieve a more balanced distribution. These verifications are performed using the verify cycle function. In addition, a function called \(addGateways()\) adds the corresponding gateway for each device. After generating the matrix, the global index is ready to be cut by rows and distributed over the devices. In order to simplify the global index final representation, we did not include the cluster gateway inside the resulting global index (Figure 4 step 4). We note that, in cases where the number of devices is higher than the number of zones, the index will have more rows than columns, while having more zones than devices will lead to a number of columns greater than the number of rows(such as in our example). If the number of devices is equal to the number of zones, the rows and the columns will be equal. ### Local Index Generation

Once the previous algorithms have been applied, the global index is ready to be distributed over the cluster heads. It is divided by device as a vector of zones. Only completed entries in the initial \(gi\) (containing 1 value) are considered in the local index (i.e., all 0 values corresponding to columns are removed). In addition, the cell values are transformed as follows: (1) values \"*\" indicate local zones covered by the corresponding device, (2) zones marked with device identifiers indicate to whom queries must be forwarded, while (3) zones marked with \"\(\square\)\" indicate uncovered zones. Query execution simulations were implemented. As cited before, the difference in user needs implies implementing many query types. We will demonstrate the methodology of the execution of each type. In the following figures, straight arrows indicate the index chosen by the device, while dotted arrows show the device to which the message is forwarded. After arriving at the destination zone, the device will return the message using the path found (the path followed must be saved inside the message). The following query processing is performed on the local index of the cluster head and not on the global index (orchestrator). Many algorithms could be employed to return the response optimally (further studies could be made on these algorithms). When the message passes through all the devices inside a zone, we prevent the message from re-entering the zone, to avoid loops inside the index. * One-path Queries: Figure 5 illustrates an example of one-path queries taking a random path strategy. We consider that a query from the location \(z4\) to \(z5\) is sent. The device \(d4\) located in \(z4\) receives the query. \(d4\) does not know any information about \(z5\).