1,a) 1 1 1,, 1. ([1]) ([2], [3]) A B 1 ([4]) 1 Graduate School of Information Science and Technology, Osaka University a) kawasumi.ryo@ist.osaka-u.ac.jp 1 1
Bucket R*-tree[5] [4] 2 3 4 5 6 2. 2.1 2.2 2.3 2.1 GSN (Global Sensor Network, [2]) P2P P2P [6] GSN X-Sensor2.0 ([3]) X-Sensor2.0 GSN P2P X-Sensor2.0 STQL (Spatio Temporal Query Language) X-Sensor2.0 2.2 R*-tree[5] R*-tree (Minimum Bounding Box, MBB) R*-tree 3 Bucket 2.3 [7] [4] [4] 3. 3.1 2 1 2 2
([2], [3]) P2P 45 135 6 1 11 20 46 136 7 20 1 1000hPa 4. 4.1 Bucket Bucket Bucket Bucket 4.2 4.3 4.4 4.5 4.2 Bucket Bucket 45 135 6 1 1 A 46 136 6 1 2 A B 6 1 1 2 45 135 46 136 A B (IP ) Bucket Bucket Bucket 4.3 Bucket Bucket Bucket Bucket Bucket R*-tree Bucket Bucket 4.3.1 [4] R*-tree Bucket Bucket ( ) Bucket Bucket 4.3.2 Bucket [4] Bucket Bucket E ( 3) overlap(v 1, V 2 ) V 1 V 2 V 1 V 2 E E = V 1 + V 2 overlap(v 1, V 2 ) E Bucket V 1 V 2 4 3
Bucket (13 14 ) getmergedbucket Bucket Bucket getoverlap (15 16 ) (17 20 ) 3 E 4 get- MergedBucket Bucket Bucket (25 26 ) Bucket (27 29 ) 5 6 Bucket ( 5) Q Q w, Q h, Q t 6 Bucket Bucket Bucket Bucket V 1 Bucket expand(v 1 ) E E = expand(v 1 ) + expand(v 2 ) overlap(expand(v 1 ), expand(v 2 )) Bucket V merged E j E V merged E j Bucket Bucket Bucket Bucket Algorithm 1 BucketB C C i C.child.get(i) Bucket Bucket getbuckettomerge getmergedbucket Bucket 2 Bucket getarea getoverlap getbuckettomerge Algorithm 1 Bucket 1: merge(b, C): 2: /* */ 3: tarea 0 4: tobj null 5: exist 1 6: i 0 7: /* Bucket */ 8: while i < c do 9: if C.child.get(i).id == B.id then 10: exist i 11: continue 12: end if 13: v1 getbuckettomerge(b,c.child.get(i)) 14: v2 getbuckettomerge(c.child.get(i),b) 15: mbr getmergedbucket(v1,v2) 16: err getoverlap(v1,v2) / getarea(mbr) 17: if tarea < getarea(mbr) && err E j then 18: tarea getarea(mbr) 19: tobj C.child.get(i) 20: end if 21: i i + 1 22: end while 23: /* */ 24: if tobj!= null then 25: tobj getmergedbucket(b, tobj) 26: tobj.s B.s + tobj.s 27: if exist > 0 then 28: C.child.remove(exist) 29: end if 30: return tobj 31: end if 32: return null 33: end 4.4 Bucket Bucket R*-tree ( Bucket ) [4] Bucket 4
Bucket 4.5 MBR [4] MBR Bucket Bucket ID ID 5. 5.1 Java CPU Intel(R) Core(TM) i7-3770 CPU @ 3.40GHz 8GB CentOS 6.3 2 2011 10 24 2012 5 31 25853434 E j 0.1 10000 1000 5.2 5.2.1 Bucket Bucket R*-tree Bucket (w/o considering query size) 7-14 7-8 2m 15 9-10 200m 1 7 9 Bucket 10-14 5.2.2 5.2.1 7 9 ( ) ( ) 8 ( ) 10 ( ) 5
R*-tree 15-18 proposal method- 2d proposal method-3d 15-16 Bucket 17-18 Bucket 6. Java 11 ( ) 13 ( ) 12 ( ) 14 ( ) 17 ( ) ( ) 18 Top-k IT IT (2012 2016 ) (A) ( 26240013) (A) ( 23680007) (SCOPE) [1] Wu, F.-J., Lim, H. B., Pereira, F., Zegras, C. and Ben- Akiva, M.: A User-centric Mobility Sensing System for Transportation Activity Surveys, Proceedings of the 11th ACM Conference on Embedded Networked Sensor Systems, SenSys 13, pp. 74:1 74:2 (2013). [2] Aberer, K., Hauswirth, M. and Salehi, A.: Global sensor networks, Technical report (2006). [3] Yoshihisa, T., Hamaguchi, Y., Ishi, Y., Teranishi, Y., Hara, T. and Nishio, S.: A Sensor Data Aggregation System Using Mobile Agents, Distributed Networks: Intelligence, Security, and Applications, pp. 39 63 (2013). [4] DEIM Forum 2014 E8-4 (2014). [5] Beckmann, N., Kriegel, H.-P., Schneider, R. and Seeger, B.: The R*-tree: an efficient and robust access method for points and rectangles, Vol. 19, No. 2, ACM (1990). [6] Perera, C., Zaslavsky, A., Christen, P., Salehi, A. and Georgakopoulos, D.: Capturing sensor data from mobile phones using global sensor network middleware, Personal Indoor and Mobile Radio Communications (PIMRC), 2012 IEEE 23rd International Symposium on, pp. 24 29 (2012). [7] Zhang, Y., Zhang, W., Lin, Q. and Lin, X.: Effectively indexing the multi-dimensional uncertain objects for range searching, Proceedings of the 15th International Conference on Extending Database Technology, pp. 504 515 (2012). 15 ( ) 16 ( ) 6