Throughput Oriented Range Query Algorithm for Moving Objects in Dual Stream Mode
Author:
Affiliation:

  • Article
  • | |
  • Metrics
  • |
  • Reference [19]
  • |
  • Related [20]
  • | | |
  • Comments
    Abstract:

    With the development of location-aware mobile devices, communication technologies and GPS systems, location based queries have become an important research issue in the area of database. This paper studies the problem of snapshot based spatial range query which searches for the moving objects within a specific query range in a specific time interval. Range query is the building block of other types of spatial queries, such as k nearest neighbor query and reverse k nearest neighbor query. A series of algorithms have been proposed to process range queries of moving objects. However, these algorithms are either designed for fast response time or high update performance. They are not purposely designed for the situation of big data where throughput is more important as both queries and updates arrive at a very high rate. For the query stream and object update stream, a high throughput main memory algorithm—Dual Stream Join algorithm is proposed for moving object range query. DSJ uses a snapshot approach. In each snapshot, DSJ builds a new index structure based on the update of the moving objects, which avoids maintaining a sophisticate structures and gives full play to the performance of the hardware. DSJ executes a batch queries at each run, which increases the data locality and improves the efficiency of the algorithm. DSJ also employs the SIMD technology to accelerate the query processing and makes sure that the system has high throughput. A comprehensive performance evaluation of the proposed techniques is conducted using the German network generated data. The results show that DSJ is highly efficient.

    Reference
    [1] Zhou AY, Yang B, Jin CQ, Ma Q. Location-Based services: Architecture and progress. Chinese Journal of Computers, 2011,34(7):1155-1171 (in Chinese with English abstract). [doi: 10.3724/SP.J.1016.2011.01155]
    [2] Dittrich J, Blunschi L, Salles MAV. Indexing moving objects using short-lived throwaway indexes. In: Proc. of the Advances in Spatial and Temporal Databases. Berlin, Heidelberg: Springer-Verlag, 2009. 189-207. [doi: 10.1007/978-3-642-02982-0_14]
    [3] Yu XH, Pu KQ, Koudas N. Monitoring k-nearest neighbor queries over moving objects. In: Proc. of the 21st Int'l Conf. on Data Engineering. Toronto: IEEE, 2005. 631-642. [doi: 10.1109/ICDE.2005.92]
    [4] Dittrich J, Blunschi L, Salles MAV. MOVIES: Indexing moving objects by shooting index images. Geo Informatica, 2011,15(4): 727-767. [doi: 10.1007/s10707-011-0122-y]
    [5] Šidlauskas D, Ross KA, Jensen CS, Šaltenis S. Thread-Level parallel indexing of update intensive moving-object workloads. In: Proc. of the Advances in Spatial and Temporal Databases. Berlin, Heidelberg: Springer-Verlag, 2011. 186-204. [doi: 10.1007/978- 3-642-22922-0_12]
    [6] Šidlauskas D, Šaltenis S, Jensen CS. Parallel main-memory indexing for moving-object query and update workloads. In: Proc. of the 2012 ACM SIGMOD Int'l Conf. on Management of Data. Scottsdale: ACM Press, 2012. 37-48. [doi: 10.1145/2213836. 2213842]
    [7] Zhang J, Zhu M, Papadias D, Tao Y, Lee DL. Location-Based spatial queries. In: Proc. of the 2003 ACM SIGMOD Int'l Conf. on Management of Data. San Diego: ACM Press, 2003. 443-454. [doi: 10.1145/872757.872812]
    [8] To QC, Dang TK, Kung J. OST-Tree: An access method for obfuscating spatio-temporal data in location based services. In: Proc. of the 4th IFIP Int'l Conf. on New Technologies, Mobility and Security (NTMS). Ho Chi Minh City: IEEE, 2011. 1-5. [doi: 10. 1109/NTMS.2011.5720620]
    [9] Tao Y, Papadias D, Sun J. The TPR*-tree: An optimized spatio-temporal access method for predictive queries. In: Proc. of the 29th Int'l Conf. on Very Large Data Bases. Berlin: VLDB Endowment, 2003. 790-801.
    [10] Harizopoulos S, Liang V, Abadi DJ, Madden S. Performance tradeoffs in read-optimized databases. In: Proc. of the 32nd Int'l Conf. on Very Large Data Bases. Seoul: VLDB Endowment, 2006. 487-498. [doi: 10.3724/SP.J.1016.2011.01155]
    [11] Orenstein JA, Merrett TH. A class of data structures for associative searching. In: Proc. of the 3rd ACM SIGACT-SIGMOD Symp. on Principles of Database Systems. Boston: ACM Press, 1984. 181-190. [doi: 10.1145/588011.588037]
    [12] Tropf H, Herzog H. Multidimensional range search in dynamically balanced trees. Angewandte Info, 1981,(2):71-77.
    [13] Hilbert D. Ueber die stetige abbildung einer line auf ein flächenstück. Mathematische Annalen, 1891,8(3):459-460. [doi: 10.1007/ 978-3-662-25726-5_1]
    [14] Mokbel MF, Xiong X, Aref WG. SINA: Scalable incremental processing of continuous queries in spatio-temporal databases. In: Proc. of the 2004 ACM SIGMOD Int'l Conf. on Management of Data. Paris: ACM Press, 2004. 623-634. [doi: 10.1145/1007568. 1007638]
    [15] Balkesen C, Alonso G, Teubner J, Tamerözsu M. Main-Memory Hash joins on modern processor architectures. IEEE Trans. on Knowledge and Data Engineering (TKDE), 2015. [doi: 10.1109/TKDE.2014.2313874]
    [16] Patel JM, De Witt DJ. Partition based spatial-merge join. ACM SIGMOD Record, 1996,25(2):259-270. [doi: 10.1145/235968. 233338]
    [17] Manegold S, Boncz P, Kersten M. Optimizing main-memory join on modern hardware. IEEE Trans. on Knowledge and Data Engineering, 2002,14(4):709-730. [doi: 10.1109/TKDE.2002.1019210]
    [18] Brinkhoff T. A framework for generating network-based moving objects. Geo Informatica, 2002,6(2):153-180. [doi: 10.1023/A: 1015231126594]
    附中文参考文献:[1] 周傲英,杨彬,金澈清,马强.基于位置的服务:架构与进展.计算机学报,2011,34(7):1155-1171. [doi: 10.3724/SP.J.1016.2011.01155]
    Cited by
    Comments
    Comments
    分享到微博
    Submit
Get Citation

薛忠斌,周烜,王珊.双流模式下高吞吐量移动对象范围查询算法.软件学报,2015,26(10):2631-2643

Copy
Share
Article Metrics
  • Abstract:2506
  • PDF: 4359
  • HTML: 1246
  • Cited by: 0
History
  • Received:June 07,2014
  • Revised:December 09,2014
  • Online: October 10,2015
You are the first2032504Visitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
Address:4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code:100190
Phone:010-62562563 Fax:010-62562533 Email:jos@iscas.ac.cn
Technical Support:Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063