558:
in a cell are indistinguishable to the index, there will be some overflow nodes in the underlying B+ tree. The existing of overflow pages not only destroys the balancing of the tree but also increases the update cost. As for the queries, for the given query region, large cell incurs more false positives and increases the processing time. On the other hand, if the space is partitioned with finer grid, i.e. smaller cells, each cell contains few objects. There is hardly overflow pages so that the update cost is minimized. Fewer false positives are retrieved in a query. However, more cells are needed to be searched. The increase in the number of cells searched also increases the workload of a query.
571:
particular, as a partition shrinks to empty and starts growing, it chooses a new set of reference points and new grid for each reference point according to the latest data density. The tuning is based on the latest statistics collected during a given period of time, so that the way of space partitioning is supposed to fit the latest data distribution best. By this means, the STB-tree is expected to minimize the effect caused by data skew in space and data changes with time.
544:, which uses the B-tree for indexing the objects. In the implementation, moving object data is transformed and stored directly on MySQL, and queries are transformed into standard SQL statements which are efficiently processed in the relational engine. Most importantly, all these are achieved neatly and independently without infiltrating into the MySQL core.
69:
566:
The STB-tree introduces a self-tuning framework for tuning the performance of the B-tree while dealing with data skew in space and data change with time. In order to deal with data skew in space, the STB-tree splits the entire space into regions of different object density using a set of reference
557:
The B tree uses a grid for space partitioning while mapping two-dimensional location into one-dimensional key. This may introduce performance degradation to both query and update operations while dealing with skewed data. If grid cell is oversize, many objects are contained in a cell. Since objects
72:
An example of the B-tree with the number of index partitions equal to 2 within one maximum update interval tmu. In this example, there are maximum three partitions existing at the same time. After linearization, object locations inserted at time 0 are indexed in partition 0 with label timestamp 0.5
55:
locations being indexed and corresponding index time. In the optimized version, each leaf node entry contains the id, velocity, single-dimensional mapping value and the latest update time of the object. The fanout is increased by not storing the locations of moving objects, as these can be derived
570:
The B-tree have multiple partitions regarding different time intervals. As time elapsed, each partition grows and shrinks alternately. The STB-tree utilizes this feature to tune the index online in order to adjust the space partitioning to make itself accommodate to the data changes with time. In
352:
Given a new object, its index key is computed and then the object is inserted into the B-tree as in the B+ tree. An update consists of a deletion followed by an insertion. An auxiliary structure is employed to keep the latest key of each index so that an object can be deleted by searching for the
528:
Since the B-tree is an index built on top of a B+ tree index, all operations in the B-tree, including the insertion, deletion and search, are the same as those in the B+ tree. There is no need to change the implementations of these operations. The only difference is to implement the procedure of
490:
The B-tree uses query-window enlargement technique to answer queries. Since the B-tree stores an object's location as of sometime after its update time, the enlargement involves two cases: a location must either be brought back to an earlier time or forward to a later time. The main idea is to
494:
After the enlargement, the partitions of the B-tree need to be traversed to find objects falling in the enlarged query window. In each partition, the use of a space-filling curve means that a range query in the native, two-dimensional space becomes a set of range queries in the transformed,
73:
tmu, object locations updated during time 0 to 0.5 tmu are indexed in partition 1 with label timestamp tmu, and so on (as indicated by arrows). As time elapses, repeatedly the first range expires (shaded area), and a new range is appended (dashed line).
97:
into single dimensional value. Specifically, objects are first partitioned according to their update time. For objects within the same partition, the B-tree stores their locations at a given time which are estimated by
507:
K nearest neighbor query is computed by iteratively performing range queries with an incrementally enlarged search region until k answers are obtained. Another possibility is to employ similar querying ideas in
272:
498:
To avoid excessively large query region after expansion in skewed datasets, an optimization of the query algorithm exists, which improves the query efficiency by avoiding unnecessary query enlargement.
116:
Finally, with the combination of the partition number (time information) and the linear order (location information), an object is indexed in B-tree with a one-dimensional index key Bvalue:
462:
353:
key. The indexing key is computed before affecting the tree. In this way, the B-tree directly inherits the good properties of the B+ tree and achieves efficient update performance.
491:
enlarge the query window so that it encloses all objects whose positions are not within query window at its label timestamp but will enter the query window at the query timestamp.
89:, i.e., the time of last update. The B+ tree is a structure for indexing single-dimensional data. In order to adopt the B+ tree as a moving object index, the B-tree uses a
310:
485:
277:
Here index-partition is an index partition determined by the update time and xrep is the space-filling curve value of the object position at the indexed time,
105:
Secondly, the space is partitioned by a grid and the location of an object is linearized within the partitions according to a space-filling curve, e.g., the
959:
1166:
102:. By doing so, the B-tree keeps a consistent view of all objects within the same partition without storing the update time of each object.
710:
520:
The range query and K Nearest
Neighbor query algorithms can be easily extended to support interval queries, continuous queries, etc.
122:
642:
Robust B+-Tree-Based
Indexing of Moving Objects, in Proceedings of the Seventh International Conference on Mobile Data Management
826:
676:
44:
791:
1176:
52:
369:
732:
656:
567:
points. Each region uses an individual grid whose cell size is determined by the object density inside of it.
343:
Example O ((0,6), (0.2, -0.3 ),10) and tmu=120 then O's position at the label timestamp of partition: ???
534:
509:
40:
703:
683:. In Proceedings of ACM SIGMOD International Conference on Management of Data (SIGMOD), page 29-42, 2008.
870:
719:
615:. In Proceedings of 30th International Conference on Very Large Data Bases (VLDB), pages 768-779, 2004.
860:
815:
315:
Given an object O ((7, 2), (-0.1,0.05), 10), tmu = 120, the Bvalue for O can be computed as follows:
99:
974:
750:
106:
830:
1141:
1100:
926:
916:
795:
78:
280:
81:
as a linear function as O = ((x, y), (vx, vy), t ), where (x, y) and (vx, vy) are location and
1035:
736:
696:
540:
SpADE is moving object management system built on top of a popular relational database system
57:
1126:
641:
20:
628:
1222:
1070:
820:
680:
660:
590:
533:. Therefore, the B-tree can be easily integrated into existing DBMS without touching the
467:
1023:
1018:
901:
835:
366:
A range query retrieves all objects whose location falls within the rectangular range
1216:
1171:
1151:
994:
883:
810:
585:
110:
90:
745:
1131:
1095:
911:
906:
888:
800:
673:
1181:
1146:
1136:
1050:
984:
979:
969:
878:
727:
1191:
1161:
1121:
964:
893:
840:
760:
77:
As for many other moving objects indexes, a two-dimensional moving object is
1196:
1156:
1003:
931:
921:
48:
612:
1085:
775:
663:: A SPatio-temporal Autonomic Database Engine for location-aware services.
580:
319:
O is indexed in partition 0 as mentioned. Therefore, indexpartition = (00)
28:
1201:
1075:
1055:
1028:
1013:
765:
82:
1186:
1090:
1065:
1008:
855:
780:
755:
688:
329:
Using Z-curve with order = 3, the Z-value of O, i.e., xrep is (010011)
1105:
1080:
1060:
1045:
954:
845:
770:
674:
ST2B-tree: A Self-Tunable Spatio-Temporal B+-tree for Moving
Objects
653:
39:
The base structure of the B-tree is a B+ tree in which the internal
949:
850:
805:
613:
Query and Update
Efficient B+tree based Indexing of Moving Objects
541:
524:
Adapting relational database engines to accommodate moving objects
68:
67:
941:
530:
47:
to its right sibling. In the earlier version of the B-tree, the
692:
672:
Su Chen, Beng Chin Ooi, Kan-Lee. Tan, and Mario A. Nacismento,
529:
deriving the indexing key as a stored procedure in an existing
267:{\displaystyle B^{x}value\left(O,t\right)=\left_{2}+\left_{2}}
93:
technique which helps to integrate objects' location at time
326:
O’s position at the label timestamp of partition 0 is (1,5).
312:
denotes the binary value of x, and “+” means concatenation.
336:
Concatenating indexpartition and xrep, Bvalue (00010011)
631:, PhD thesis, National University of Singapore, 2006.
470:
372:
283:
125:
1114:
993:
940:
869:
726:
479:
456:
304:
266:
611:Christian S. Jensen, Dan Lin, and Beng Chin Ooi.
629:Indexing and Querying Moving Objects Databases
704:
8:
607:
605:
31:-based index structures for moving objects.
27:is a query that is used to update efficient
640:Jensen, C.S., D. Tiesyte, N. Tradisauskas,
711:
697:
689:
457:{\displaystyle q=\left(\left;\left\right)}
469:
371:
296:
282:
258:
226:
130:
124:
64:Utilizing the B+ tree for moving objects
43:serve as a directory, each containing a
644:, Nara, Japan, 9 pages, May 9–12, 2006.
601:
85:of the object at a given time instance
623:
621:
7:
14:
553:Potential problem with data skew
487:not prior to the current time.
348:Insertion, update and deletion
1:
1239:
305:{\displaystyle \left_{2}}
1167:Left-child right-sibling
503:K nearest neighbor query
997:data partitioning trees
955:C-trie (compressed ADT)
510:The iDistance Technique
495:one-dimensional space.
481:
458:
306:
268:
74:
16:Computer science query
482:
459:
307:
269:
71:
51:contained the moving-
1177:Log-structured merge
720:Tree data structures
468:
370:
281:
123:
100:linear interpolation
1142:Fractal tree index
737:associative arrays
679:2011-06-11 at the
659:2009-01-02 at the
548:Performance tuning
480:{\displaystyle tq}
477:
454:
302:
264:
75:
1210:
1209:
1230:
713:
706:
699:
690:
684:
670:
664:
651:
645:
638:
632:
625:
616:
609:
486:
484:
483:
478:
463:
461:
460:
455:
453:
449:
448:
444:
414:
410:
311:
309:
308:
303:
301:
300:
295:
273:
271:
270:
265:
263:
262:
257:
253:
231:
230:
225:
221:
169:
165:
135:
134:
21:computer science
1238:
1237:
1233:
1232:
1231:
1229:
1228:
1227:
1213:
1212:
1211:
1206:
1110:
989:
936:
865:
861:Weight-balanced
816:Order statistic
730:
722:
717:
687:
681:Wayback Machine
671:
667:
661:Wayback Machine
652:
648:
639:
635:
626:
619:
610:
603:
599:
591:Z-order (curve)
577:
564:
555:
550:
526:
518:
505:
466:
465:
422:
418:
388:
384:
383:
379:
368:
367:
364:
359:
350:
339:
332:
322:
285:
284:
279:
278:
240:
236:
235:
178:
174:
173:
155:
151:
126:
121:
120:
66:
37:
35:Index structure
17:
12:
11:
5:
1236:
1234:
1226:
1225:
1215:
1214:
1208:
1207:
1205:
1204:
1199:
1194:
1189:
1184:
1179:
1174:
1169:
1164:
1159:
1154:
1149:
1144:
1139:
1134:
1129:
1124:
1118:
1116:
1112:
1111:
1109:
1108:
1103:
1098:
1093:
1088:
1083:
1078:
1073:
1068:
1063:
1058:
1053:
1048:
1043:
1026:
1021:
1016:
1011:
1006:
1000:
998:
991:
990:
988:
987:
982:
977:
975:Ternary search
972:
967:
962:
957:
952:
946:
944:
938:
937:
935:
934:
929:
924:
919:
914:
909:
904:
899:
891:
886:
881:
875:
873:
867:
866:
864:
863:
858:
853:
848:
843:
838:
833:
823:
818:
813:
808:
803:
798:
788:
783:
778:
773:
768:
763:
758:
753:
748:
742:
740:
724:
723:
718:
716:
715:
708:
701:
693:
686:
685:
665:
646:
633:
617:
600:
598:
595:
594:
593:
588:
583:
576:
573:
563:
560:
554:
551:
549:
546:
525:
522:
517:
514:
504:
501:
476:
473:
452:
447:
443:
440:
437:
434:
431:
428:
425:
421:
417:
413:
409:
406:
403:
400:
397:
394:
391:
387:
382:
378:
375:
363:
360:
358:
355:
349:
346:
345:
344:
341:
337:
334:
330:
327:
324:
320:
299:
294:
291:
288:
275:
274:
261:
256:
252:
249:
246:
243:
239:
234:
229:
224:
220:
217:
214:
211:
208:
205:
202:
199:
196:
193:
190:
187:
184:
181:
177:
172:
168:
164:
161:
158:
154:
150:
147:
144:
141:
138:
133:
129:
111:Hilbert curves
65:
62:
36:
33:
15:
13:
10:
9:
6:
4:
3:
2:
1235:
1224:
1221:
1220:
1218:
1203:
1200:
1198:
1195:
1193:
1190:
1188:
1185:
1183:
1180:
1178:
1175:
1173:
1170:
1168:
1165:
1163:
1160:
1158:
1155:
1153:
1152:Hash calendar
1150:
1148:
1145:
1143:
1140:
1138:
1135:
1133:
1130:
1128:
1125:
1123:
1120:
1119:
1117:
1113:
1107:
1104:
1102:
1099:
1097:
1094:
1092:
1089:
1087:
1084:
1082:
1079:
1077:
1074:
1072:
1069:
1067:
1064:
1062:
1059:
1057:
1054:
1052:
1049:
1047:
1044:
1041:
1039:
1033:
1031:
1027:
1025:
1022:
1020:
1017:
1015:
1012:
1010:
1007:
1005:
1002:
1001:
999:
996:
992:
986:
983:
981:
978:
976:
973:
971:
968:
966:
963:
961:
958:
956:
953:
951:
948:
947:
945:
943:
939:
933:
930:
928:
927:van Emde Boas
925:
923:
920:
918:
917:Skew binomial
915:
913:
910:
908:
905:
903:
900:
898:
896:
892:
890:
887:
885:
882:
880:
877:
876:
874:
872:
868:
862:
859:
857:
854:
852:
849:
847:
844:
842:
839:
837:
834:
832:
828:
824:
822:
819:
817:
814:
812:
809:
807:
804:
802:
799:
797:
796:Binary search
793:
789:
787:
784:
782:
779:
777:
774:
772:
769:
767:
764:
762:
759:
757:
754:
752:
749:
747:
744:
743:
741:
738:
734:
729:
725:
721:
714:
709:
707:
702:
700:
695:
694:
691:
682:
678:
675:
669:
666:
662:
658:
655:
650:
647:
643:
637:
634:
630:
624:
622:
618:
614:
608:
606:
602:
596:
592:
589:
587:
586:Hilbert curve
584:
582:
579:
578:
574:
572:
568:
561:
559:
552:
547:
545:
543:
538:
536:
532:
523:
521:
516:Other queries
515:
513:
511:
502:
500:
496:
492:
488:
474:
471:
450:
445:
441:
438:
435:
432:
429:
426:
423:
419:
415:
411:
407:
404:
401:
398:
395:
392:
389:
385:
380:
376:
373:
361:
356:
354:
347:
342:
335:
328:
325:
318:
317:
316:
313:
297:
292:
289:
286:
259:
254:
250:
247:
244:
241:
237:
232:
227:
222:
218:
215:
212:
209:
206:
203:
200:
197:
194:
191:
188:
185:
182:
179:
175:
170:
166:
162:
159:
156:
152:
148:
145:
142:
139:
136:
131:
127:
119:
118:
117:
114:
112:
108:
103:
101:
96:
92:
91:linearization
88:
84:
80:
70:
63:
61:
59:
54:
50:
46:
42:
34:
32:
30:
26:
22:
1037:
1029:
894:
827:Left-leaning
785:
733:dynamic sets
728:Search trees
668:
649:
636:
569:
565:
562:Index tuning
556:
539:
527:
519:
506:
497:
493:
489:
365:
351:
314:
276:
115:
104:
94:
86:
76:
38:
24:
18:
1127:Exponential
1115:Other trees
362:Range query
1071:Priority R
821:Palindrome
597:References
49:leaf nodes
1157:iDistance
1036:implicit
1024:Hilbert R
1019:Cartesian
902:Fibonacci
836:Scapegoat
831:Red–black
627:Dan Lin.
56:from the
1217:Category
1172:Link/cut
884:Binomial
811:Interval
677:Archived
657:Archived
575:See also
464:at time
83:velocity
60:values.
1132:Fenwick
1096:Segment
995:Spatial
912:Pairing
907:Leftist
829:)
801:Dancing
794:)
792:Optimal
581:B+ tree
357:Queries
79:modeled
58:mapping
45:pointer
29:B+ tree
1223:B-tree
1182:Merkle
1147:Fusion
1137:Finger
1061:Octree
1051:Metric
985:Y-fast
980:X-fast
970:Suffix
889:Brodal
879:Binary
535:kernel
53:object
25:B tree
23:, the
1192:Range
1162:K-ary
1122:Cover
965:Radix
950:Ctrie
942:Tries
871:Heaps
851:Treap
841:Splay
806:HTree
761:(a,b)
751:2–3–4
654:SpADE
542:MySQL
107:Peano
41:nodes
1197:SPQR
1076:Quad
1004:Ball
960:Hash
932:Weak
922:Skew
897:-ary
531:DBMS
340:=19.
1202:Top
1056:MVP
1014:BSP
766:AVL
746:2–3
109:or
19:In
1219::
1187:PQ
1101:VP
1091:R*
1086:R+
1066:PH
1040:-d
1032:-d
1009:BK
856:UB
781:B*
776:B+
756:AA
620:^
604:^
537:.
512:.
113:.
1106:X
1081:R
1046:M
1042:)
1038:k
1034:(
1030:k
895:d
846:T
825:(
790:(
786:B
771:B
739:)
735:/
731:(
712:e
705:t
698:v
475:q
472:t
451:)
446:]
442:2
439:y
436:q
433:;
430:2
427:x
424:q
420:[
416:;
412:]
408:1
405:y
402:q
399:,
396:1
393:x
390:q
386:[
381:(
377:=
374:q
338:2
333:.
331:2
323:.
321:2
298:2
293:]
290:X
287:[
260:2
255:]
251:p
248:e
245:r
242:x
238:[
233:+
228:2
223:]
219:n
216:o
213:i
210:t
207:i
204:t
201:r
198:a
195:p
192:x
189:e
186:d
183:n
180:i
176:[
171:=
167:)
163:t
160:,
157:O
153:(
149:e
146:u
143:l
140:a
137:v
132:x
128:B
95:t
87:t
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
