314:
97:
89:
22:
210:. If so and if it was not previously reported, then we report it. We can use the convention that we only report a candidate the first time we find it. This can be done easily by clipping the candidate against the query rectangle and comparing its lower-left corner against the current location. If it is a match then we report, otherwise we skip.
266:
Like a hash table, bin's efficiency depends a lot on the distribution of both location and size of candidates and queries. In general, the smaller the query rectangle, the more efficient the query. The bin's size should be such that it contains as few candidates as possible but large enough so that
330:
222:
In a multithread environment, insert, delete and query are mutually exclusive. However, instead of locking the whole data structure, a sub-range of bins may be locked. Detailed performance analysis should be done to justify the overhead.
218:
Insertion is linear to the number of bins a candidate intersects because inserting a candidate into 1 bin is constant time. Deletion is more expensive because we need to search the singly linked list of each bin the candidate intersects.
267:
candidates do not span too many bins. If a candidate span many bins, a query has to skip this candidate over and over again after it is reported at the first bin of intersection. For example, in the figure,
297:, the bin structure allows efficient insertion and deletion without the complexity of rebalancing. This can be very useful in algorithms that need to incrementally add shapes to the search data structure.
170:
rectangles to be queried. All the bins are arranged in a 2D array. All the candidates are represented also as 2D arrays. The size of a candidate's array is the number of bins it intersects.
198:, we can find out which bin its lower-left corner intersects efficiently by simply subtracting the bin's bounding box's lower-left corner from the lower-left corner of
40:
181:. If a candidate intersects a bin, it is chained to the bin's linked list. Each element in a candidate's array is a link node in the corresponding bin's linked list.
206:
intersects and examine all the candidates in the linked-lists of these bins. For each candidate we will check if it does indeed intersect
177:
has 6 elements arranged in a 3 row by 2 column array because it intersects 6 bins in such an arrangement. Each bin contains the head of a
383:
247:
is the number of candidates. If the candidates are evenly spaced so that each bin has a constant number of candidates, The query is O(
324:
58:
368:
116:
that allows efficient region queries. Each time a data point falls into a bin, the frequency of that bin is increased by one.
96:
120:
279:
105:
263:
is the number of bins the inserting candidate intersects. In practice delete is much slower than insert.
82:
202:
and dividing the result by the width and height of a bin respectively. We then can iterate the bins
363:
178:
320:
235:. The worst-case scenario is that all candidates are concentrated in one bin. Then query is O(
124:
88:
152:
113:
377:
282:. This requires the number of bins along an axis direction to be an exponent of 2.
163:
76:
255:
is the number of bins the query rectangle intersects. Insert and delete are O(
232:
72:
158:
The data structure partitions a region of the 2D plane into uniform-sized
354:
291:
129:"Given a query rectangle, what are the rectangles intersecting it?"
95:
87:
15:
278:
To further speed up the query, divisions can be replaced by
316:
139:
are existing rectangles, so the query with the rectangle
36:
31:
may be too technical for most readers to understand
360:is another efficient range query data structure
286:Compared to other range query data structures
8:
173:For example, in the top figure, candidate
127:, the structure can answer the question,
59:Learn how and when to remove this message
43:, without removing the technical details.
306:
100:A histogram ordered into 100,000 bins.
41:make it understandable to non-experts
7:
271:is visited 4 times in the query of
275:and so has to be skipped 3 times.
131:In the example in the top figure,
14:
151:, if we define all rectangles as
369:Quantization (signal processing)
20:
119:For example, if there are some
1:
243:), and insert is O(1), where
231:The analysis is similar to a
123:-aligned rectangles on a 2D
400:
80:
70:
384:Geometric data structures
194:From the query rectangle
166:of the bins encloses all
92:The bin data structure.
214:Insertion and deletion
106:computational geometry
101:
93:
227:Efficiency and tuning
99:
91:
83:Bin (disambiguation)
81:For other uses, see
364:Space partitioning
179:singly linked list
102:
94:
69:
68:
61:
391:
342:
341:
339:
338:
329:. Archived from
311:
153:closed intervals
64:
57:
53:
50:
44:
24:
23:
16:
399:
398:
394:
393:
392:
390:
389:
388:
374:
373:
351:
346:
345:
336:
334:
327:
313:
312:
308:
303:
288:
239:), delete is O(
229:
216:
192:
187:
86:
79:
65:
54:
48:
45:
37:help improve it
34:
25:
21:
12:
11:
5:
397:
395:
387:
386:
376:
375:
372:
371:
366:
361:
350:
347:
344:
343:
325:
305:
304:
302:
299:
287:
284:
228:
225:
215:
212:
191:
188:
186:
183:
143:should return
114:data structure
67:
66:
28:
26:
19:
13:
10:
9:
6:
4:
3:
2:
396:
385:
382:
381:
379:
370:
367:
365:
362:
359:
357:
353:
352:
348:
333:on 2016-03-06
332:
328:
326:9780549534365
322:
318:
317:
310:
307:
300:
298:
296:
294:
285:
283:
281:
276:
274:
270:
264:
262:
258:
254:
250:
246:
242:
238:
234:
226:
224:
220:
213:
211:
209:
205:
201:
197:
189:
184:
182:
180:
176:
171:
169:
165:
161:
156:
154:
150:
146:
142:
138:
134:
133:A, B, C, D, E
130:
126:
122:
117:
115:
111:
107:
98:
90:
84:
78:
74:
63:
60:
52:
42:
38:
32:
29:This article
27:
18:
17:
355:
335:. Retrieved
331:the original
315:
309:
292:
289:
280:right shifts
277:
272:
268:
265:
260:
256:
252:
248:
244:
240:
236:
230:
221:
217:
207:
203:
199:
195:
193:
174:
172:
167:
164:bounding box
159:
157:
148:
144:
140:
136:
132:
128:
118:
109:
103:
77:data binning
55:
46:
30:
337:2016-01-12
301:References
233:hash table
185:Operations
71:See also:
168:candidate
73:histogram
49:June 2012
378:Category
349:See also
319:. 2008.
290:Against
259:) where
251:) where
358:-d tree
295:-d tree
145:C, D, E
35:Please
323:
162:. The
108:, the
190:Query
125:plane
112:is a
321:ISBN
160:bins
147:and
135:and
121:axis
75:and
110:bin
104:In
39:to
380::
155:.
356:k
340:.
293:k
273:Q
269:E
261:m
257:m
253:k
249:k
245:n
241:n
237:n
208:Q
204:Q
200:Q
196:Q
175:B
149:F
141:Q
137:F
85:.
62:)
56:(
51:)
47:(
33:.
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
