Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
GeoInformatica
Published in: GeoInformatica 1/2019

09-10-2018

Spatio-temporal access methods: a survey (2010 - 2017)

Authors: Ahmed R. Mahmood, Sri Punni, Walid G. Aref

Published in: GeoInformatica | Issue 1/2019

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

The volume of spatio-temporal data is growing at a rapid pace due to advances in location-aware devices, e.g., smartphones, and the popularity of location-based services, e.g., navigation services. A number of spatio-temporal access methods have been proposed to support efficient processing of queries over the spatio-temporal data. Spatio-temporal access methods can be classified according to the type of data being indexed into the following categories: (1) indexes for historical spatio-temporal data, (2) indexes for current and recent spatio-temporal data, (3) indexes for future spatio-temporal data, (4) indexes for past, present, and future spatio-temporal data, (5) indexes for spatio-temporal data with associated textual data, and (6) parallel and distributed spatio-temporal systems and indexes. This survey is Part 3 of our previous surveys on the same subject (Mokbel et al. IEEE Data Eng Bull 26(2):40–49, 2003; Nguyen-Dinh et al. IEEE Data Eng Bull 33(2):46–55, 2010). In this survey, we present an overview and a broad classification of the spatio-temporal access methods published between 2010 and 2017.
next article Spatial data management in apache spark: the GeoSpark perspective and beyond

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
Literature
1.
Abdelguerfi M, Givaudan J, Shaw K, Ladner R (2002) The 2-3TR-tree, a trajectory-oriented index structure for fully evolving valid-time spatio-temporal datasets. In: ACM-GIS, pp 29–34
2.
Agarwal PK, Arge L, Erickson J (2000) Indexing moving points. In: Proceedings of the nineteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems (PODS), pp 175–186. ACM
3.
Ahmed P, Hasan M, Kashyap A, Hristidis V, Tsotras VJ (2017) Efficient computation of top-k frequent terms over spatio-temporal ranges. In: The international conference on management of data (SIGMOD’17), pp 1227–1241
4.
Akdogan A, Shahabi C, Demiryurek U (2014) ToSS-it: A cloud-based throwaway spatial index structure for dynamic location data. In: The IEEE international conference on mobile data management (MDM’14), pp 249–258
5.
Akdogan A, Shahabi C, Demiryurek U (2016) D-toSS: A distributed throwaway spatial index structure for dynamic location data. IEEE Trans Knowl Data Eng (TKDE) 28(9):2334–2348CrossRef
6.
Akman V, Franklin WR, Kankanhalli M, Narayanaswami C (1989) Geometric computing and uniform grid technique. Comput Aided Des 21(7):410–420CrossRef
7.
Alarabi L, Mokbel MF (2017) A demonstration of ST-hadoop: A mapreduce framework for big spatio-temporal data. The Proceedings of the VLDB Endowment (PVLDB’17) 10(12):1961–1964CrossRef
8.
Aref WG, Samet H (1990) Efficient processing of window queries in the pyramid data structure. In: Proceedings of the ninth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, pp 265–272
9.
Atluri V, Adam NR, Youssef M (2003) Towards a unified index scheme for mobile data and customer profiles in a location-based service environment. In: Workshop on next generation geospatial information (NG2i’03). Citeseer
10.
Atluri V, Guo Q (2005) Unified index for mobile object data and authorizations. In: European symposium on research in computer security, pp 80–97. Springer
11.
Atluri V, Shin H (2007) Efficient security policy enforcement in a location based service environment. In: IFIP Annual conference on data and applications security and privacy, pp 61–76. Springer
12.
Bayer R, MCCReight E (1972) Organization and maintenance of large ordered indexes. Acta Informatica 1:173–189CrossRef
13.
Becker B, Gschwind S, Ohler T, Seeger B, Widmayer P (1996) An asymptotically optimal multiversion B-tree. Intern J Very Large Data Bases (VLDB Journal) 5(4):264–275CrossRef
14.
Beckmann N, Kriegel HP, Schneider R, Seeger B (1990) The R*-tree: An efficient and robust access method for points and rectangles. SIGMOD Rec 19(2):322–331CrossRef
15.
Belhassena A, HongZhi W (2017) Distributed skyline trajectory query processing. In: Proceedings of the ACM Turing 50th Celebration Conference-China, p 19. ACM
16.
Bentley JL (1975) Multidimensional binary search trees used for associative searching. Commun ACM 18(9):509–517CrossRef
17.
Blei DM, Ng AY, Jordan MI (2003) Latent dirichlet allocation. J Machine Learn Res 3(Jan):993–1022
18.
Bok KS, Seo DM, Shin SS, Yoo JS (2004) TPKDB-Tree: An index structure for efficient retrieval of future positions of moving objects. In: International conference on conceptual modeling, pp 67–78. Springer
19.
Brisaboa NR, Ladra S (2009) Navarro, g.: k2-trees for compact web graph representation. In: The international symposium on string processing and information retrieval, vol 9, pp 18–30
20.
Burton FW, Kollias JG, Matsakis D, Kollias V (1990) Implementation of overlapping B-trees for time and space efficient representation of collections of similar files. Comput J 33(3):279–280CrossRef
21.
Cai M, Revesz P (2000) Parametric R-tree: An index structure for moving objects. In: International conference on management of data and advances in data management (COMAD’00)
22.
Cai R, Lu Z, Wang L, Zhang Z, Fu TZ, Winslett M (2017) DITIR: Distributed Index for high throughput trajectory insertion and real-time temporal range query. The Proceedings of the VLDB Endowment (PVLDB’17) 10(12):1865–1868CrossRef
23.
Cai Y, Ng R (2004) Indexing spatio-temporal trajectories with chebyshev polynomials. In: International conference on management of data (SIGMOD’04), pp 599–610. ACM
24.
Cha SK, Hwang S, Kim K, Kwon K (2001) Cache-conscious concurrency control of main-memory indexes on shared-memory multiprocessor systems. In: The Proceedings of the VLDB Endowment (PVLDB’01), vol 1, pp 181–190
25.
Chakka VP, Everspaugh A, Patel JM (2003) Indexing large trajectory data sets with SETI. In: The biennial conference on innovative data systems research (CIDR’03)
26.
Chen JD, Meng XF (2007) Indexing future trajectories of moving objects in a constrained network. J Comput Sci Technol 22(2):245–251CrossRef
27.
Chen N, Shou LD, Chen G, Dong JX (2008) Adaptive indexing of moving objects with highly variable update frequencies. J Comput Sci Technol 23(6):998–1014CrossRef
28.
Chen S, Ooi BC, Tan KL, Nascimento MA (2008) ST2B-tree: A self-tunable spatio-temporal b+-tree index for moving objects. In: International conference on management of data (SIGMOD’11), pp 29–42. ACM
29.
Chen W, Zhao L, Jiajie X, Zheng K, Zhou X (2014) Ranking based activity trajectory search. In: International conference on web information systems engineering, pp 170–185. Springer
30.
Chon HD, Agrawal D, El Abbadi A (2001) Storage and retrieval of moving objects. In: International conference on mobile data management (MDM’01), pp 173–184. Springer
31.
Christoforaki M, He J, Dimopoulos C, Markowetz A, Suel T (2011) Text vs. space: efficient geo-search query processing. In: The ACM international conference on information and knowledge management (CIKM’11), pp 423–432
32.
Cudre-Mauroux P, Wu E, Madden S (2010) Trajstore: an adaptive storage system for very large trajectory data sets. In: The international conference on data engineering (ICDE’10), pp 109–120. IEEE
33.
Dai J, Lu CT (2011) DIME: Disposable Index for moving objects. In: The IEEE international conference on mobile data management (MDM’11), vol 1, pp 68–77
34.
De Almeida VT, Güting RH (2005) Indexing the trajectories of moving objects in networks. Geoinformatica 9(1):33–60CrossRef
35.
Ding X, Lu Y, Ding X, Zhao N, Wei Q (2007) An efficient index for moving objects with frequent updates. In: International conference on wireless communications, networking and mobile computing (wicom’07), pp 5951–5954. IEEE
36.
Ding Z (2008) UTR-Tree: An index structure for the full uncertain trajectories of network-constrained moving objects. In: International conference on mobile data management (MDM’08), pp 33–40. IEEE
37.
Dittrich J, Blunschi L, Salles MAV (2009) Indexing moving objects using short-lived throwaway indexes. In: International symposium on spatial and temporal databases, pp 189–207. Springer
38.
Dittrich J, Quiané-Ruiz JA (2012) Efficient big data processing in hadoop mapreduce. Proceedings of the VLDB Endowment (PVLD’12) 5(12):2014–2015CrossRef
39.
Doraiswamy H, Vo HT, Silva CT, Freire J (2016) A GPU-based index to support interactive spatio-temporal queries over historical data. In: The IEEE international conference on data engineering (ICDE’16), pp 1086–1097
40.
Elbassioni K, Elmasry A, Kamel I (2003) An efficient indexing scheme for multi-dimensional moving objects. In: International conference on database theory, pp 425–439. Springer
41.
Eldawy A, Mokbel MF (2015) Spatialhadoop: a mapreduce framework for spatial data. In: The IEEE international conference on data engineering (ICDE’15), pp 1352–1363
42.
Fan P, Li G, Yuan L, Li Y (2012) Vague continuous k-nearest neighbor queries over moving objects with uncertain velocity in road networks. Inf Syst 37(1):13–32CrossRef
43.
Fang Y, Cao J, Peng Y, Wang L (2008) Indexing the past, present and future positions of moving objects on fixed networks. In: International conference on computer science and software engineering, vol 4, pp 524–527. IEEE
44.
Fang Y, Cao J, Wang J, Peng Y, Song W (2011) HTPR*-Tree: An efficient index for moving objects to support predictive query and partial history query. In: International conference on web-age information management (WAIM’11), pp 26–39. Springer
45.
Feng J, Lu J, Zhu Y, Mukai N, Watanabe T (2007) Indexing of moving objects on road network using composite structure. In: International conference on knowledge-based and intelligent information and engineering systems, pp 1097–1104. Springer
46.
Finkel RA, Bentley JL (1974) Quad trees a data structure for retrieval on composite keys. Acta informatica 4(1):1–9CrossRef
47.
Frentzos E (2003) Indexing objects moving on fixed networks. In: International symposium on spatial and temporal databases, pp 289–305. Springer
48.
Ghanem TM, Hammad MA, Mokbel MF, Aref WG, Elmagarmid AK (2007) Incremental evaluation of sliding-window queries over data streams. IEEE Trans Knowl Data Eng (TKDE) 19(1):57–72
49.
Gionis A, Indyk P, Motwani R, et al. (1999) Similarity search in high dimensions via hashing. In: The Proceedings of the VLDB Endowment (PVLDB’99), vol 99, pp 518–529
50.
Gravano L, Ipeirotis PG, Jagadish HV, Koudas N, Muthukrishnan S, Srivastava D et al (2001) Approximate string joins in a database (almost) for free. In: The Proceedings of the VLDB Endowment (PVLDB’01), vol 1, pp 491–500
51.
Guttman A (1984) R-trees: a dynamic index structure for spatial searching. SIGMOD Rec 14:47–57CrossRef
52.
Hadjieleftheriou M, Kollios G, Tsotras VJ, Gunopulos D (2002) Efficient indexing of spatiotemporal objects. In: International conference on extending database technology, pp 251–268. Springer
53.
Han L, Huang L, Yang X, Pang W, Wang K (2016) A novel spatio-temporal data storage and index method for ARM-based hadoop server. In: International conference on cloud computing and security, pp 206–216. Springer
54.
Han Y, Wang L, Zhang Y, Zhang W, Lin X (2015) Spatial keyword range search on trajectories. In: The international conference on database systems for advanced applications (DASFAA’15), pp 223–240
55.
Hariharan R, Hore B, Li C, Mehrotra S (2007) Processing spatial-keyword (SK) queries in geographic information retrieval (GIR) systems. In: The international conference on scientific and statistical database management (SSDBM’07), pp 16–16
56.
He Z, Kraak MJ, Huisman O, Ma X, Xiao J (2013) Parallel indexing technique for spatio-temporal data. ISPRS J Photogramm Remote Sens 78:116–128CrossRef
57.
Hendawi AM, Bao J, Mokbel MF, Ali M (2015) Predictive tree: an efficient index for predictive queries on road networks. In: The IEEE international conference on data engineering (ICDE’15), pp 1215–1226
58.
Issa H, Damiani ML (2016) Efficient access to temporally overlaying spatial and textual trajectories. In: The IEEE international conference on mobile data management (MDM’16), vol 1, pp 262–271
59.
Jackins CL, Tanimoto SL (1980) OCT-Trees and their use in representing three-dimensional objects. Comput Graphics and Image Process 14(3):249–270CrossRef
60.
Jensen CS, Lin D, Ooi BC (2004) Query and update efficient b+-tree based indexing of moving objects. In: The Proceedings of the VLDB Endowment (PVLDB’04), pp 768–779
61.
Jensen CS, Lu H, Yang B (2009) Indexing the trajectories of moving objects in symbolic indoor space. In: International symposium on spatial and temporal databases, pp 208–227. Springer
62.
Jeung H, Yiu ML, Zhou X, Jensen CS (2010) Path prediction and predictive range querying in road network databases. Intern J Very Large Data Bases (VLDB J) 19(4):585–602CrossRef
63.
Kim KS, Kim SW, Kim TW, Li KJ (2003) Fast indexing and updating method for moving objects on road networks. In: International conference on web information systems engineering workshops, pp 34–42. IEEE
64.
Knuth D (1973) The art of computer programming
65.
Kollios G, Gunopulos D, Tsotras VJ (1999) On indexing mobile objects. In: Proceedings of the eighteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems (PODS), pp 261–272. ACM
66.
Kollios G, Tsotras VJ, Gunopulos D, Delis A, Hadjieleftheriou M (2001) Indexing animated objects using spatiotemporal access methods. IEEE Trans Knowl Data Eng (TKDE) 13(5):758–777CrossRef
67.
Kumar A, Tsotras VJ, Faloutsos C (1998) Designing access methods for bitemporal databases. IEEE Trans Knowl Data Eng (TKDE) 10(1):1–20CrossRef
68.
Kwon D, Lee S, Lee S (2002) Indexing the current positions of moving objects using the lazy update R-tree. In: International conference on mobile data management (MDM’03), pp 113–120. IEEE
69.
Le TTT, Nickerson BG (2008) Efficient search of moving objects on a planar graph. In: International conference on advances in geographic information systems (SIGSPATIAL’08), p 41. ACM
70.
Lee ML, Hsu W, Jensen CS, Cui B, Teo KL (2003) Supporting frequent updates in R-trees: a bottom-up approach. In: The Proceedings of the VLDB Endowment (PVLDB’03), pp 608–619
71.
Liang Y (2011) A efficient indexing maintenance method for grouping moving objects with grid. pp 486–492 Elsevier
72.
Liao W, Tang G, Jing N, Zhong Z (2006) VTPR-Tree: An efficient indexing method for moving objects with frequent updates. In: International conference on conceptual modeling, pp 120–129. Springer
73.
Lin B, Mokhtar H, Pelaez-Aguilera R, Su J (2003) Querying moving objects with uncertainty. In: Vehicular technology conference (VTC’03), vol 4, pp 2783–2787. IEEE
74.
Lin B, Su J (2005) Handling frequent updates of moving objects. In: International conference on information and knowledge management, pp 493–500. ACM
75.
Lin D, Jensen CS, Ooi BC, Šaltenis S (2005) Efficient indexing of the historical, present, and future positions of moving objects. In: International conference on mobile data management (MDM’05), pp 59–66. ACM
76.
Lin D, Jensen CS, Zhang R, Xiao L, Lu J (2011) A moving-object index for efficient query processing with peer-wise location privacy. The Proceedings of the VLDB Endowment (PVLDB’11) 5(1):37–48CrossRef
77.
Lin D, Zhang R, Zhou A (2006) Indexing fast moving objects for kNN queries based on nearest landmarks. Geoinformatica 10(4):423–445CrossRef
78.
Lin HY (2009) Indexing the trajectories of moving objects. International multi-conference of engineers and computer scientists
79.
Liu H, Xu J, Zheng K, Liu C, Du L, Wu X (2017) Semantic-aware query processing for activity trajectories. In: Proceedings of the Tenth ACM International Conference on Web Search and Data Mining, pp 283–292. ACM
80.
Liu Z, Liu X, Ge J, Bae H (2005) Indexing large moving objects from past to future with PCFI+-index. In: International conference on management of data and advances in data management (COMAD’05), pp 131–137
81.
Lomet D, Salzberg B (1989) Access methods for multiversion data, vol 18. ACM
82.
Luo W, Tan H, Chen L, Ni LM (2013) Finding time period-based most frequent path in big trajectory data. In: The international conference on management of data (SIGMOD’13), pp 713–724
83.
Ma C, Lu H, Shou L, Chen G (2013) KSQ: Top-K similarity query on uncertain trajectories. IEEE Trans Knowl Data Eng (TKDE) 25(9):2049–2062CrossRef
84.
MacQueen J, et al. (1967) Some methods for classification and analysis of multivariate observations. In: Proceedings of the fifth Berkeley symposium on mathematical statistics and probability, vol 1, pp 281–297
85.
Magdy A, Aly AM, Mokbel MF, Elnikety S, He Y, Nath S, Aref WG (2016) GeoTrend: Spatial trending queries on real-time microblogs. In: The ACM international conference on advances in geographic information systems (SIGSPATIAL’16), p 7
86.
Magdy A, Mokbel MF, Elnikety S, Nath S, He Y (2014) Mercury: a memory-constrained spatio-temporal real-time search on microblogs. In: The IEEE international conference on data engineering (ICDE’14), pp 172–183
87.
Mahmood AR, Aly AM, Kuznetsova T, Basalamah S, Aref WG (2018) Disk-based indexing of recent trajectories. ACM Transactions on Spatial Algorithms and Systems (TSAS) 4(3):7.1–7.27
88.
Mahmood AR, Aref WG, Aly AM, Basalamah S (2014) Indexing recent trajectories of moving objects. In: The ACM international conference on advances in geographic information systems (SIGSPATIAL’14), pp 393–396
89.
Meagher DJ (1980) OCTRee encoding: A new technique for the representation, manipulation and display of arbitrary 3-d objects by computer. Electrical and Systems Engineering Department Rensseiaer Polytechnic Institute Image Processing Laboratory
90.
Mehta P, Skoutas D, Voisard A (2015) Spatio-temporal keyword queries for moving objects. In: The ACM international conference on advances in geographic information systems (SIGSPATIAL’15), p 55
91.
Mokbel MF, Ghanem TM, Aref WG (2003) Spatio-temporal access methods. IEEE Data Eng Bull 26(2):40–49
92.
Morton GM (1966) A computer oriented geodetic data base and a new technique in file sequencing. International Business Machines Company, New York
93.
Mukai N, Feng J, Watanabe T (2004) Heuristic approach based on lambda-interchange for VRTPR-tree on specific vehicle routing problem with time windows. In: International conference on industrial, engineering and other applications of applied intelligent systems, pp 229–238. Springer
94.
Mukai N, Feng J, Watanabe T (2004) Indexing approach for delivery demands with time constraints. In: Pacific rim international conference on artificial intelligence, pp 95–103. Springer
95.
Nascimento MA, Silva JR (1998) Towards historical R-trees. In: Symposium on applied computing, pp 235–240. ACM
96.
Nascimento MA, Silva JR, Theodoridis Y (1999) Evaluation of access structures for discretely moving points. In: Spatio-temporal database management, pp 171–189. Springer
97.
Nguyen T, He Z, Chen YPP (2012) SeTPR*-tree: Efficient buffering for spatiotemporal indexes via shared execution. Comput J 56(1):115–137CrossRef
98.
Nguyen T, He Z, Zhang R, Ward P (2012) Boosting moving object indexing through velocity partitioning. The Proceedings of the VLDB Endowment (PVLDB’12) 5(9):860–871CrossRef
99.
Nguyen-Dinh LV, Aref WG, Mokbel MF (2010) Spatio-temporal access methods: Part 2 (2003-2010). IEEE Data Eng Bull 33(2):46–55
100.
Ni J, Ravishankar CV (2005) PA-Tree: A parametric indexing scheme for spatio-temporal trajectories. In: International symposium on spatial and temporal databases, pp 254–272. Springer
101.
Nievergelt J, Hinterberger H, Sevcik KC (1984) The grid file: an adaptable, symmetric multikey file structure. ACM Trans Database Syst (TODS) 9(1):38–71CrossRef
102.
Orenstein JA, Merrett TH (1984) A class of data structures for associative searching. In: Proceedings of the 3rd ACM SIGACT-SIGMOD symposium on Principles of database systems (PODS), pp 181–190. ACM
103.
Patel JM, Chen Y, Chakka VP (2004) STRIPES: An efficient index for predicted trajectories. In: The international conference on management of data (SIGMOD’04), pp 637–646
104.
Patroumpas K, Sellis T (2009) Monitoring orientation of moving objects around focal points. In: International symposium on spatial and temporal databases, pp 228–246. Springer
105.
Pelanis M, Šaltenis S, Jensen CS (2006) Indexing the past, present, and anticipated future positions of moving objects. ACM Trans Database Syst (TODS) 31 (1):255–298CrossRef
106.
Pfoser D, Jensen CS, Theodoridis Y et al (2000) Novel approaches to the indexing of moving object trajectories. In: The Proceedings of the VLDB Endowment (PVLDB’00), pp 395–406
107.
Popa IS, Zeitouni K, Oria V, Barth D, Vial S (2010) PARINET: A tunable access method for in-network trajectories. In: The IEEE international conference on data engineering (ICDE’10), pp 177–188. IEEE
108.
Porkaew K, Lazaridis I, Mehrotra S (2001) Querying mobile objects in spatio-temporal databases. In: International symposium on spatial and temporal databases (SSTD’01), pp 59–78. Springer
109.
Prabhakar S, Xia Y, Kalashnikov DV, Aref WG, Hambrusch SE (2002) Query indexing and velocity constrained indexing: Scalable techniques for continuous queries on moving objects. IEEE Trans Comput 51(10):1124–1140CrossRef
110.
Procopiuc CM, Agarwal PK, Har-Peled S (2002) Star-tree: an efficient self-adjusting index for moving objects. In: Workshop on algorithm engineering and experimentation, pp 178–193. Springer
111.
Pugh W (1990) Concurrent maintenance of lists. In: Dept. of computer science, university of maryland, college park
112.
Ranu S, Deepak P, Telang AD, Deshpande P, Raghavan S (2015) Indexing and matching trajectories under inconsistent sampling rates. In: The IEEE international conference on data engineering (ICDE’15), pp 999–1010
113.
Ray S (2014) Towards high performance spatio-temporal data management systems. In: The IEEE international conference on mobile data management (MDM’14), vol 2, pp 19–22
114.
Romero M, Brisaboa N, Rodríguez MA (2012) The SMO-index: A succinct moving object structure for timestamp and interval queries. In: Advances in geographic information systems, pp 498–501
115.
Saltenis S, Jensen CS (2002) Indexing of moving objects for location-based services. In: International conference on data engineering (ICDE’02), pp 463–472. IEEE
116.
Šaltenis S, Jensen CS, Leutenegger ST, Lopez MA (2000) Indexing the positions of continuously moving objects. In: International conference on management of data (SIGMOD’00), vol 29, pp 331–342. ACM
117.
Sandu Popa I, Zeitouni K, Oria V, Barth D, Vial S (2011) Indexing in-network trajectory flows. Intern J Very Large Data Bases (VLDB J) 20(5):643–669CrossRef
118.
Schmiegelt P, Behrend A, Seeger B, Koch W (2014) A concurrently updatable index structure for predicted paths of moving objects. Data Knowl Eng 93:80–96CrossRef
119.
Senechal M (1993) Spatial tessellations: Concepts and applications of voronoi diagrams. Science 260(5111):1170–1173CrossRef
120.
Seo DM, Song SI, Park YH, Yoo JS, Kim MH (2008) Bdh-tree: A B+-tree based indexing method for very frequent updates of moving objects. In: International symposium on computer science and its applications (CSA’08), pp 314–319. IEEE
121.
Shen B, Zhao Y, Li G, Zheng W, Qin Y, Yuan B, Rao Y (2017) V-Tree: Efficient kNN search on moving objects with road-network constraints. In: The IEEE international conference on data engineering (ICDE’17), pp 609–620
122.
Šidlauskas D, Ross K, Jensen C, Šaltenis S (2011) Thread-level parallel indexing of update intensive moving-object workloads. Adv Spatial Temporal Database 6849:186–204
123.
Šidlauskas D, Šaltenis S, Christiansen CW, Johansen JM, Šaulys D (2009) Trees or grids?: indexing moving objects in main memory. In: The ACM international conference on advances in geographic information systems (SIGSPATIAL’09), pp 236–245
124.
Šidlauskas D, Šaltenis S, Jensen CS (2012) Parallel main-memory indexing for moving-object query and update workloads. In: The international conference on management of data (SIGMOD’12), pp 37–48
125.
Silva YN, Xiong X, Aref WG (2009) The RUM-tree: supporting frequent updates in R-trees using memos. Intern J Very Large Data Bases (VLDB J) 18 (3):719–738CrossRef
126.
Singh M, Zhu Q, Jagadish H (2012) SWST: A disk based index for sliding window spatio-temporal data. In: The IEEE international conference on data engineering (ICDE’12), pp 342–353
127.
Skovsgaard A, Sidlauskas D, Jensen CS (2014) Scalable top-k spatio-temporal term querying. In: The IEEE international conference on data engineering (ICDE’14), pp 148–159
128.
Song Z, Roussopoulos N (2001) Hashing moving objects. In: International conference on mobile data management (MDM’01), pp 161–172. Springer
129.
Song Z, Roussopoulos N (2003) SEB-Tree: An approach to index continuously moving objects. In: International conference on mobile data management (MDM’03), pp 340–344. Springer
130.
Stantic B, Topor R, Terry J, Sattar A (2010) Advanced indexing technique for temporal data. Computer Science and Information Systems 7(4):679–703
131.
Tanimoto S, Pavlidis T (1975) A hierarchical data structure for picture processing. Comput Graphics Image Process 4(2):104–119CrossRef
132.
Tao Y, Faloutsos C, Papadias D, Liu B (2004) Prediction and indexing of moving objects with unknown motion patterns. In: International conference on management of data (SIGMOD’04), pp 611–622. ACM
133.
Tao Y, Papadias D (2001) Efficient historical R-trees. In: The international conference on scientific and statistical database management (SSDBM’01), p 0223. IEEE
134.
Tao Y, Papadias D (2001) MV3R-tree: A spatio-temporal access method for timestamp and interval queries. In: The Proceedings of the VLDB Endowment (PVLDB’01), pp 431–440
135.
Tao Y, Papadias D, Sun J (2003) The TPR*-tree: An optimized spatio-temporal access method for predictive queries. In: International conference on very large data bases (PVLDB’03), pp 790–801. VLDB endowment
136.
Tayeb J, Ulusoy Ö, Wolfson O (1998) A quadtree-based dynamic attribute indexing method. Comput J 41(3):185–200CrossRef
137.
That DHT, Popa IS, Zeitouni K (2015) TRIFL: A generic trajectory index for flash storage. ACM Trans Spatial Algorithm Syst 1(2):6CrossRef
138.
Theodoridis Y, Vazirgiannis M, Sellis T (1996) Spatio-temporal indexing for large multimedia applications. In: International conference on multimedia computing and systems, pp 441–448. IEEE
139.
To QC, Dang TK, Kung J (2011) OST-Tree: An access method for obfuscating spatio-temporal data in location based services. In: International conference on new technologies, mobility and security (NTMS’11), pp 1–5. IEEE
140.
Toshniwal A, Taneja S, et al. (2014) Storm@ twitter. In: The international conference on management of data (SIGMOD’14), pp 147–156
141.
Tung HDT, Jung YJ, Lee EJ, Ryu KH (2004) Moving point indexing for future location query. In: International conference on conceptual modeling, pp 79–90. Springer
142.
143.
Tzouramanis T, Vassilakopoulos M, Manolopoulos Y (1998) Overlapping linear quadtrees: a spatio-temporal access method. In: International symposium on advances in geographic information systems, pp 1–7. ACM
144.
Ulrich T (2000) Loose octrees. Game Programming Gems 1:434–442
145.
Valdés F, Güting RH (2017) Index-supported pattern matching on tuples of time-dependent values. GeoInformatica 21(3):429–458CrossRef
146.
Wang H, Belhassena A (2017) Parallel trajectory search based on distributed index. Inf Sci 388:62–83CrossRef
147.
Wang L, Zheng Y, Xie X, Ma WY (2008) A flexible spatio-temporal indexing scheme for large-scale GPS track retrieval. In: International conference on mobile data management (MDM’08), pp 1–8. IEEE
148.
Wang S, Bao Z, Culpepper JS, Sellis T, Sanderson M, Qin X (2017) Answering top-k exemplar trajectory queries. In: The IEEE international conference on data engineering (ICDE’17), pp 597–608. IEEE
149.
Wang X, Zhang Y, Zhang W, Lin X, Wang W (2015) AP-Tree: Efficiently support location-aware publish/subscribe. Intern J Very Large Data Bases (VLDB J.) 24(6):823–848CrossRef
150.
Xu X, Lu JHW (1990) RT-tree: An improved R-tree indexing structure for temporal spatial databases. In: The international symposium on spatial data handling, pp 1040–1049
151.
Xie X, Lu H, Pedersen TB (2013) Efficient distance-aware query evaluation on indoor moving objects. In: The IEEE international conference on data engineering (ICDE’13), pp 434–445. IEEE
152.
Xie X, Mei B, Chen J, Du X, Jensen CS (2016) Elite: an elastic infrastructure for big spatiotemporal trajectories. Intern J Very Large Data Bases (VLDB J) 25(4):473–493CrossRef
153.
Xiong X, Aref WG (2006) R-trees with update memos. In: The IEEE international conference on data engineering (ICDE’06), pp 22–22
154.
Xiong X, Mokbel MF, Aref WG (2006) LUGRid: Update-tolerant grid-based indexing for moving objects. In: International conference on mobile data management (MDM’13), p 13
155.
Xu X, Xiong L, Sunderam V (2016) D-grid: an in-memory dual space grid index for moving object databases. In: The IEEE international conference on mobile data management (MDM’16), pp 252–261
156.
Xu X, Xiong L, Sunderam V, Liu J, Luo J (2015) Speed partitioning for indexing moving objects. In: The international symposium on spatial and temporal databases (SSTD’15), pp 216–234
157.
Xu Y, Tan G (2014) Sim-Tree: indexing moving objects in large-scale parallel microscopic traffic simulation. In: ACM Conference on principles of advanced discrete simulation (PADS) (SIGSIM’14), pp 51–62
158.
YAN Qy, MENG Fr (2004) Multiple version TPR-tree. Comput Eng Design 10:057
159.
Yan X, Guo J, Lan Y, Cheng X (2013) A biterm topic model for short texts. In: Proceedings of the 22nd international conference on World Wide Web, pp 1445–1456. ACM
160.
Yao B, Li F, Hadjieleftheriou M, Hou K (2010) Approximate string search in spatial databases. In: The IEEE international conference on data engineering (ICDE’10), pp 545–556. IEEE
161.
Yiu ML, Tao Y, Mamoulis N (2008) The Bdual-tree: Indexing moving objects by space filling curves in the dual space. Intern J Very Large Data Bases (VLDB J) 17(3):379–400CrossRef
162.
Yu Z, Liu Y, Yu X, Pu KQ (2015) Scalable distributed processing of k nearest neighbor queries over moving objects. IEEE Trans Knowl Data Eng (TKDE) 27(5):1383–1396CrossRef
163.
Zaharia M, Xin RS, Wendell P, Das T, Armbrust M, Dave A, Meng X, Rosen J, Venkataraman S, Franklin MJ et al (2016) Apache spark: a unified engine for big data processing. Commun ACM 59(11):56–65CrossRef
164.
Zäschke T, Zimmerli C, Norrie MC (2014) The PH-tree: A space-efficient storage structure and multi-dimensional index. In: The international conference on management of data (SIGMOD’14), pp 397–408
165.
Zheng B, Yuan NJ, Zheng K, Xie X, Sadiq S, Zhou X (2015) Approximate keyword search in semantic trajectory database. In: The IEEE international conference on data engineering (ICDE’15), pp 975–986. IEEE
166.
Zheng K, Shang S, Yuan NJ, Yang Y (2013) Towards efficient search for activity trajectories. In: The IEEE international conference on data engineering (ICDE’13), pp 230–241. IEEE
167.
Zheng K, Trajcevski G, Zhou X, Scheuermann P (2011) Probabilistic range queries for uncertain trajectories on road networks. In: The international conference on extending database technology (EDBT’11), pp 283–294
168.
Zheng K, Zheng B, Xu J, Liu G, Liu A, Li Z (2016) Popularity-aware spatial keyword search on activity trajectories. World Wide Web 4(20):749–773
169.
Zhou P, Zhang D, Salzberg B, Cooperman G, Kollios G (2005) Close pair queries in moving object databases. In: Proceedings of the 13th annual ACM international workshop on Geographic information systems, pp 2–11. ACM
170.
Zhu Y, Ren X, Feng J (2006) NCO-Tree: A spatio-temporal access method for segment-based tracking of moving objects. In: International conference on knowledge-based and intelligent information and engineering systems, pp 1191–1198. Springer
171.
Zhu Y, Wang S, Zhou X, Zhang Y (2013) RUM+-Tree: A new multidimensional index supporting frequent updates. In: The international conference on web-age information management (WAIM’13), pp 235–240
Metadata
Title
Spatio-temporal access methods: a survey (2010 - 2017)
Authors
Ahmed R. Mahmood
Sri Punni
Walid G. Aref
Publication date
09-10-2018
Publisher
Springer US
Published in
GeoInformatica / Issue 1/2019
Print ISSN: 1384-6175
Electronic ISSN: 1573-7624
DOI
https://doi.org/10.1007/s10707-018-0329-2