MCPcopy Create free account
hub / github.com/alibaba/zvec / inter_insert

Method inter_insert

src/core/algorithm/diskann/diskann_algorithm.cc:92–162  ·  view source on GitHub ↗

Source from the content-addressed store, hash-verified

90}
91
92int DiskAnnAlgorithm::inter_insert(diskann_id_t id,
93 std::vector<diskann_id_t> &pruned_list,
94 DiskAnnContext *ctx) {
95 DistCalculator &dc = ctx->dist_calculator();
96
97 for (auto &des : pruned_list) {
98 std::vector<diskann_id_t> new_neighbors;
99 bool need_prune = false;
100
101 {
102 auto lock = lock_for(des);
103
104 auto neighbors = entity_.get_neighbors(des);
105
106 bool found = false;
107 for (size_t i = 0; i < neighbors.first; ++i) {
108 if ((neighbors.second)[i] == id) {
109 found = true;
110 break;
111 }
112 }
113
114 if (!found) {
115 if (neighbors.first <
116 static_cast<uint64_t>(DiskAnnEntity::kDefaultGraphSlackFactor *
117 max_degree_)) {
118 int ret = entity_.add_neighbor(des, id);
119 if (ret != 0) return ret;
120 need_prune = false;
121 } else {
122 new_neighbors.resize(neighbors.first + 1);
123 memcpy(&new_neighbors[0], neighbors.second,
124 sizeof(diskann_id_t) * neighbors.first);
125
126 new_neighbors[neighbors.first] = id;
127
128 need_prune = true;
129 }
130 }
131 }
132
133 if (need_prune) {
134 std::set<diskann_id_t> new_visited;
135 std::vector<Neighbor> new_pool(0);
136
137 size_t reserve_size = static_cast<size_t>(std::ceil(
138 1.05 * DiskAnnEntity::kDefaultGraphSlackFactor * max_degree_));
139
140 new_pool.reserve(reserve_size);
141
142 for (auto node_id : new_neighbors) {
143 if (new_visited.find(node_id) == new_visited.end() && node_id != des) {
144 float dist = dc.dist(des, node_id);
145 new_pool.emplace_back(Neighbor(node_id, dist));
146 new_visited.insert(node_id);
147 }
148 }
149

Callers

nothing calls this directly

Calls 10

NeighborClass · 0.70
get_neighborsMethod · 0.45
add_neighborMethod · 0.45
resizeMethod · 0.45
reserveMethod · 0.45
findMethod · 0.45
endMethod · 0.45
distMethod · 0.45
insertMethod · 0.45
set_neighborsMethod · 0.45

Tested by

no test coverage detected